C in 100 Seconds: Doubly Linked List

Doubly Linked List

A doubly linked list adds a prev pointer to each node. You can walk forward or backward, and deleting from the middle is cleaner because you can reach both neighbors.

The Node Struct

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

Two pointers instead of one. prev points backward, next points forward.

Traverse Both Directions

// Forward: follow next
while (c != NULL) { c = c->next; }

// Backward: follow prev
while (c != NULL) { c = c->prev; }

Insert at Head

Node *insert_head(Node *head, int value) {
  Node *n = create_node(value);
  n->next = head;
  if (head != NULL) head->prev = n;
  return n;
}

The extra step: after linking n->next to head, also set head->prev to n. Both directions must be wired.

Delete by Value

if (c->prev != NULL) c->prev->next = c->next;
else head = c->next;
if (c->next != NULL) c->next->prev = c->prev;
free(c);

Two rewires: the previous node skips forward, the next node skips backward. Then free the target.

Student Code

Try it yourself: episode45/doubly.c