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):
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):
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.
References:
- https://www.tutorialspoint.com/find-length-of-a-linked-list-iterative-and-recursive-in-cplusplus
- https://www.journaldev.com/30153/find-length-of-a-linked-list
- https://www.faceprep.in/data-structures/find-length-of-a-linked-list-iterative-and-recursive/
- https://www.codespeedy.com/find-length-of-a-linked-list-recursive-in-cpp/
