// Tutorial //

How to Find Length of a Linked List?

Published on August 3, 2022
Default avatar
By Pankaj
Developer and author at DigitalOcean.
How to Find Length of a Linked List?

While we believe that this content benefits our community, we have not yet thoroughly reviewed it. If you have any suggestions for improvements, please let us know by clicking the “report an issue“ button at the bottom of the tutorial.

What is a Linked List?

  • 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
Node
LinkedList Node
Linked List
Linked List

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.
Iterative Approach for LinkedList Length
Iterative Approach for LinkedList Length

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 : %d\n", 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 List\n");

    printLinkedList(head);

    printf("\nLinked List Length : %d", getLength(head));

    return 0;

}

Output

Iterative Solution Output
Iterative Solution 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)
Recursive Solution
Recursive Solution

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:

Memory Stack
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

Recursive Solution Output
Recursive Solution Output

Time Complexity

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

If you’ve enjoyed this tutorial and our broader community, consider checking out our DigitalOcean products which can also help you achieve your development goals.

Learn more here


About the authors
Default avatar
Pankaj

author

Developer and author at DigitalOcean.

Still looking for an answer?

Was this helpful?