C Linked List: Create, Traverse, Free

A linked list is a chain of nodes — each node holds a value and a pointer to the next. The first node is the head; the last node's next is NULL. Dynamically grows with each malloc.

Linked lists are the canonical introduction to dynamic data structures in C. Each node lives on the heap; pointers link them together; you traverse by following next from the head.

The basic shape

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

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

Node *create_node(int value) {
  Node *n = malloc(sizeof(Node));
  n->data = value;
  n->next = NULL;
  return n;
}

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

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

int main() {
  Node *head = create_node(10);
  head->next = create_node(20);
  head->next->next = create_node(30);

  print_list(head);   // 10 -> 20 -> 30 -> NULL

  Node *new_head = create_node(5);
  new_head->next = head;
  head = new_head;

  print_list(head);   // 5 -> 10 -> 20 -> 30 -> NULL

  free_list(head);
  return 0;
}

The Node struct

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

Each node has:

• data — the payload (here, an int).
• next — pointer to the next node, or NULL for the last.

The named-typedef form (struct Node plus Node) is needed because the field references its own type before the typedef is complete.

create_node — heap allocation

Node *create_node(int value) {
  Node *n = malloc(sizeof(Node));
  n->data = value;
  n->next = NULL;
  return n;
}

Allocate one node on the heap. Fill in the fields. Return the pointer. Caller becomes responsible for freeing.

For production code, check malloc:

Node *create_node(int value) {
  Node *n = malloc(sizeof(Node));
  if (n == NULL) return NULL;
  n->data = value;
  n->next = NULL;
  return n;
}

Linking nodes together

Node *head = create_node(10);
head->next = create_node(20);
head->next->next = create_node(30);

Visualised:

head -> [10|*] -> [20|*] -> [30|NULL]

Each node points to the next; the last points to NULL.

For cleaner construction, build a builder function:

Node *make_list_from(int *values, int n) {
  if (n == 0) return NULL;
  Node *head = create_node(values[0]);
  Node *tail = head;
  for (int i = 1; i < n; i++) {
    tail->next = create_node(values[i]);
    tail = tail->next;
  }
  return head;
}

print_list — traversal

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

Walk from the head, following next until NULL. Standard linked-list traversal.

The current pointer marches through the list; head itself is never modified, so the caller's pointer stays put.

free_list — release every node

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

The trick: save current->next before freeing current. Otherwise current = current->next after free(current) is undefined.

For each node:

1. Save current to temp.
2. Advance current to current->next.
3. Free temp.

Repeat until current is NULL.

Prepending (insert at head)

Node *new_head = create_node(5);
new_head->next = head;
head = new_head;

Three steps:

1. Make new node.
2. Point its next at the old head.
3. Update head to the new node.

This is O(1) — fast, regardless of list size.

For a function that does this:

Node *prepend(Node *head, int value) {
  Node *n = create_node(value);
  n->next = head;
  return n;
}

head = prepend(head, 5);

Returns the new head; the caller reassigns. (Or use a Node **head parameter to modify in place — episode 29.)

Linked list vs array

Lists are great for "frequently insert at front" and "size unknown in advance." Arrays are better for "iterate or random-access a known sequence."

For most general-purpose lists, dynamic arrays (episode 56) win on cache locality.

Why linked lists in C

C lists are educational — they teach pointer manipulation and dynamic memory. They're also useful for:

• Insertion-heavy workloads where order doesn't matter.
• Building "free lists" for memory pools.
• Implementing other structures (queues, stacks, graphs).
• Kernel data structures (Linux uses doubly-linked lists everywhere).

For everyday "list of things," modern code prefers dynamic arrays.

Common mistakes

Forgetting next = NULL on creation. The new node's next is garbage; traversal walks into random memory.

Memory leak on free. Forget to walk the whole list, you leave nodes allocated.

Use after free. Walk a list and free as you go without saving next first.

Modifying head without returning it. A function that prepends to head modifies a local copy unless it takes Node **.

Cycles. If two next pointers form a cycle, traversal runs forever and free runs into freed memory.

Pointer to local in node. Node *n = &local_node; head->next = n; — n dies when its scope ends. Always allocate nodes on the heap.

What's next

Episode 43: insert and delete. More sophisticated operations — insert at end, delete by value.

Recap

Linked list: nodes with data and next * chained until NULL. create_node allocates one on the heap. Traverse by following next from head. Free in order: save next, free current, advance. Prepending is O(1); random access is O(n). Compared to arrays: better for head-insert-heavy workloads; worse for cache and random access. Lists teach pointer manipulation; for production work, dynamic arrays often win.

Next episode: insert and delete.