Doubly linked list
easyIn a singly linked list you cannot delete a node you are standing on - you need its predecessor. A prev pointer removes that walk, which is why LRU caches and browser history use this structure.
O(1) insert/delete given the nodeWorst O(n) searchSpace O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How doubly linked list works
In a singly linked list, deleting a node you are already holding still costs a walk - repairing the chain needs the predecessor, and only a walk from the head finds it. A doubly linked list stores a prev pointer alongside next, so the predecessor is one hop away. Deletion given the node becomes two writes: node.prev.next = node.next and node.next.prev = node.prev.
That single capability is why the structure exists. An LRU cache must yank a node out of the middle of its recency list on every access; browser history moves you backwards as easily as forwards. Both need O(1) unlinking of an arbitrary node, which only the back pointer provides.
The price is measured in bytes and bookkeeping. Two pointers per node instead of one - 8 extra bytes per element on a 64-bit machine, often more than the data itself - and every insert or delete now maintains links in both directions, doubling the chances of leaving one dangling.
Step by step
- Start with 12, 37, 5, 84 linked in both directions. head points at 12; the tail node 84 has a null next.
- insertHead(9): point 9's next at 12, set 12's prev to 9, move head. Three writes, still O(1).
- Suppose a hash map hands us the node holding 5 directly - no walk needed to find it.
- Unlink it: 37's next becomes 84 and 84's prev becomes 37. Two writes, zero traversal, and the node is gone.
- search(84) is unchanged: hop 9, 12, 37, then 84 - prev pointers add a direction, not a shortcut.
- Final list: 9, 12, 37, 84 - four nodes you can now walk from either end, which a singly linked list cannot offer.
Complexity
| Best case time | O(1) insert/delete given the node |
|---|---|
| Worst case time | O(n) search |
| Space | O(n) |
Reference implementation
Python
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def insert_head(self, v):
n = Node(v)
n.next = self.head
if self.head:
self.head.prev = n
self.head = n # O(1)
def delete(self, node):
"""O(1) when you already hold the node - the whole point."""
if node.prev:
node.prev.next = node.next
else:
self.head = node.next
if node.next:
node.next.prev = node.prevJavaScript
class Node {
constructor(value) { this.value = value; this.next = null; this.prev = null; }
}
class LinkedList {
head = null;
insertHead(v) {
const n = new Node(v);
n.next = this.head;
if (this.head) this.head.prev = n;
this.head = n; // O(1)
}
search(v) {
let cur = this.head, i = 0;
while (cur) { // O(n) - no random access
if (cur.value === v) return i;
cur = cur.next; i++;
}
return -1;
}
}Worth noticing
The back pointer buys O(1) deletion
In a singly linked list you cannot delete a node you are standing on - you need its predecessor, which costs a walk from the head. A prev pointer removes that walk entirely, which is why LRU caches and browser history use doubly linked lists.
You pay a pointer per node for it
Two pointers per node instead of one. On a 64-bit machine that is 8 extra bytes for every element - often more than the data itself. Every structure choice is this kind of trade.
Common pitfalls
- Updating only one direction: fixing prev.next but forgetting next.prev leaves a corrupted chain that only surfaces when someone walks backwards.
- Null edge cases: deleting the head means there is no prev to repair, and deleting the tail means no next - both need explicit branches.
- Skipping head.prev = n on head insertion, so backward traversal stops at the old head and silently never reaches the new node.
- Paying the memory tax blindly: an extra pointer per node is dead weight if nothing ever walks backwards or deletes from the middle.
Where it is used
- The recency list inside an LRU cache, where every access moves a middle node to the front.
- Browser history - back and forward are one pointer hop each.
- Python's OrderedDict and Java's LinkedHashMap - hash maps threaded onto exactly this list.
- Playlists and undo systems where entries leave from the middle as easily as from the ends.
Frequently asked questions
What is the time complexity of a doubly linked list?
Insert and delete are O(1) when you already hold the node - a pointer repair on each side. Search is still O(n) worst case, since prev pointers add a direction but no shortcuts. Space is O(n), with two pointers stored per node instead of one.
Why use a doubly linked list instead of a singly linked list?
For O(1) deletion of a node you are standing on. Singly linked deletion needs the predecessor, which costs a walk from the head. If some other structure - typically a hash map - hands you nodes directly, the prev pointer is what turns that into constant-time removal.
What is the main disadvantage of a doubly linked list?
Memory and maintenance. Each node carries a second pointer - 8 extra bytes per element on a 64-bit machine - and every mutation must keep both directions consistent. Miss one of the writes and the corruption often surfaces far from the bug, during some later backward traversal.
Where are doubly linked lists used in real systems?
LRU caches pair one with a hash map so eviction and move-to-front are both O(1). Python's OrderedDict and Java's LinkedHashMap are the same pairing built into the standard library. Browser history is the textbook example - back and forward each follow one pointer.