神刀安全网

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

Hi Guys,

Here is one of the classical programming questions asked to me first time on an interview with multinational Investment bank. After 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 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 e.g. array, string, or other data structure, you can always search this blog.

If you like to read books then you can also take a look at Cracking the Coding Interviews , which contains 150 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 doubly linked list, binary trees, self balanced trees, and binary heaps.

2 Ways to find length of linked list in Java

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

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

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

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, the first element.

Iterative Solutions

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.

You can also check out  Cracking the Coding Interviews for more linked list based coding questions.

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

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

Recursive Solution:

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 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.

As always suggestions , comments , innovative and better answers are most welcome.

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » How do you find length of a Singly Linked list using Loop and Recursion

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址