FundamentalsData structureaka DLL, two-way list, bidirectional list

Doubly Linked List

A linked list whose nodes carry both prev and next pointers, so any node can be removed in O(1) given just its reference and the list can be walked in both directions.

▶ Visualize Pattern: Hashing Practice (3)

Progress

Definition

A doubly linked list extends the Singly Linked List with a prev pointer on every node. That single addition changes what is possible: deleting a node no longer requires walking to its predecessor, moving a node to the front is O(1), and iteration can run backwards from the tail.

This is the structure behind LRU Cache (hash map to node + O(1) unlink and move-to-front), Deque implementations, java.util.LinkedList, std::list, Go's container/list, and Python's OrderedDict internals.

The price is one more pointer per node (typically 8 bytes) and slightly more bookkeeping on every edit — four pointer writes instead of two — but with two sentinel nodes (dummy head and dummy tail) every insert/delete becomes the same unconditional code path.

prev pointerbidirectionalO(1) delete by nodesentinelsLRUdeque

Intuition

A mental model before the formal terms.

A train where each carriage is coupled on both sides. Standing on any carriage, you can uncouple it from both neighbours and reconnect them to each other without walking to the front. That is exactly what a cache needs: "this item was just used — pull it out from wherever it is and put it at the front."

Sentinels are like permanent buffer carriages at both ends: real carriages are always inserted between two existing ones, so there is never a "first" or "last" special case.

How it works

Node: { value, prev, next }. List: head and tail sentinels with head.next = tail, tail.prev = head; real nodes live between them.
insertAfter(node, v): new.prev = node; new.next = node.next; node.next.prev = new; node.next = new.
remove(node): node.prev.next = node.next; node.next.prev = node.prev. No traversal, no predecessor search.
pushFront(v) = insertAfter(head, v); pushBack(v) = insertAfter(tail.prev, v); popFront() = remove(head.next); popBack() = remove(tail.prev).
moveToFront(node): remove(node) then insertAfter(head, node) — the LRU "touch" operation.
Traversal: forward from head.next until tail, backward from tail.prev until head.

Why it works

With both neighbours reachable from the node itself, unlinking is a purely local operation: rewrite the two pointers that referenced the node and it is gone, in constant time.

Sentinels guarantee node.prev and node.next are never null for a real node, so remove and insertAfter need no conditionals and cannot dereference null.

Combined with a Hash Map from key to node, the list gives O(1) lookup and O(1) reordering — neither structure alone can provide both.

Operations

Operation	Description	Cost
pushFront(v) / pushBack(v)	Insert next to the head or tail sentinel.	O(1)
popFront() / popBack()	Remove the node adjacent to a sentinel.	O(1)
insertAfter(node, v) / insertBefore(node, v)	Four pointer writes around an existing node.	O(1)
remove(node)	Unlink using `prev` and `next` — no predecessor search.	O(1)
moveToFront(node)	`remove` then `insertAfter(head)`; the LRU touch.	O(1)
get(i)	Walk from the nearer end.	O(n)
search(v)	Linear scan in either direction.	O(n)

Recognition

How to tell a problem wants this.

A cache or "recently used" ordering that must evict from one end and promote arbitrary items in O(1).
You need O(1) push/pop at both ends (a Deque) plus O(1) removal from the middle by reference.
The problem needs backward traversal or "previous node" access (browser history, text editor cursor).

“have you seen this before” → Hashing “reverse a linked list” → Linked List Manipulation

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Singly Linked List visualization.

Commands — Comma separated: append N, prepend N, insert N at I, delete N, reverse

empty list

1/30Start with an empty list: head = null. Each node stores a value and a single `next` pointer, so traversal is one-directional.

VisitingInsertedRemovedMatch

PseudocodeLearn Singly Linked List →

1append(v): walk to the tail; tail.next = Node(v)
2prepend(v): node = Node(v); node.next = head; head = node
3insert(v, i): walk to node i-1; node.next = prev.next; prev.next = node
4delete(v): walk until curr.value == v; prev.next = curr.next
5reverse(): prev = null; curr = head
6  while curr: next = curr.next; curr.next = prev; prev = curr; curr = next
7  head = prev

Variables

size0

Complexity

access O(n)

search O(n)

insert O(1)

delete O(1)

Speed

Pseudocode

1class Node: value, prev, next
2class DoublyLinkedList:
3  head = Node(sentinel); tail = Node(sentinel)
4  head.next = tail; tail.prev = head; size = 0
5  insertAfter(node, v):
6    n = Node(v); n.prev = node; n.next = node.next
7    node.next.prev = n; node.next = n; size++
8  remove(node):
9    node.prev.next = node.next; node.next.prev = node.prev; size--
10  pushFront(v): insertAfter(head, v)
11  pushBack(v): insertAfter(tail.prev, v)
12  popFront(): remove(head.next)
13  popBack(): remove(tail.prev)
14  moveToFront(node): remove(node); relink node after head

Implementation

1from typing import Generic, Optional, TypeVar
2 
3T = TypeVar("T")
4 
5 
61 · Node with prev/next and two sentinels
7class DNode(Generic[T]):
8    __slots__ = ("value", "prev", "next")
9 
10    def __init__(self, value: Optional[T] = None) -> None:
11        self.value = value
12        self.prev: Optional[DNode[T]] = None
13        self.next: Optional[DNode[T]] = None
14 
15 
16class DoublyLinkedList(Generic[T]):
17    def __init__(self) -> None:
18        self.head: DNode[T] = DNode()  # sentinel before the first element
19        self.tail: DNode[T] = DNode()  # sentinel after the last element
20        self.head.next = self.tail
21        self.tail.prev = self.head
22        self._n = 0
23 
24    def __len__(self) -> int:
25        return self._n
26 
27    def is_empty(self) -> bool:
28        return self._n == 0
29 
302 · Insert after a node (the one primitive)
31    def insert_after(self, node: DNode[T], v: T) -> DNode[T]:
32        fresh: DNode[T] = DNode(v)
33        after = node.next
34        assert after is not None  # tail sentinel ends the chain
35        fresh.prev, fresh.next = node, after
36        after.prev = fresh
37        node.next = fresh
38        self._n += 1
39        return fresh
40 
413 · Unlink a node in O(1)
42    def remove(self, node: DNode[T]) -> T:
43        if node is self.head or node is self.tail:
44            raise ValueError("cannot remove sentinel")
45        prev, nxt = node.prev, node.next
46        assert prev is not None and nxt is not None
47        prev.next, nxt.prev = nxt, prev
48        node.prev = node.next = None
49        self._n -= 1
50        return node.value  # type: ignore[return-value]
51 
524 · End operations expressed via the primitives
53    def push_front(self, v: T) -> DNode[T]:
54        return self.insert_after(self.head, v)
55 
56    def push_back(self, v: T) -> DNode[T]:
57        assert self.tail.prev is not None
58        return self.insert_after(self.tail.prev, v)
59 
60    def pop_front(self) -> T:
61        if self.is_empty():
62            raise IndexError("pop from empty list")
63        return self.remove(self.head.next)  # type: ignore[arg-type]
64 
65    def pop_back(self) -> T:
66        if self.is_empty():
67            raise IndexError("pop from empty list")
68        return self.remove(self.tail.prev)  # type: ignore[arg-type]
69 
705 · Move an existing node to the front (LRU idiom)
71    def move_to_front(self, node: DNode[T]) -> None:
72        prev, nxt = node.prev, node.next
73        assert prev is not None and nxt is not None
74        prev.next, nxt.prev = nxt, prev
75        first = self.head.next
76        assert first is not None
77        node.prev, node.next = self.head, first
78        first.prev = node
79        self.head.next = node

Walkthrough

DNode with __slots__ keeps nodes compact; sentinels are created with value=None.
insert_after wires the four links; assert after is not None documents the sentinel invariant for type checkers.
remove swaps neighbours in one tuple assignment, clears the node's links and returns the value.
push_*/pop_* delegate to the primitives; is_empty guards the pops with a clear IndexError.
move_to_front unlinks and relinks in O(1) — the LRU hit path.

Complexity (this implementation)

time O(1) all listed operations · space O(n)

Each node is a Python object with three slots (~64 bytes); collections.deque and OrderedDict implement the same idea in C.

Language notes

collections.OrderedDict with move_to_end(key) and popitem(last=False) is the standard LRU building block — it is a doubly linked list plus a dict.
collections.deque is a doubly linked list of fixed-size blocks: O(1) at both ends, O(n) in the middle.
Use is to compare against sentinels — identity, not ==.

Common mistakes in this language

Forgetting to clear node.prev/node.next after removal and later walking from a stale node.
Comparing nodes with == when value defines __eq__.
Removing a sentinel in a while loop that pops until head.next is tail.

Language differences that matter here

Standard library: C++ std::list (with O(1) splice); Python OrderedDict/deque cover the LRU and deque uses; JS/TS have none, though Map preserves insertion order.
Node handles: C++ returns raw pointers that dangle after delete; JS/TS/Python handles stay valid objects but are detached from the list.
Null typing: TypeScript needs casts or a non-null sentinel design; Python type checkers need assert ... is not None; JS and C++ compile without either.
Copy semantics: copying the C++ class needs rule-of-five care; JS/Python objects are shared by reference.

Complexity

Operation	Average	Worst	Note
Access	O(n)	O(n)	O(1) at either end.
Search	O(n)	O(n)
Insert	O(1)	O(1)	Before or after any known node.
Delete	O(1)	O(1)	Any node by reference — no predecessor needed.
Update	O(n)	O(n)	O(1) once located.
Push / Pop both ends	O(1)	O(1)
Move to front	O(1)	O(1)
Reverse traversal	O(n)	O(n)
Space	O(n)		Two pointers per node plus two sentinels.

Advantages & disadvantages

Advantages

O(1) deletion and relocation of any node given its reference.
O(1) operations at both ends — a complete Deque.
Bidirectional traversal; can walk from whichever end is closer.
Sentinels make the code branch-free and null-safe.

Disadvantages

Two pointers per node: roughly 16 bytes of overhead on 64-bit systems, plus allocation cost.
Still O(n) indexed access and search; no cache locality.
More pointer updates per operation than a singly linked list — easier to get subtly wrong.

Use cases

LRU Cache and LFU Cache: hash map to node + move-to-front + evict from tail.
Deques and queues with O(1) operations at both ends.
Undo/redo stacks, browser history, media playlists with previous/next navigation.
Ordered dictionaries that preserve insertion order with O(1) delete (OrderedDict, LinkedHashMap).
Free lists and intrusive lists in kernels and allocators where nodes are embedded in larger objects.

Use it when

You must delete or relocate nodes given only a reference (LRU/LFU caches, schedulers).
You need a deque with O(1) at both ends and no resize spikes.
Backward iteration or "previous item" navigation is required.

Avoid it when

Memory per element matters and you only ever move forward — a Singly Linked List halves the pointer overhead.
You need random access or cache-friendly scans — use a Dynamic Array or ring-buffer Deque.
The only ends-based operations are push/pop at the back — a Dynamic Array suffices.

Alternatives

Singly Linked List Deque Dynamic Array Circular Linked List

Common mistakes

Updating only next (or only prev) on insert/delete, leaving the list inconsistent in one direction.
Not using sentinels and then mishandling empty-list, single-node, head and tail cases.
Forgetting to clear a removed node's pointers, keeping neighbours alive (memory leak) or allowing a double remove.
In an LRU cache, updating the map but not the list (or vice versa) so lookups return stale or detached nodes.
Writing the four pointer assignments in an order that overwrites node.next before reading it.

Interview patterns

LRU cache: HashMap<key, node> + DLL; get moves to front, put evicts tail.prev.
LFU cache: DLL per frequency bucket with O(1) promotion between buckets.
Design a browser history / text editor with O(1) back and forward.
Flatten a multilevel doubly linked list; convert a BST to a sorted DLL in place.
Implement deque operations for sliding window maximum (Monotonic Queue).

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Hash map or array?Beginner
Array versus linked listBeginner

Mock interviews

Two SumBeginner
Longest Substring Without Repeating CharactersIntermediate
Subarray Sum Equals KIntermediate

Interview problems

Sliding Window Maximumhard Reverse Linked Listeasy LRU Cachemedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related