Find length of a Singly Linked List

   Last Updated: 06 October, 2024       🕓  5 Mins

In this Linked List tutorial, we will see and learn how to find the length of a Linked List. The length of a linked list is the total number of nodes present in a linked list.

Examples:

There are basically two approaches to find a length of a linked list:

1. Iterative Approach
2. Recursive Approach

1. Find length of a linked list using an Iterative Approach

Following are the steps we need to follow to find the length of the Linked List using Iterative approach:

1. Create a count variable and Initialize with value 0.
2. Initialize the temp variable with Head, tempNode = head.
3. Do following while tempNode is not NULL
   • tempNode = tempNode -> next
   • Increment count by 1
4. Once tempNode is NULL then return count.

In the below given example we will see the implementation of Iterative approach in Java.

public class Node { public int data; public Node next; // Constructor public Node(int data) { this.data = data; this.next = null; } } public class FindLengthUsingIterativeApproachInSLL { // Counts number of nodes in linked list static int countTotalNodes(Node head) { // Initialize count with 0 int count = 0; // Initialize tempNode with head of Linked List Node tempNode = head; // Traverse till we reach null while (tempNode != null) { // Increment count by 1 count++; // Move pointer to next node tempNode = tempNode.next; } // Return the count of nodes return count; } public static void main(String[] args) { // Create a linked list Node head = new Node(10); head.next = new Node(20); head.next.next = new Node(30); head.next.next.next = new Node(40); head.next.next.next.next = new Node(50); // Linked list will be created like this // 10 -> 20 -> 30 -> 40 -> 50 // Printing total number of nodes in the list System.out.println("Length of the linked list is: " + countTotalNodes(head)); // Now adding two more nodes head.next.next.next.next.next = new Node(60); head.next.next.next.next.next.next = new Node(70); // Now, the linked list will be like this // 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 System.out.println("After adding two new nodes, length of the linked list is: " + countTotalNodes(head)); } }

Output

Length of the linked list is: 5
After adding two new nodes, length of the linked list is: 7

Time complexity: O(N), Where N is the length of the linked list.

Auxiliary Space: O(1), As constant extra space is used.

2. Find length of linked list using Recursive Approach

To implement the recursive approach, we defined a function called countTotalNodes(node). This function takes a node as an argument and calls itself with the next node until we reach the end of the linked list. Each of the recursive calls returns 1 + the count of remaining nodes.

In the below given example we will see how to find the length of a linked list using Recursive approach in Java.

public class Node { public int data; public Node next; // Constructor public Node(int data) { this.data = data; this.next = null; } } public class FindLengthUsingRecursiveApproachInSLL { static int countTotalNodes(Node head) { // Returns 0, if list is empty if (head == null) { return 0; } // Adding 1 in the total number of nodes of the list return 1 + countTotalNodes(head.next); } public static void main(String[] args) { // Create a linked list Node head = new Node(10); head.next = new Node(20); head.next.next = new Node(30); head.next.next.next = new Node(40); head.next.next.next.next = new Node(50); // Linked list will be created like this // 10 -> 20 -> 30 -> 40 -> 50 // Printing total number of nodes in the list System.out.println("Length of the linked list is: " + countTotalNodes(head)); // Now adding two more nodes head.next.next.next.next.next = new Node(60); head.next.next.next.next.next.next = new Node(70); // Now, the linked list will be like this // 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 System.out.println("After adding two new nodes, length of the linked list is: " + countTotalNodes(head)); } }

Output

Length of the linked list is: 5
After adding two new nodes, length of the linked list is: 7

Time complexity: O(N), Where N is the length of the linked list.

Auxiliary Space: O(N), Extra space is used in the recursion call stack.