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.

8 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

Anonymous said...

Java LinkedList is indeed Doubly linked list implementation of List and Deque interface in Java, as stated by Java doc. The do have two pointers first and last to point at both end of linked list.

Anonymous said...

Can you write a generic implementation of Singly linked list in Java?

Joyti said...

This question was asked to me as well, but they also asked me to find the complexity of both iterative and recursive solution. I said that if whether you use two pointer or one pointer approach you are checking almost each element, which means it's O(n) on times. Then he said, can you optimize the solution to reduce the time atleast to logarithimic or constant time. This question I couldn't answer because there is no other way to do this until you keep a pointer pointing to keep track of size. If anyone knows the aswer or trick, let me know please

Post a Comment