C Linked List: Traverse, Count, Search

count_nodes walks until NULL. search walks until match. get_at walks N steps. The three "read-only" operations on a linked list — all O(n).

After insert and delete, the read operations: count, find by value, get by position. All variations on the same theme — walk the list while testing.

The basic shape

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

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

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

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

int search(Node *head, int value) {
  Node *c = head;
  int index = 0;
  while (c != NULL) {
    if (c->data == value) return index;
    index++;
    c = c->next;
  }
  return -1;
}

int get_at(Node *head, int index) {
  Node *c = head;
  for (int i = 0; i < index && c != NULL; i++) {
    c = c->next;
  }
  if (c != NULL) return c->data;
  return -1;
}

count_nodes

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

Walk until NULL, increment a counter. O(n).

For a list with a tracked size, you'd cache size in a wrapper struct and avoid the walk:

typedef struct {
  Node *head;
  int size;
} List;

// Update size on every insert/delete.
// Now: int count(List *l) { return l->size; } — O(1)

For pure linked lists (no wrapper), counting is O(n).

search by value

int search(Node *head, int value) {
  Node *c = head;
  int index = 0;
  while (c != NULL) {
    if (c->data == value) return index;
    index++;
    c = c->next;
  }
  return -1;
}

Walk until match or end. Return the position (0-based) of the first match, or -1 if not found.

To return the matching node instead:

Node *find(Node *head, int value) {
  Node *c = head;
  while (c != NULL) {
    if (c->data == value) return c;
    c = c->next;
  }
  return NULL;
}

Pointer return is more useful for "find and update" — you have the node directly.

get_at by index

int get_at(Node *head, int index) {
  Node *c = head;
  for (int i = 0; i < index && c != NULL; i++) {
    c = c->next;
  }
  if (c != NULL) return c->data;
  return -1;
}

Walk index steps from head. Return the data, or -1 if out of range.

For "give me a node pointer at index N":

Node *node_at(Node *head, int index) {
  Node *c = head;
  for (int i = 0; i < index && c != NULL; i++) {
    c = c->next;
  }
  return c;
}

NULL if out of range.

get_at is O(n) — random access is slow

Compared to arrays where arr[i] is O(1), get_at is O(n). Walking from head every time defeats the purpose of "indexing."

For workloads with frequent index access, use an array — even a dynamic array (episode 56). Linked lists are not the right tool.

Last node and middle node

Node *last(Node *head) {
  if (head == NULL) return NULL;
  Node *c = head;
  while (c->next != NULL) c = c->next;
  return c;
}

Node *middle(Node *head) {
  Node *slow = head;
  Node *fast = head;
  while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
  }
  return slow;
}

last is straightforward. middle uses the two-pointer technique — when fast reaches the end, slow is in the middle. Same trick used for cycle detection (episode 43).

For "Nth from the end":

Node *nth_from_end(Node *head, int n) {
  Node *fast = head;
  for (int i = 0; i < n && fast != NULL; i++) {
    fast = fast->next;
  }
  if (fast == NULL) return NULL;

  Node *slow = head;
  while (fast->next != NULL) {
    slow = slow->next;
    fast = fast->next;
  }
  return slow;
}

Two pointers n apart; advance both until fast hits the end. Slow is at "Nth from end." One pass.

Sum and other reductions

int sum(Node *head) {
  int total = 0;
  Node *c = head;
  while (c != NULL) {
    total += c->data;
    c = c->next;
  }
  return total;
}

int max(Node *head) {
  if (head == NULL) return INT_MIN;
  int m = head->data;
  Node *c = head->next;
  while (c != NULL) {
    if (c->data > m) m = c->data;
    c = c->next;
  }
  return m;
}

Same walk-and-track pattern. For functional-style code, you'd write a reduce helper that takes a function pointer:

int reduce(Node *head, int (*fn)(int, int), int initial) {
  int acc = initial;
  Node *c = head;
  while (c != NULL) {
    acc = fn(acc, c->data);
    c = c->next;
  }
  return acc;
}

int add(int a, int b) { return a + b; }
int sum = reduce(list, add, 0);

Function-pointer machinery from episode 27.

Reversing a list

Node *reverse(Node *head) {
  Node *prev = NULL;
  Node *current = head;
  while (current != NULL) {
    Node *next = current->next;
    current->next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

Walk the list, redirecting each next pointer backward. The original head ends up at the tail (with next = NULL). The new head is what was previously the tail.

O(n) time, O(1) extra space — in-place.

Recursive traversal

void print_recursive(Node *head) {
  if (head == NULL) {
    printf("NULL\n");
    return;
  }
  printf("%d -> ", head->data);
  print_recursive(head->next);
}

Each call prints one node and recurses on next. Cleaner code, but uses stack frames per node — for huge lists, stack overflow.

For traversal, prefer iterative.

For naturally recursive operations (in-order traversal of a tree), recursion is fine.

Common mistakes

Walking past NULL. c->data when c == NULL crashes. Always check.

Off-by-one in get_at. Walking index steps lands on head for index 0, head->next for index 1, etc. Standard "0-based" indexing.

Index returned vs node returned. Pick a convention. search returns int index; find returns a Node*. Each has uses; they're different functions.

Cycles cause infinite walks. Pre-check with Floyd's algorithm if cycles are possible.

Modifying during traversal. Don't insert or delete while walking — current pointer becomes stale.

What's next

Episode 45: doubly linked lists. Each node has prev and next. Lets you traverse backward and delete in O(1) given a node pointer.

Recap

Linked-list reads: walk and test. count_nodes returns the length. search finds by value (position or pointer). get_at walks N steps to a position. All O(n). Two-pointer technique (slow + fast) for "middle" and "Nth from end." reduce for fold-style operations. Recursion is shorter but uses stack space — prefer iteration for long lists.

Next episode: doubly linked lists.