# 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:

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

The list usually stores both `head` and `tail`.

```text
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:

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

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

The `head` node has no previous node.

```text
head.prev == null
```

The `tail` node has no next node.

```text
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`.

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

Backward traversal starts at `tail`.

```text
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.

```text
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.

```text
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.

```text
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.

```text
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.

```text
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.

```text
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.

```text
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.

```text
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

| Operation                | Time | Space |
| ------------------------ | ---: | ----: |
| Forward traversal        | O(n) |  O(1) |
| Backward traversal       | O(n) |  O(1) |
| Insert before known node | O(1) |  O(1) |
| Insert after known node  | O(1) |  O(1) |
| Delete known node        | O(1) |  O(1) |
| Push front               | O(1) |  O(1) |
| Push back                | O(1) |  O(1) |
| Search by value          | O(n) |  O(1) |

## 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.