Find Length of a Linked List (using Loop and Recursion)

• Write a C program to find length of linked list using loop.
• C program to count the number of nodes in a linked list using recursion.

Length of a linked list is the total number of nodes in a linked list. Here we will find length of linked list using both iterative and recursive approach.

Linked List : 2 --> 4 --> 5 --> 8 --> 11
Length : 5

---

Find length of linked list using loop

Algorithm to count number of nodes in Linked list using for loop.

• Initialize an integer variable "length" to 0.
• Using a for loop, traverse linked list from head node till last node.
• In every iteration, increment the value of length.
• Return length.

---

#include <stdio.h>
#include <stdlib.h>
 
/* A structure of linked list node */
struct node {
  int data;
  struct node *next;
} *head;

void initialize(){
    head = NULL;
}

/* 
Given a Inserts a node in front of a singly linked list. 
*/
void insert(int num) {
    /* Create a new Linked List node */
    struct node* newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data  = num;
    /* Next pointer of new node will point to head node of linked list  */
    newNode->next = head;
    /* make new node as new head of linked list */
    head = newNode;
    printf("Inserted Element : %d\n", num);
}

int getLength(struct node *head){
    int length =0;
    while(head != NULL){
        head = head->next;
        length++;
    }
    return length;
}
/*
Prints a linked list from head node till tail node 
*/
void printLinkedList(struct node *nodePtr) {
  while (nodePtr != NULL) {
     printf("%d", nodePtr->data);
     nodePtr = nodePtr->next;
     if(nodePtr != NULL)
         printf("-->");
  }
}
 
int main() {
    initialize();
    /* Creating a linked List*/
    insert(8);  
    insert(3); 
    insert(2); 
    insert(7);
    insert(9);
    printf("\nLinked List\n");
    printLinkedList(head);
    printf("\nLinked List Length : %d", getLength(head));
    return 0;
}

Output

Inserted Element : 8
Inserted Element : 3
Inserted Element : 2
Inserted Element : 7
Inserted Element : 9

Linked List
8-->3-->2-->7-->9
Linked List Length : 5

---

Find length of linked list using recursion

Recursive algorithm to find length of linked list
Let the prototype of recursive function be "int getLength(struct node *head)"

• Recursive equation : getLength(head) = 1 + getLength(head->next);
• Recursion termination condition : if(head == NULL) return 0;

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

#include <stdio.h>
#include <stdlib.h>
 
/* A structure of linked list node */
struct node {
  int data;
  struct node *next;
} *head;

void initialize(){
    head = NULL;
}

/* 
Given a Inserts a node in front of a singly linked list. 
*/
void insert(int num) {
    /* Create a new Linked List node */
    struct node* newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data  = num;
    /* Next pointer of new node will point to head node of linked list  */
    newNode->next = head;
    /* make new node as new head of linked list */
    head = newNode;
    printf("Inserted Element : %d\n", num);
}

/*
Recursive function to calculate length of Linked list
getLength(head) =  1 + getLength(head->next);
*/
int getLength(struct node *head){
    if (head == NULL)
        return 0;
    return 1 + getLength(head->next);
 
}
/*
Prints a linked list from head node till tail node 
*/
void printLinkedList(struct node *nodePtr) {
  while (nodePtr != NULL) {
     printf("%d", nodePtr->data);
     nodePtr = nodePtr->next;
     if(nodePtr != NULL)
         printf("-->");
  }
}
 
int main() {
    initialize();
    /* Creating a linked List*/
    insert(8);  
    insert(3); 
    insert(2); 
    insert(7);
    insert(9);
    printf("\nLinked List\n");
    printLinkedList(head);
    printf("\nLinked List Length : %d", getLength(head));
    return 0;
}

Output

Inserted Element : 8
Inserted Element : 3
Inserted Element : 2
Inserted Element : 7
Inserted Element : 9

Linked List
8-->3-->2-->7-->9
Linked List Length : 5