How do you find length of a Singly Linked list using Loop and Recursion

Hello guys, here is one of the classical programming questions how do you find the length of a linked list using recursion and without recursion. This is not the about theLinkedList class of Java API but the linked list data structure which is made of nodes which contains both data and address of the next node. In order to calculate the length, you need to count all nodes in the linked list. Since it's a singly linked list you can only move in one direction from the head to tail.  This coding problem was asked to me on my first interview with a multinational Investment bankAfter that, this question has been asked to me on several occasions in other Programming Job Interviews as well.

What makes this question interesting is that Java developers are not that great with the data structure as compared to a C++ developer which is obvious because of the fundamental difference between these two languages.

The C++ is more of system programming language while Java is more on application programming, also a rich set of Java API allows the programmer to skip this kind of basic programming techniques.

By the way, if you are preparing for programming job interviews and looking for more coding or algorithm based questions like anarray, string , or other data structures, you can always search this blog. I have shared a lot of questions in this blog on over the years.

If you like to read books then you can also take a look at Cracking the Coding Interviews , which contains 189 Programming Questions and Solutions. One of the best collection of coding questions for beginners, intermediate, and experienced programmers.

It contains questions from both fundamental and advanced data structure like a doubly linked list, binary trees, self-balanced trees, and binary heaps. Btw, if you are not familiar with essential data structure then  I suggest you join a good course like  Data Structures and Algorithms: Deep Dive Using Java on Udemy, it's one of the best course to learn and master data structure and Algorithms. Even if you know data structure, this can be used to further strengthen your knowledge.

2 Ways to find the length of the linked list in Java

Anyway let's come back to the question, everybody knows that in the singly linked list is the last element will point to"null" element, So the first answer would most of the times be "I will use a counter and increment till it reaches the end of the element".

Once you reach at the end of the linked list, the value of counter would be equal to the total number of elements encountered i.e. length of the elements.

Here is the sample code to implement this algorithm, you can use the linked list implementation given in this article for understanding the purpose. We are assuming the linked list class hold reference of the head, a pointer which points to the first node in the linked list.

To learn more about linked list data structure, you can pick a good course on data structure and algorithms like  Algorithms and Data Structures - Part 1 and 2 on Pluralsight.

1. Iterative Solution

In this solution, we are just going through the entire linked list, one node at a time until we reach the null, which is the end of the linked list.

public int length(){
 int count=0;
 Node current = this.head;

 while(current != null){
  count++;
  current=current.next()
 }
 return count;
}

If you answer this question without any difficulty most interviewer will ask you to write a"recursive" solutionfor this problem, just to check how you deal with recursion if your first answer would have been recursive they will ask you to write an "iterative solution" as shown above.

Btw, if you are preparing for a Programming job interview, it's important to refresh data structure and algorithms before interviews.  I suggest you to check out the  Data Structures in Java: An Interview Refresher course on Educative to do well on your interview and practice more linked list based coding questions.

And now, here is how to find the length of singly linked list using recursion in Java :

2. Recursive Solution:

This is a much more concise then Iterative solution but sometimes it's not easy to come up with the solution if you are not familiar with Recursion, but if you do then it's very easy.

public int length(Node current){
 if(current == null){ //base case
   return 0;
 }
 return 1+length(current.next());
}

You can see that we have used the fact that the last node will point to null to terminate the recursion. This is called the base case. It's very important to identify a base case while coding a recursive solution, without a base case, your program will never terminate and result in StackOverFlowError.

Further Learning

Data Structures and Algorithms: Deep Dive Using Java

Algorithms and Data Structures - Part 1 and 2

Data Structures in Java: An Interview Refresher

Cracking the Coding Interview - 189 Questions and Solutions

Related Data Structure and Algorithm Interview Questions from Javarevisited Blog

• How to implement a linked list using generics in Java? ( solution )
• How to reverse a singly linked list in Java? ( solution )
• How to find the middle element of the linked list using a single pass? ( solution )
• How to find the 3rd element from the end of a linked list in Java? (solution)
• Top 15 Data Structure and Algorithm Interview Questions (see here)
• Top 20 String coding interview questions (see here)
• 133 core Java interview questions of the last 5 years (see here)
• Top 30 Array Coding Interview Questions with Answers ( see here )
• Top 30 linked list coding interview questions ( see here )
• Top 50 Java Programs from Coding Interviews ( see here )
• 5 Free Data Structure and Algorithms Courses for Programmers (courses)
• 10 Algorithms Books Every Programmer Should read ( books )
• 50+ Data Structure and Algorithms Problems from Interviews ( questions )
• 10 Free Data Structure and Algorithm Courses for Programmers ( courses )
• 100+ Data Structure Coding Problems from Interviews ( questions )

Thanks for reading this article so far. If you like this article then please share with your friends and colleagues. If you have any question or doubt then please let us know and I'll try to find an answer for you. As always suggestions, comments, innovative and better answers are most welcome.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the  Easy to Advanced Data Structures

course on Udemy. It's authored by a Google Software Engineer and Algorithm expert and its completely free of cost.