How to Find Length of a Linked List? With Examples [Latest]

• A linked list is a linear data structure used for storing collections of data
• Successive elements are connected by pointers
• The last element points to NULL
• Each element is a separate object and is called a Node
• Each node in a linked list comprises of two parts
  • Data
  • Reference to Next Node
  • 

How to Find the Length of a Linked List?

There are two ways to find the length of a linked list:

1. Iterative Approach
2. Recursive Approach

Length of Linked List using Iterative Approach

We will use the Linked list traversal to find the length of a linked list.

• Head Points to the First Node of The List.
• Initialize the count variable with value 0
• Initialize the temp variable with Head
• As we access each Node, the value of count variable is increased by 1.
• Stop The process when we reach null.
• Do not change the head reference.
• 

Code in Java

package com.journaldev.ds;
public class MyLinkedList {
	public class Node {
		int data;
		Node next;
	}
	public Node head;
	public Node tail;
	public int size;
	public int getFirst() throws Exception {
		if (this.size == 0) {
			throw new Exception("linked list is empty");
		}
		return this.head.data;
	}
	public int getLast() throws Exception {
		if (this.size == 0) {
			throw new Exception("linked list is empty");
		}
		return this.tail.data;
	}
	public void display() {
		Node temp = this.head;
		while (temp != null) {
			System.out.println(temp.data + " ");
			temp = temp.next;
		}
	}
	public void addFirst(int item) {
		Node nn = new Node();
		nn.data = item;
		if (this.size == 0) {
			this.head = nn;
			this.tail = nn;
			this.size = this.size + 1;
		} else {
			nn.next = this.head;
			this.head = nn;
			this.size = this.size + 1;
		}
	}
	public int length() {
		Node temp = this.head;
		int count = 0;
		while (temp != null) {
			count++;
			temp = temp.next;
		}
		return count;
	}
	public static void main(String[] args) {
		MyLinkedList ll = new MyLinkedList();
		ll.addFirst(10);
		ll.addFirst(20);
		ll.addFirst(30);
		ll.addFirst(40);
		ll.addFirst(50);
		System.out.println("Length of Linked List is " + ll.length());
	}
}

Code in C

#include <stdio.h>
#include <stdlib.h>
/* A structure of linked list node */
struct node {
  int data;
  struct node *next;
} *head;
void initialize(){
    head = NULL;
}
/*
Inserts a node in front of a singly linked list.
*/
void insert(int num) {
    /* Create a new Linked List node */
    struct node* newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data  = num;
    /* Next pointer of new node will point to head node of linked list  */
    newNode->next = head;
    /* make new node as the new head of linked list */
    head = newNode;
    printf("Inserted Element : %dn", num);
}
int getLength(struct node *head){
    int length =0;
    while(head != NULL){
        head = head->next;
        length++;
    }
    return length;
}
/*
Prints a linked list from head node till the tail node
*/
void printLinkedList(struct node *nodePtr) {
  while (nodePtr != NULL) {
     printf("%d", nodePtr->data);
     nodePtr = nodePtr->next;
     if(nodePtr != NULL)
         printf("-->");
  }
}
int main() {
    initialize();
    /* Creating a linked List*/
    insert(8);
    insert(3);
    insert(2);
    insert(7);
    insert(9);
    printf("nLinked Listn");
    printLinkedList(head);
    printf("nLinked List Length : %d", getLength(head));
    return 0;
}

Output

Length of Linked List using Recursive Solution

Base Case:

• Last Node points to Null value
• Return 0

Recursive Case:

• At each step update the Value of Current Node to the Next Node
• Call= 1+fun(curr.next)
• 

Example:
There are 3 elements in the linked list: LL1, LL2, and LL3.

We will Observe What happens in the Memory Stack when the Recursive Call is made.

MEMORY STACK:

The main function calls LL1, LL1 calls LL2, LL2 calls LL3, LL3 calls null value.

As Null value is reached, we return from here.

0 is returned to LL3, LL3 returns 1 to LL2, LL2 returns 2 to LL1.

LL1 finally returns 3 to the main function.

Code in Java

package com.journaldev.ds;
public class MyLinkedList {
    public class Node {
         int data;
         Node next;
    }
    public Node head;
    public Node tail;
    public int size;
    public int getfirst() throws Exception {
         if (this.size == 0) {
             throw new Exception("linked list is empty");
         }
         return this.head.data;
    }
    public int RemoveFirst() throws Exception {
         if (this.size == 0) {
             throw new Exception("LL is empty");
         }
         Node temp = this.head;
         if (this.size == 1) {
             this.head = null;
             this.tail = null;
             size = 0;
         } else {
             this.head = this.head.next;
             this.size--;
         }
         return temp.data;
    }
    public void addFirst(int item) {
         Node nn = new Node();
         nn.data = item;
         if (this.size == 0) {
             this.head = nn;
             this.tail = nn;
             this.size = this.size + 1;
         } else {
             nn.next = this.head;
             this.head = nn;
             this.size = this.size + 1;
         }
    }
    public int lengthUsingRecursiveApproach (){
         return lengthUsingRecursiveApproach(this.head);
    }
    private int lengthUsingRecursiveApproach(Node curr) {
         // TODO Auto-generated method stub
         if (curr == null) {
             return 0;
         }
         return 1 + lengthUsingRecursiveApproach (curr.next);
    }
    public static void main(String[] args) {
         MyLinkedList ll = new MyLinkedList();
         // insert elements into the Linked List
        ll.addFirst(10);
         ll.addFirst(20);
         ll.addFirst(30);
         ll.addFirst(40);
         ll.addFirst(50);
         // Length of List
         System.out.println("Recursive Approach length " + ll.lengthUsingRecursiveApproach(ll.head));
    }
}

Code in C

#include <stdio.h>
struct Node
{
    int data;
    struct Node* next;
};
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node =  (struct Node*) malloc(sizeof(struct Node));
    new_node->data  = new_data;
    /* link the old list of the new node */
    new_node->next = (*head_ref);
    (*head_ref)    = new_node;
}
int getCount(struct Node* head)
{
    // Base case
    if (head == NULL)
        return 0;
    return 1 + getCount(head->next);
}
int main()
{
    struct Node* head = NULL;
    push(&head, 1);
    push(&head, 3);
    push(&head, 1);
    push(&head, 2);
    push(&head, 1);
    printf("count of nodes is %d", getCount(head));
    return 0;
}

Output

Time Complexity

O(N) in both the recursive and iterative solution, as all we need, is a single traversal to know the length.