Doubly Linked List

A doubly linked list stores prev and next. This makes insertions and deletions $O(1)$ once the node is known, as the predecessor can be accessed without searching.

Costs: more memory and more invariants (keeping both directions consistent). Sentinels at the head and tail are helpful.

java.util.LinkedList is doubly linked and suitable for frequent insertion/deletion operations at both ends.

Where used

LRU caches (nodes are moved to the front upon access), deques, browser history, text editor rope variants. $O(1)$ removal at a known node is the core reason for double linking.

Depth

Each node has references to both its predecessor and successor. For adjacent nodes, the invariant is that the forward and backward references correspond to each other. Modifications must update both directions.

If a node is already known, it can be removed locally without needing to find its predecessor. However, index access remains linear. A stored end reference also allows for constant insertion and deletion at the back end.

Sentinels at both ends reduce special cases. Empty and non-empty states then use the same four reference updates, while the sentinels themselves never represent user data.

Difficulty levels

1. Check forward and backward invariants.
2. Safely remove a known inner node.
3. Weigh sentinel nodes against explicit edge case handling.

Pitfalls

Updating only one direction creates a structure that is correct in one pass and appears corrupted in the reverse pass. Removed nodes should also be detached from their neighbors.