# How to Find Length of a Linked List?

Filed Under: C Programming

## 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  ## 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 Node {

int data;

Node next;

}

public Node tail;
public int size;

public int getFirst() throws Exception {

if (this.size == 0) {

throw new Exception("linked list is empty");
}

}

public int getLast() throws Exception {

if (this.size == 0) {

throw new Exception("linked list is empty");
}
return this.tail.data;
}

public void display() {

while (temp != null) {
System.out.println(temp.data + " ");
temp = temp.next;
}
}

Node nn = new Node();

nn.data = item;
if (this.size == 0) {
this.tail = nn;
this.size = this.size + 1;

} else {

this.size = this.size + 1;

}

}

public int length() {

int count = 0;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}

public static void main(String[] args) {

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;

void initialize(){

}

/*

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  */

/* make new node as the new head of linked list */

printf("Inserted Element : %d\n", num);

}

int length =0;

length++;

}

return length;

}

/*

*/

while (nodePtr != NULL) {

printf("%d", nodePtr->data);

nodePtr = nodePtr->next;

if(nodePtr != NULL)

printf("-->");

}

}

int main() {

initialize();

insert(8);

insert(3);

insert(2);

insert(7);

insert(9);

return 0;

}
``````

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

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

``````package com.journaldev.ds;

public class Node {

int data;

Node next;

}

public Node tail;

public int size;

public int getfirst() throws Exception {

if (this.size == 0) {

throw new Exception("linked list is empty");

}

}

public int RemoveFirst() throws Exception {

if (this.size == 0) {

throw new Exception("LL is empty");

}

if (this.size == 1) {

this.tail = null;

size = 0;

} else {

this.size--;

}

return temp.data;

}

Node nn = new Node();

nn.data = item;

if (this.size == 0) {

this.tail = nn;

this.size = this.size + 1;

} else {

this.size = this.size + 1;

}

}

public int lengthUsingRecursiveApproach (){

}

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) {

// insert elements into the Linked List

// 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 */

}

{

// Base case

return 0;

}

int main()

{

printf("count of nodes is %d", getCount(head));

return 0;

}
``````

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.

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages