Finding Length of Linked List

The length (number of nodes) of a singly linked list is found by walking from head and incrementing a counter until cur becomes NULL. You must visit every node—O(n) time and O(1) extra space for an empty list head == NULL returns length 0.

C program (return int count)

The list is built with insert_begin as in insert at beginning. The length function only reads the list. main prints the list, prints the length, then frees with free_list.

• length(NULL) is 0 (the while loop never runs).
• Same traversal pattern as search and print_list, but you count instead of comparing or printing.

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

struct Node {
    int data;
    struct Node *next;
};

struct Node *insert_begin(struct Node *head, int data)
{
    struct Node *newNode = malloc(sizeof(struct Node));
    if (newNode == NULL)
        return head;

    newNode->data = data;
    newNode->next = head;
    return newNode;
}

int length(struct Node *head)
{
    int count = 0;
    struct Node *cur = head;
    while (cur != NULL) {
        count++;
        cur = cur->next;
    }
    return count;
}

void print_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void free_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        struct Node *next = cur->next;
        free(cur);
        cur = next;
    }
}

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

    head = insert_begin(head, 30);
    head = insert_begin(head, 20);
    head = insert_begin(head, 10);

    print_list(head);   /* 10 20 30 */

    printf("length = %d\n", length(head));

    free_list(head);
    return 0;
}

Program output

Overall program flow

Each iteration inside length (one call, list 10 20 30)

Start: head = 0x3000. Counter count starts at 0.

Iteration 1 (cur at 0x3000, data 10)

Iteration 2 (cur at 0x2000, data 20)

Iteration 3 (cur at 0x1000, data 30)

Return count (3).

Memory layout (example addresses)

List in heap (same as insert_begin example)

Visual representation

head (0x3000)
   │
   ▼
┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ data: 10     │    │ data: 20     │    │ data: 30     │
│ next: 0x2000 ┼───→│ next: 0x1000 ┼───→│ next: NULL   │
└──────────────┘    └──────────────┘    └──────────────┘
     n1                   n2                   n3
  (inserted last)     (inserted 2nd)      (inserted first)

Detailed step-by-step: iteration 2 of length

Inside the while when cur is 0x2000 and count is 1 (about to count the second node):

Complexity summary

The key takeaway is that length is a full traversal: you cannot know how many nodes exist without walking the list (unless you maintain a separate size field updated on every insert/delete).

Alternative: store size in a list wrapper struct; or recursive length with O(n) call stack space.