Friday, October 1, 2010

How do you find length of a Singly Linked list

Hi Guys,

Here is one of the classical questions asked to me on an interview with multinational Investment bank after that this question asked to me on several times in other interviews also . what makes this question interesting is that java developers are not that great with data structure relative to C++ developer which is obvious because of fundamental difference between this two language.C++ is more of system programming language while java is more on application programming , also rich set of java API allows programmer to skip this kind of basic programming techniques.


anyway lets come back to the question , everybody knows that Linked lists is last element will point to "null" element , so first answer would most of the times would be "I will use a counter and increment till we reach the end of the element" e.g.


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" solution for this 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.

Recursive Solution:

public int length(Node current){
if(current == null) //base case
return 0;

return 1+length(current.next());
}

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

5 comments :

LinkedList said...

This example to find length of linked list can also be extended to solve problems like how do you find middle element of linked list in Single pass or how to you find nth element from last in linked list in one loop. key here is to use two pointer one incrementing one at a time while other incrementing two at a time.

Anonymous said...

Just wondering why the interviewer asks these kind of questions when we have an size() method to get the size?

-Durai

Anonymous said...

@Durai

Even i wonder why they ask this question.

@Linked list : Anyways thanks for sharing information

Aditya Chaudhary said...

Java LinkedList is doubly Linked List.

Pancham said...

If Java LinkedList is doubly Linked List, then it should contaion two null elements, one in the begining and other at the end. Please correct if I am wrong

Post a Comment