C Program to Find the Length of a Linked List

Introduction

The length of a linked list refers to the number of nodes present in the list. To find the length, you need to traverse the entire list from the head to the last node, counting each node as you go.

Example:

• Input: A linked list with nodes containing [10, 20, 30, 40].
• Output: The length of the linked list is 4.

Problem Statement

Create a C program that:

• Creates a singly linked list.
• Calculates the length of the linked list.
• Displays the length of the linked list.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output functions and dynamic memory allocation.
2. Define the Node Structure: Create a structure for the node containing an integer data part and a pointer to the next node.
3. Implement the Function to Find the Length of the Linked List: Write a function that traverses the linked list and counts the number of nodes.
4. Implement the Function to Insert a Node at the End of the Linked List: Write a function to insert nodes at the end of the linked list.
5. Create a Main Function: In the main() function, create the linked list, calculate its length, and display the result.

C Program to Find the Length of a Linked List

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

// Step 2: Define the Node Structure
struct Node {
    int data;
    struct Node* next;
};

// Function to find the length of the linked list
int getLength(struct Node* head) {
    int count = 0;
    struct Node* current = head;

    while (current != NULL) {
        count++;
        current = current->next;
    }

    return count;
}

// Function to insert a node at the end of the linked list
void insertAtEnd(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head_ref;

    new_node->data = new_data;
    new_node->next = NULL;

    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

    while (last->next != NULL) {
        last = last->next;
    }

    last->next = new_node;
}

// Function to display the linked list
void displayList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    // Insert elements at the end
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);

    // Display the linked list
    printf("Linked List: ");
    displayList(head);

    // Find and display the length of the linked list
    int length = getLength(head);
    printf("Length of the linked list: %d\n", length);

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Step 2: Define the Node Structure

• The Node structure contains two members: an integer data to store the node’s data, and a pointer next to point to the next node in the list.

Function to Find the Length of the Linked List

• The getLength function takes a pointer to the head of the linked list and returns the number of nodes in the list.
• It uses a while loop to traverse the linked list, incrementing a count variable for each node encountered.
• The function returns the value of count, which represents the length of the linked list.

Function to Insert a Node at the End of the Linked List

• The insertAtEnd function takes a double pointer to the head of the linked list (head_ref) and the data to be inserted (new_data).
• A new node is allocated dynamically using malloc().
• If the linked list is empty, the new node becomes the head of the list.
• Otherwise, the function traverses the list to the last node and updates the last node’s next pointer to point to the new node.

Function to Display the Linked List

• The displayList function traverses the linked list from the head and prints each node’s data, followed by an arrow (->), until it reaches the end (NULL).

Main Function

• The main function creates a linked list by inserting nodes at the end using the insertAtEnd function.
• It then displays the linked list and calculates its length using the getLength function, displaying the result.

Output Example

Example Output:

Linked List: 10 -> 20 -> 30 -> 40 -> NULL
Length of the linked list: 4

Conclusion

This C program demonstrates how to find the length of a linked list. It covers basic concepts such as dynamic memory allocation, pointer manipulation, and linked list traversal, making it a useful example for beginners learning data structures in C programming.