{ } LinearIntermediate interactive
Doubly Linked List
Two-way pointers for O(1) backward traversal.
doubly_linked_list
4 nodes
headnull
7⇄
13⇄
4⇄
21⇄
Each node links both ways — delete in O(1) without searching for the predecessor.
tap ✕ to delete
How it works
Each node carries both a next and a prev pointer, so you can walk the list in either direction and delete a node in O(1) given only a reference to it. This is the backbone of LRU caches and browser history.
Mental models
- Deleting a node needs no predecessor search — prev is already there.
- Sentinel head and tail nodes remove almost every boundary check.
Complexity
- Access
- O(n)
- Insert
- O(1)given the node
- Delete
- O(1)given the node
- Traverse back
- O(1) per step
- Space
- O(n)extra pointer per node
Reach for it when
- LRU caches
- Undo/redo & browser history
- Music playlists