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.

##

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.

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 on data structure and algorithms e.g. Introduction to Algorithms by Thomas Cormen.

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

And now, here is

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.

Algorithms and Data Structures - Part 1

Algorithms and Data Structures - Part 2

Introduction to Algorithms

Related

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.

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 on data structure and algorithms e.g. Introduction to Algorithms by Thomas Cormen.

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

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.

**Further Reading**Algorithms and Data Structures - Part 1

Algorithms and Data Structures - Part 2

Introduction to Algorithms

Related

**Data Structure and Algorithm Interview Questions**from Javarevisited Blog- Top 15 Data Structure and Algorithm Interview Questions (see here)
- Top 20 String coding interview questions (see here)
- 133 core Java interview questions of 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)
- Top 5 books on Programming/Coding Interviews (list)

## 11 comments :

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.

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

-Durai

@Durai

Even i wonder why they ask this question.

@Linked list : Anyways thanks for sharing information

Java LinkedList is doubly Linked List.

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

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.

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

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

why recursive method doesn't work?

I tried it for head as well, but it keep returns 0 instead of number of nodes....

@Anonymous, you can find a generic implementation of a Singly linked list in Java here.

Does this program is also the solution of question "How to find length of linked list in one pass"? I am not sure, please clarify.

## Post a Comment