Length of Linked List using iterative and recursive methods

05 min read

Given a singly linked list, we need to find the length of the linked list, (i.e.) Total number of nodes present in the linked list.

length of linked list

 

Iterative Solution to find the length of linked list

1) Initialize count = 0 
2) Initialize a node pointer, i.e, temp = head.
3) Do following while temp is not NULL
     a) temp = temp -> next
     b) count++;
4) Return count 

C program to find the length of the linked list (Iterative approach)

#include <stdio.h>
#include <stdlib.h>
// Creating node with data and a pointer
struct node {
int data;
struct node *next;
}*head;

void createList(int n)
{
struct node *newNode, *temp;
int data, i;

head = (struct node *)malloc(sizeof(struct node));
// When the list is empty
if(head == NULL)
{
printf("Unable to allocate memory.");
}
else
{
printf("\nEnter the data of node 1: ");
scanf("%d", &data);
head->data = data;
head->next = NULL;
temp = head;
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
if(newNode == NULL)
{
printf("Unable to allocate memory.");
break;
}
else
{
printf("\nEnter the data of node %d: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->next = NULL;
temp->next = newNode;
temp = temp->next;
}
}
}
}

void length_of_list()
{
struct node * temp = head;
int count = 0;
if(head == NULL)
{
printf("List is empty\n");
count= 0;
}
while(temp != NULL)
{
temp = temp -> next; // Move to the next node
count++; // Increment the number of nodes by 1
}
printf("\nThe Length of the Linked List : %d ",count);
}

void displayList()
{
struct node *temp;
if(head == NULL)
{
printf("List is empty.\n");
}
else
{
temp = head;
while(temp != NULL)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("\n");
}
}

int main()
{
int n, data;
printf("\nEnter the total number of nodes: ");
scanf("%d", &n);
createList(n);
printf("\nThe List is \n");
displayList();
length_of_list();
return 0;
}


Recursive solution to find the length of a linked list

1) If head is NULL, return 0.
2) Else return 1 + length_of_list(head->next)  // Iterate and add 1 to count until the end of the list.

C program to find the length of the linked list (Recursive approach)

#include <stdio.h>
#include <stdlib.h>
// Creating node with data and a pointer
struct node {
int data;
struct node *next;
}*head;

void createList(int n)
{
struct node *newNode, *temp;
int data, i;

head = (struct node *)malloc(sizeof(struct node));
// When the list is empty
if(head == NULL)
{
printf("Unable to allocate memory.");
}
else
{
printf("\nEnter the data of node 1: ");
scanf("%d", &data);
head->data = data;
head->next = NULL;
temp = head;
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
if(newNode == NULL)
{
printf("Unable to allocate memory.");
break;
}
else
{
printf("\nEnter the data of node %d: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->next = NULL;
temp->next = newNode;
temp = temp->next;
}
}
}
}

int length_of_list(struct node * head)
{
int count = 0;
if(head == NULL)
{
return 0;
}
return 1 + length_of_list(head -> next);
}

void displayList()
{
struct node *temp;
if(head == NULL)
{
printf("List is empty.\n");
}
else
{
temp = head;
while(temp != NULL)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("\n");
}
}

int main()
{
int n, data;
printf("\nEnter the total number of nodes: ");
scanf("%d", &n);
createList(n);
printf("\nThe List is \n");
displayList();
printf("\nThe Length of the Linked List : %d ",length_of_list(head));
return 0;
}



OUTPUT

linked list length

 
POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error