Find the length of a linked list using recursion

In this tutorial, we will learn how to write a recursive function to find the length of a linked list using the C program? By Piyas Mukherjee Last updated : August 02, 2023

Solution

Recursive function: func_length(node *temp)

Input

A singly linked list whose address of the first node is stored in a pointer, say head.

Output

Length of the link list

Data Structure Used

Singly linked list where each node contains a data element say data, and the address of the immediate next node say next, with head holding the address of the first node.

Steps:

Declare a global variable l=0

Pseudo Code

Begin
    If(temp=NULL)
        print l //printing final length
    Else
        l=l+1;
        length(temp->next); //recursive call
    End If-else
End

C program to find the length of a linked list using recursion

#include <stdio.h>
#include <stdlib.h>

typedef struct list {
    int data;
    struct list* next;
} node;

//global variable to store length
int l = 0;

//recursive function to find length
int length(node* temp)
{
    if (temp == NULL)
        return l;
    else {
        l = l + 1;
        length(temp->next);
    }
}

// Main code
int main()
{
    node *head = NULL, *temp, *temp1;
    int len, choice, count = 0, key;
    
    //building the link list
    do {
        temp = (node*)malloc(sizeof(node));
        if (temp != NULL) {
            printf("\nEnter the element in the list : ");
            scanf("%d", &temp->data);
            temp->next = NULL;
            if (head == NULL) {
                head = temp;
            }
            else {
                temp1 = head;
                while (temp1->next != NULL) {
                    temp1 = temp1->next;
                }
                temp1->next = temp;
            }
        }
        else {
            printf("\nMemory not avilable...node allocation is not possible");
        }
        printf("\nIf you wish to add m ore data on the list enter 1 : ");
        scanf("%d", &choice);
    } while (choice == 1);

    len = length(head);
    printf("The list has a total of %d no of nodes", l);

    return 0;
}

Output

Enter the element in the list : 1

If you wish to add m ore data on the list enter 1 : 1

Enter the element in the list : 2

If you wish to add m ore data on the list enter 1 : 1

Enter the element in the list : 3

If you wish to add m ore data on the list enter 1 : 1

Enter the element in the list : 4

If you wish to add m ore data on the list enter 1 : 1

Enter the element in the list : 5

If you wish to add m ore data on the list enter 1 : 1

Enter the element in the list : 6

If you wish to add m ore data on the list enter 1 : 0
The list has atotal of 6 no of nodes