December 26, 2018

Find length of a linked list by iterative method

We are going to find lenght of a Linked List using iterative method. You can read the recursive method here.

The simple logic to find length of a Linked list is – to increment a counter until you run out of nodes.

Here is the simple algorithm.

Step 1 :- Initialize a counter to 0

Step 2 :- Until we run out of nodes i.e our reference to the nodes become null.

2-a) increment the counter by 1

2-b) move to the next node

Step 3 :- return the value of counter

I am providing two implementations.

One is going to be verbose, and other one will be more concise and readable.

Implementation 1 :-

private static int length(Node head) {                                                           
        if(head == null) return 0;                                                                   
                                                                                                     
        int length = 0;                                                                              
        while(head != null) {                                                                        
            ++length;                                                                                
            head = head .next;                                                                       
        }                                                                                            
                                                                                                     
        return length;                                                                               
}

You can see that we have initialized a variable and we are incrementing it until we run out of nodes.

Implementation 2 :-

private static int lengthBetter(Node head) {                                                     
        int length = 0;                                                                              
                                                                                                     
        while(head != null) {                                                                        
            ++length;                                                                                
            head = head .next;                                                                       
        }                                                                                            
                                                                                                     
        return length;                                                                               
}

This one is more concise. It does not have the if-statement.

Now, I am going to walk you through the code.

The Step 1 :-  create a counter

int length = 0;

The Step 2 :- while we have nodes – 1. increment counter 2. move to the next node

while(head != null) {                                                                        
    ++length;                                                                                
    head = head .next;                                                                       
}

The step 3 :- return the counter value

return length;

Complete Code

public class LinkedListLengthIterative {                                                             
    private static class Node {                                                                      
        int data;                                                                                    
        Node next;                                                                                   
        Node prev;                                                                                   
                                                                                                     
        Node(final int data) {                                                                       
            this .data = data;                                                                       
        }                                                                                            
    }                                                                                                
                                                                                                     
    public static void main(String ... args) {                                                       
        Node a = new Node(1);                                                                        
        Node b = new Node(2);                                                                        
        Node c = new Node(3);                                                                        
        Node d = new Node(4);                                                                        
        a .next = b;                                                                                 
        b .next = c;                                                                                 
        c .next = d;                                                                                 
                                                                                                     
        System.out.println("Length is :- " + length(a));                                             
        System .out .println("Length is :- " + lengthBetter(a));                                     
                                                                                                     
    }                                                                                                
                                                                                                     
    //Method 1                                                                                       
    private static int length(Node head) {                                                           
        if(head == null) return 0;                                                                   
                                                                                                     
        int length = 0;                                                                              
        while(head != null) {                                                                        
            ++length;                                                                                
            head = head .next;                                                                       
        }                                                                                            
                                                                                                     
        return length;                                                                               
    }                                                                                                
                                                                                                     
    //Method 2                                                                                       
    private static int lengthBetter(Node head) {                                                     
        int length = 0;                                                                              
                                                                                                     
        while(head != null) {                                                                        
            ++length;                                                                                
            head = head .next;                                                                       
        }                                                                                            
                                                                                                     
        return length;                                                                               
    }                                                                                                
}