C Doubly Linked List: prev and next

Each node has prev and next. Traversal works in both directions. Deletion given a node pointer is O(1) — no need to find the predecessor.

A doubly linked list adds a prev pointer to each node. Costs more memory (one extra pointer per node) and slightly more complex inserts, but unlocks fast deletes and bidirectional iteration.

The basic shape

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

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

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

void print_forward(Node *head) {
  printf("Forward:  ");
  for (Node *c = head; c != NULL; c = c->next) {
    printf("%d <-> ", c->data);
  }
  printf("NULL\n");
}

void print_backward(Node *tail) {
  printf("Backward: ");
  for (Node *c = tail; c != NULL; c = c->prev) {
    printf("%d <-> ", c->data);
  }
  printf("NULL\n");
}

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

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

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

The Node struct

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

Two pointers per node instead of one. For each node:

• prev points to the previous node (or NULL for head).
• next points to the next node (or NULL for tail).

Memory cost: 8 bytes (pointer) extra per node on a 64-bit system. For lists of small payloads, that's overhead. For lists of large payloads, negligible.

Traversing both directions

// Forward
for (Node *c = head; c != NULL; c = c->next) ...

// Backward
for (Node *c = tail; c != NULL; c = c->prev) ...

Singly linked lists only support forward traversal. Doubly linked lets you walk back from any node — useful for "go to previous record" navigation, undo lists, etc.

insert_head

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

Two extra steps vs singly linked:

1. New node's next points to old head.
2. Old head's prev points to new node. (If old head exists.)
3. Return new node as the head.

Don't forget the old-head update — that's what makes prev correct for backward traversal.

delete_node — O(1) given a pointer

The big advantage of doubly linked lists: if you have a pointer to the node, you can delete it without walking from the head:

void delete_given_node(Node **head, Node *target) {
  if (target->prev != NULL) {
    target->prev->next = target->next;
  } else {
    *head = target->next;   // target was the head
  }
  if (target->next != NULL) {
    target->next->prev = target->prev;
  }
  free(target);
}

Update predecessor's next; update successor's prev; free the target. Each operation is O(1).

In a singly linked list, you'd have to walk from head to find the predecessor first — O(n).

Insert before / after a known node

void insert_after(Node *node, int value) {
  Node *n = create_node(value);
  n->prev = node;
  n->next = node->next;
  if (node->next != NULL) node->next->prev = n;
  node->next = n;
}

void insert_before(Node **head, Node *node, int value) {
  Node *n = create_node(value);
  n->next = node;
  n->prev = node->prev;
  if (node->prev != NULL) {
    node->prev->next = n;
  } else {
    *head = n;
  }
  node->prev = n;
}

Both O(1) given the node pointer. Splice in by updating four pointers.

Tail tracking

For O(1) tail operations, store both head and tail:

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

void insert_tail(List *l, int value) {
  Node *n = create_node(value);
  n->prev = l->tail;
  if (l->tail != NULL) l->tail->next = n;
  else l->head = n;
  l->tail = n;
  l->size++;
}

Now insert_head, insert_tail, delete_head, and delete_tail are all O(1).

Use cases

• Browser history. Forward and back navigation.
• Undo/redo. Move both directions through actions.
• LRU caches. Move recently-used items to the head; evict from tail.
• Text editors. Cursor moves backward and forward through a buffer.
• OS process lists. Linux kernel uses doubly linked lists pervasively.

Circular doubly linked list

A variation: tail's next is head, head's prev is tail. No NULL terminators.

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

// In a circular list, you can iterate from any node and end where you started.
void print_circular(Node *start) {
  Node *c = start;
  do {
    printf("%d -> ", c->data);
    c = c->next;
  } while (c != start);
}

Useful for round-robin scheduling, ring buffers as linked lists.

Comparison to singly linked

For most modern code, doubly linked is preferred — the small memory overhead is worth the simpler delete API.

Common mistakes

Forgetting to update prev. Insert sets next correctly but forgets to set the old head's prev. Backward traversal breaks.

Wrong prev/next ordering on splice. Update both directions when inserting or deleting. Four pointer updates per operation.

Memory leak on delete. Splicing alone doesn't free.

Tail pointer stale. Delete the tail but forget to update the tracker.

Head NULL after deleting last node. Remember to clear head when the list becomes empty.

What's next

Episode 46: stack — push, pop, peek. A LIFO structure built on an array (or linked list).

Recap

Doubly linked list: each node has prev and next. Forward and backward traversal. Insert is two extra pointer updates. Delete given a node pointer is O(1) — singly linked needs O(n) to find the predecessor. Memory: 2 pointers extra per node. With tracked head and tail, all four end-operations are O(1). For UI history, undo, LRU caches: doubly linked is the right shape.

Next episode: stack.