Find Length of a Linked List (Iterative and Recursive)?

Both recursion and iteration execute a series of instructions repeatedly. Recursion is when a declaration in a function repeatedly calls itself. Iteration means that the loop repeats itself until the control condition goes false. The main difference between recursion and iteration is that recursion is a process and always applies to a function. Iteration is applied to a series of instructions that are executed repeatedly.

Iterative method:

The iterative method is the simplest way to calculate the length of a linked list. The iterative method simply uses a counter with an initial value of zero. Now use iterations to trace the linked list to the last node and increment the counter on each iteration.

Steps:

  • Initialize the counter to zero.
  • Initialize the node pointer with the head pointer pTmpNode = head.
  • Crawl the linked list until you no longer get a null pointer.
  • pTmpNode = pTmpNode-> pNextNode
  • Increase the counter with each iteration. iCounter ++.

For example:

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

linked list

linked list

linked list

linked list

Here Code:

#include <stdio.h>
#include <stdlib.h>
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));
          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;  
                   count++;              
          }
          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 method:

You can also use the recursive method to find the length of the linked list. Here, each recursive call reduces the number of nodes and increases the counter.

In general, the iterative method of calculating the length of the list was preferred. The recursive method uses stack memory for calculations, so if the linked list is too large, you may face a stack overflow scenario.

Steps:

  • Returns 0 if the header is NULL.
  • Otherwise, it returns 1 + GetAndPrintTheList (pNode-> pNextNode).

For example:

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

linked list

linked list

linked list

linked list

Here Code:

#include <stdio.h>
#include <stdlib.h>
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));
          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;
}

Conclusion:

In this article, you will learn how to calculate the length of a linked list using an iterative and recursive method. Recursive functions are easy to write, but they don’t perform well compared to iteration. Iterative, on the other hand, are difficult to write, but they work better than recursion.

Recommended Articles:

  1. How to split a circular linked list into two halves?
  2. How to swap nodes in a linked list without Swapping data?
  3. How to write C functions that modify head pointer of a Linked List?
  4. A Programmer’s approach of looking at Array vs. Linked List
  5. Differences between Arrays and Linked Lists?

References:

Help Me Please: If you found any error in the content or example please let us know by comment also write your suggestion or if any doubt in the concept please feel free to write us in the comment section.

Practice your Code online here

(Visited 67 times, 1 visits today)

0 0 vote
Article Rating
Subscribe
Notify of
4 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
trackback

[…] Find Length of a Linked List (Iterative and Recursive)? […]

trackback

[…] Find Length of a Linked List (Iterative and Recursive)? […]

trackback

[…] Find Length of a Linked List (Iterative and Recursive)? […]

trackback

[…] Find Length of a Linked List (Iterative and Recursive)? […]

You cannot copy content of this page
Scroll Up
4
0
Would love your thoughts, please comment.x
()
x

  • Name

  • Minimum length of 8 characters.