An Easy-To-Understand Guide For How To Find Length Of Linked List C

Oriana Fall

3 min read

·

28-02-2025

1

0

Share

Finding the length of a linked list is a fundamental operation in C programming. This guide will walk you through different approaches, explaining the concepts clearly and providing you with well-commented code examples. We'll cover both iterative and recursive methods, helping you choose the best approach for your specific needs.

Understanding Linked Lists

Before diving into length calculations, let's briefly revisit what a linked list is. A linked list is a linear data structure where elements are not stored at contiguous memory locations. Instead, each element, called a node, points to the next node in the sequence. The last node points to NULL, signifying the end of the list. Each node typically contains two parts:

• Data: The value stored in the node.
• Next: A pointer to the next node in the list.

Method 1: Iterative Approach

This is the most common and generally preferred method for finding the length of a linked list. It's efficient and easy to understand.

#include <stdio.h>

// Node structure definition
struct Node {
    int data;
    struct Node* next;
};

// Function to calculate the length of the linked list
int getLinkedListLength(struct Node* head) {
    int length = 0;
    struct Node* current = head; //Start at the head of the list

    //Iterate through the list until the end (NULL) is reached.
    while (current != NULL) {
        length++;
        current = current->next;
    }

    return length;
}


int main() {
    // Example usage:  Creating a sample linked list
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    // allocate 3 nodes in the heap
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    head->data = 1; //Assign data to each node
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL; //Mark the end of the list

    int listLength = getLinkedListLength(head);
    printf("The length of the linked list is: %d\n", listLength);

    //Remember to free allocated memory to prevent memory leaks!
    free(head);
    free(second);
    free(third);
    return 0;
}

Explanation:

1. We initialize a length variable to 0.
2. A current pointer is set to the head of the list.
3. The while loop continues as long as current is not NULL (i.e., we haven't reached the end of the list).
4. Inside the loop, we increment length and move current to the next node using current = current->next.
5. Finally, the function returns the calculated length.

Method 2: Recursive Approach

While less efficient than the iterative approach due to function call overhead, the recursive method offers a concise and elegant solution.

#include <stdio.h>

// Node structure (same as before)
struct Node {
    int data;
    struct Node* next;
};

// Recursive function to calculate the length
int getLinkedListLengthRecursive(struct Node* head) {
    if (head == NULL) {
        return 0; // Base case: empty list
    } else {
        return 1 + getLinkedListLengthRecursive(head->next); // Recursive call
    }
}

int main() {
    //Example usage (same as before, just change the function call)
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    int listLength = getLinkedListLengthRecursive(head);
    printf("The length of the linked list (recursive) is: %d\n", listLength);

    free(head);
    free(second);
    free(third);
    return 0;
}

Explanation:

1. The base case is when head is NULL (empty list), returning 0.
2. Otherwise, the function recursively calls itself with head->next, adding 1 to the result of the recursive call to account for the current node.

Choosing the Right Method

For most practical applications, the iterative approach is recommended due to its efficiency. The recursive approach, while elegant, can be less efficient for very large linked lists due to function call overhead and potential stack overflow issues. However, understanding both methods is crucial for a well-rounded understanding of linked list manipulation in C. Remember always to handle memory allocation and deallocation properly to avoid memory leaks.