Find Length of a Linked List (Iterative and Recursive) | DSA in C++ - Software Development PDF Download

Introduction

Iterative Approach

The iterative approach involves traversing the linked list from the head node to the tail node and counting the number of nodes encountered.

Code Example

#include <iostream>

struct Node {

    int data;

    Node* next;

};

int getLengthIterative(Node* head) {

    int length = 0;

    Node* current = head;    

    while (current != nullptr) {

        length++;

        current = current->next;

    }    

    return length;

}

int main() {

    // Create a sample linked list: 1 -> 2 -> 3 -> nullptr

    Node* head = new Node{1, nullptr};

    head->next = new Node{2, nullptr};

    head->next->next = new Node{3, nullptr};    

    int length = getLengthIterative(head);

    std::cout << "Length of the linked list: " << length << std::endl;   

    return 0;

}

Explanation

• We define a struct 'Node' to represent each node in the linked list. Each node contains an integer data value and a pointer to the next node.
• The function 'getLengthIterative' takes the head node of the linked list as an argument and returns the length of the list.
• We initialize the 'length' variable to 0 and create a pointer 'current' to keep track of the current node being processed.
• We iterate through the linked list by advancing the 'current' pointer to the next node until it reaches the end (i.e., becomes 'nullptr').
• In each iteration, we increment the 'length' variable to count the number of nodes encountered.
• Finally, we return the computed 'length'.

Code Output

Length of the linked list: 3

Recursive Approach

The recursive approach involves calling a recursive function on the next node and adding 1 to the result until reaching the end of the linked list.

Code Example

#include <iostream>

struct Node {

    int data;

    Node* next;

};

int getLengthRecursive(Node* node) {

    if (node == nullptr)

        return 0;

    else

        return 1 + getLengthRecursive(node->next);

}

int main() {

    // Create a sample linked list: 1 -> 2 -> 3 -> nullptr

    Node* head = new Node{1, nullptr};

    head->next = new Node{2, nullptr};

    head->next->next = new Node{3, nullptr};    

    int length = getLengthRecursive(head);

    std::cout << "Length of the linked list: " << length << std::endl;    

    return 0;

}

Explanation

• The function 'getLengthRecursive' takes a node as an argument and returns the length of the linked list starting from that node.
• If the node is 'nullptr', i.e., the end of the linked list is reached, we return 0 to terminate the recursion.
• Otherwise, we recursively call 'getLengthRecursive' on the next node ('node->next') and add 1 to the result.
• The recursion continues until we reach the end of the linked list, and the lengths are accumulated and returned.

Code Output

Length of the linked list: 3

Sample Problems

Problem 1: Write a function to find the length of a singly linked list with a recursive approach.

int getLengthRecursive(Node* node) {

    if (node == nullptr)

        return 0;

    else

        return 1 + getLengthRecursive(node->next);

}

Problem 2: Write a function to find the length of a singly linked list with an iterative approach.

int getLengthIterative(Node* head) {

    int length = 0;

    Node* current = head;    

    while (current != nullptr) {

        length++;

        current = current->next;

    }    

    return length;

}

Conclusion

In this article, we discussed two approaches to find the length of a linked list: iterative and recursive. We provided easy-to-understand code examples, explanations, and code outputs for each approach. By understanding these concepts, you can efficiently determine the length of a linked list in your C++ programs. Remember to choose the approach that best suits your needs and the requirements of your application.