How to Find Length of a Linked List?

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
    • Iterative-Solution

 

LinkedList Node

Iterative-Solution

 

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

Code in Java

Code in C

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

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

Code in C

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.

By admin

Leave a Reply

%d bloggers like this: