How to find length of a single Linked List

This is one of the question an interviewer asked me when I just started to look for a new company. I replied that using size() method of list when can find out the length of list. But, interviewer asked me to write a data structure code for this because most of the java developers are not that great with data structure. As, Java is rich set of API which makes Java developers to skip this kind of basic programming techniques.

What is Linked List

A linked list is a dynamic data structure consisting of a group of nodes together. The number of nodes in the list is not fixed and can grow and shrink on demand. Any application which has to deal with an unknown number of objects will need to use a linked list.

Each element (we will call it a node) of a list is comprising of two items - the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.

One disadvantage of a linked list against an array is that it does not allow direct access to the individual elements. If you want to access a particular item then you have to start at the head and follow the references until you get to that item.
Another disadvantage is that a linked list uses more memory compare with an array - we extra 4 bytes (on 32-bit CPU) to store a reference to the next node.

After waiting for around 2 min., I told interviewer that I can be possible in 2 ways. I thought about Iterative and Recursive solutions.

Ways to find length of List

• Iterative
• Recursive

Iterative Solution

Use a counter and increment it until you reach end of list:

public int size()
{
    int size = 0;
    Node current = head;
    while(current.next != null)
    {
        current = current.next;
        size++;     
    }
    return size;
}

Recursive

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

I gave the answer to this question and interviewer was happy but, then he dive deep into the data structure and asked more questions related to data structure, linked list, set and map. Though, I could qualify up to 8 rounds but couldn't go further.

Then, I thought of sharing my experience with others what I faced in interviews. I'll write more about those questions. Please check after sometime.

Also, feel free to post your comments, questions and feedback. If you found any error or any wrong information then provide me better information to change the content so that right information could reach others.