3.2 Doubly Linked Lists

A doubly linked list is a sequence of nodes where each node stores a value, a reference to the next node, and a reference to the previous node. Compared with a singly linked list, it gives bidirectional movement, but every structural update must preserve two links instead of one.

Structure

A minimal node definition is:

Node {
  value
  prev : Node | null
  next : Node | null
}

The list usually stores both head and tail.

List {
  head : Node | null
  tail : Node | null
}

If the list is empty, both head and tail are null. If the list has one node, both head and tail point to that same node.

Core Invariant

For every node x in the list:

if x.next != null:
  x.next.prev == x

if x.prev != null:
  x.prev.next == x

The head node has no previous node.

head.prev == null

The tail node has no next node.

tail.next == null

These conditions define the structural correctness of a doubly linked list. Most bugs come from updating one direction and forgetting the other.

Traversal

Forward traversal starts at head.

cur = head
while cur != null:
  process(cur.value)
  cur = cur.next

Backward traversal starts at tail.

cur = tail
while cur != null:
  process(cur.value)
  cur = cur.prev

Both traversals take O(n) time and O(1) extra space.

Insert After a Node

To insert new after cur, preserve the old successor before rewiring.

after = cur.next

new.prev = cur
new.next = after

cur.next = new

if after != null:
  after.prev = new
else:
  tail = new

The order matters. First connect the new node to its neighbors. Then connect the neighbors back to the new node. If cur was the tail, the list tail must be updated.

Insert Before a Node

To insert new before cur, preserve the old predecessor.

before = cur.prev

new.next = cur
new.prev = before

cur.prev = new

if before != null:
  before.next = new
else:
  head = new

If cur was the head, the list head must be updated.

Delete a Node

Deletion is simpler than in a singly linked list because the node already stores its predecessor.

before = cur.prev
after = cur.next

if before != null:
  before.next = after
else:
  head = after

if after != null:
  after.prev = before
else:
  tail = before

After deletion, it is often useful to detach the removed node.

cur.prev = null
cur.next = null

Detaching prevents accidental reuse of stale links, especially in languages where nodes may be moved between lists.

Push Front

Insert a node at the beginning.

new.prev = null
new.next = head

if head != null:
  head.prev = new
else:
  tail = new

head = new

When the old list is empty, the new node is both head and tail.

Push Back

Insert a node at the end.

new.next = null
new.prev = tail

if tail != null:
  tail.next = new
else:
  head = new

tail = new

Again, the empty list case must update both endpoints.

Pop Front

Remove and return the first node.

if head == null:
  return null

node = head
head = head.next

if head != null:
  head.prev = null
else:
  tail = null

node.next = null
node.prev = null
return node

The important edge case is a one-node list. After removing that node, both head and tail must become null.

Pop Back

Remove and return the last node.

if tail == null:
  return null

node = tail
tail = tail.prev

if tail != null:
  tail.next = null
else:
  head = null

node.next = null
node.prev = null
return node

This is symmetric to pop_front.

Complexity Summary

Common Failure Modes

A doubly linked list fails when the two directions disagree. For example, a.next = b but b.prev != a describes a broken structure. Such a list may appear correct when traversed forward but fail when traversed backward.

The common bugs are forgetting to update head, forgetting to update tail, failing to handle the one-node case, deleting a node twice, and leaving stale prev or next pointers attached to a removed node.

Use Cases

Doubly linked lists are useful when deletion of a known node must be O(1), or when the algorithm needs movement in both directions. They appear in LRU caches, browser history, undo systems, intrusive containers, and schedulers.

The cost is extra memory and more update rules. Each node stores one additional pointer, and each insertion or deletion must preserve both forward and backward reachability.