Get Length of Linked List in DSA C

Mental Model

Count how many nodes are in the linked list by moving from the start to the end one by one.

Analogy: Like counting people standing in a line by walking from the first person to the last and counting each one.

head -> [1] -> [2] -> [3] -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null

Goal: Find how many nodes are in the list

Step 1: start at head node with value 1

head -> [1 ↑] -> [2] -> [3] -> null

Why: We begin counting from the first node

Step 2: move to next node with value 2, count = 2

head -> [1] -> [2 ↑] -> [3] -> null

Why: Count each node as we move forward

Step 3: move to next node with value 3, count = 3

head -> [1] -> [2] -> [3 ↑] -> null

Why: Continue counting nodes

Step 4: next node is null, stop counting

head -> [1] -> [2] -> [3] -> null ↑

Why: Reached end of list, total count is final

Result:

head -> [1] -> [2] -> [3] -> null
Length = 3

Annotated Code

DSA C

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

// Define node structure
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to get length of linked list
int getLength(struct Node* head) {
    int count = 0;
    struct Node* current = head;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

int main() {
    // Create linked list 1 -> 2 -> 3 -> null
    struct Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);

    int length = getLength(head);
    printf("Length = %d\n", length);
    return 0;
}

while (current != NULL) {

loop through each node until end of list

count++;

increment count for each node visited

current = current->next;

advance to next node to continue counting

Output

Length = 3

Complexity Analysis

Time: O(n) because we visit each of the n nodes once to count them

Space: O(1) because we only use a few variables regardless of list size

vs Alternative: This is optimal; no simpler way than visiting each node once to count

Edge Cases

empty list (head is NULL)

function returns 0 because there are no nodes

DSA C

while (current != NULL) {

single node list

function returns 1 counting the single node

DSA C

while (current != NULL) {

When to Use This Pattern

When you need to find how many items are in a linked list, use a simple traversal counting each node until you reach the end.

Common Mistakes

Mistake: Forgetting to move to the next node inside the loop, causing an infinite loop
Fix: Add 'current = current->next;' inside the while loop to advance the pointer

Mistake: Initializing count incorrectly or outside the function
Fix: Initialize count to zero inside the function before counting

Summary

Counts the number of nodes in a linked list by traversing it.

Use when you need to know the size of a linked list.

The key is to move through each node one by one and count them.