Find length of a linked list ( Recursive) in C++

Hi there. Today we are going to see how to find the length of a linked list using recursion in C++. Mainly there are two methods for it. Iterative method and recursive method. We are going to implement the recursion based method.

Each time the function calls itself, we increment the count value by 1. Because whenever the function calls itself, it means a node is present next to the current node whose next pointer is not null. When we find the null pointer, we return 0. In the end, it returns the total count. Now, let’s look at the programming part.

Finding length of linked list using recursion C++

We will take the required input in the main function. Then we will create the function for counting the length, which is equal to the total number of nodes in the linked list. In our function, we first pass the head pointer as a parameter. Then, we recursively run it by passing each node’s next pointer to the function, until that pointer is found to be null for the last node.

Let’s take a look at the code.

#include<bits/stdc++.h>
using namespace std;

struct Node{
  int data;
  struct Node *next;
  Node(int x){
    data=x;
    next=NULL;
  }
};

void append(struct Node** head_ref,struct Node** tail_ref,int new_data)
{
  struct Node* new_node =new Node(new_data);
  if(*head_ref==NULL)
    *head_ref=new_node;
  else
    (*tail_ref)->next=new_node;
  *tail_ref=new_node;
}
  
int Count(struct Node* head) 
{ 
    if (head == NULL)
    {
    	return 0;
  }    
    return(1+Count(head->next)); 
} 

int main() 
{ 
    struct Node* head = NULL,*tail=NULL; 
  	cout<<"Enter the number of elements"<<endl;
    int n,temp;
    cin>>n;
    cout<<"Enter each element separated by space"<<endl;
    for(int i=1;i<=n;i++)
    {
    	cin>>temp;
    	append(&head,&tail,temp);
  }
  
    cout<<endl<<"Number of nodes is: "<<Count(head);
    return 0; 
}
Now, let's look at the output.

Enter the number of elements
10
Enter each element separated by space
1 2 3 4 5 5 4 3 2 1

Number of nodes is: 10

I hope you found this article helpful. For your further practice, try to implement this program using iteration. Or try to perform search operations using recursion or iteration.  These topics will further enhance your understanding.

Also read: Convert a Singly Linked List to an Array in C++

Leave a Reply

Your email address will not be published. Required fields are marked *