Linked List: Program to find the length of a linked list


Write a program to find the length of the linked list

Linked list is a series of node in which each node contains data field
and reference (pointer) to next node in the list

 
Iterative Approach

  ● Initialize count as zero and set temporary Pointer (temp) on head node and.
  ● Traverse whole linked list till temp is not NULL
  ● Increase the count by one and go to the next node.
  ● After traversing linked list length is obtained

 Complexity :
 Time Complexity : O(n) , where n is the size of linked list
 Space Complexity : O(1)

 
Recursive Approach

  int getCount(head)
  1) If head is NULL, return 0
  2) Else return 1 + getCount(head -> next)

Complexity:
Time Complexity : O(n) , where n is the size of linked list
Space Complexity : O(1)

 
Java Code
class Node
    {
        //initializing data field and next pointer of node
        int data;
        Node next;
        Node(int data)
        {
            data = data;
            next = null;
        }
    } 
    class LinkedList
    {
        Node head;
        //insertion of node in linked list
        public void insert(int new_data)
        {
            Node temp = new Node(new_data);
            temp.next = head;
            head = temp;
        }
        //iterative approach
        public int length()
        {
            Node current = head;
            int count = 0;
            while (current != null)
            {
                count++;
                current = current.next;
            }
            return count;
        }
        //recursive approach
        public int findLengthRecursive(Node node)
        {
            if (node == null)
                return 0;
            return 1 + findLengthRecursive(node.next);
        }
        public int findLength()
        {
            return findLengthRecursive(head);
        }
        public static void main(String[] args)
        {
            //initializing object of linkedlist class
            LinkedList ll = new LinkedList();
            ll.insert(10);
            ll.insert(50);
            ll.insert(60);
            ll.insert(30);
            ll.insert(20);
    
            //call for iterative function
            System.out.println("Using Iterative Approach");
            System.out.println("Length of Linked List is " + ll.length());
            
            //call for recursive function
            System.out.println("Using Recursive Approach");
            System.out.println("Length of Linked List is " + ll.findLength()); 
        }
    }
Output

Using Iterative Approach
Length of Linked List is 5
Using Recursive Approach
Length of Linked List is 5



Thanks for feedback.



Read More....
Clone a Linked List
Find the middle of linked list with odd no of nodes
Check if linked list nodes form a palindrome
Delete a node at specific position from linked list
Delete a node from linked list
Detect if cycle is present in a linked list