Doubly linked list

A doubly linked list is a Linked list where each node has two pointers — next (forward to the next node) and prev (backward to the previous node). This lets you traverse in both directions, at the cost of one extra pointer per node.

typedef struct node {
    int           value;
    struct node  *next;   // forward link
    struct node  *prev;   // backward link
} node;
 
node *head;   // first node
node *tail;   // last node

The list typically maintains both a head (first node) and tail (last node) pointer for O(1) operations at either end.

Why have prev pointers

Three things become much cheaper compared to a singly linked list:

1. Backward traversal. Walk from tail to head, in reverse order, by following prev pointers.
2. Delete a given node. With only next, deleting a node requires the previous node — you’d typically search for it from the head. With prev, the previous node is one pointer away (node->prev), so deletion is O(1) given the node.
3. Insert before a given node. Same logic — prev is right there.

The cost: one extra pointer per node (8 bytes on a 64-bit system) and the maintenance burden of keeping both directions consistent on every insert/delete.

Comparison with singly linked list

Operation	Singly	Doubly
Insert at head	O(1)	O(1)
Insert at tail (with tail pointer)	O(1)	O(1)
Delete given node (have pointer to it)	O(n) — find previous	O(1)
Backward traversal (in place, no aux memory)	O(n²)	O(n)
Memory per node	1 pointer	2 pointers

Doubly linked lists win when you need to delete arbitrary nodes given pointers to them (typical in OS process tables) or when bidirectional traversal is required.

Real-world examples

• Browser history — going back and forward through pages.
• Music playlist — next track, previous track.
• Undo/redo stacks — but typically two separate stacks instead.
• OS process lists — quickly remove a process from the run queue without scanning.

For the operation patterns common to deques (which usually use doubly linked lists internally), see Deque.