Doubly Linked Lists
A doubly linked list (DLL) is a sequence of nodes where every node stores a value plus two links: a prev pointer to the node before it and a next pointer to the node after it. That second link is the whole point: it lets you walk the list backward as easily as forward, and it lets you unlink a node in O(1) time once you already hold a reference to it, without walking the list to find its predecessor. Doubly linked lists show up under the hood of browser back/forward history, undo-redo stacks, LRU caches, and Python’s own collections.deque.
Overview: How a Doubly Linked List Works
A singly linked list only knows how to go forward: each node has a next pointer, and to find the node before a given one you have to start at the head and walk until you find it, which costs O(n). A doubly linked list fixes this by giving every node a second pointer, prev, that points back at its predecessor. The list itself typically keeps two references: head (the first node) and tail (the last node), so you can append or prepend in O(1) without scanning.
Picture a list holding 10, 20, 30. Node 20 points forward to node 30 via next and backward to node 10 via prev. The head node’s prev is None and the tail node’s next is None — those are your boundary markers, and forgetting to check for them is where almost every doubly linked list bug comes from.
The key advantage over a singly linked list is O(1) deletion given a node reference. To remove a node from a singly linked list you need its predecessor (to rewrite that predecessor’s next), and finding the predecessor means scanning from the head — O(n). In a doubly linked list, the node you want to delete already carries a pointer straight to its predecessor via prev, so unlinking is four pointer reassignments, done in constant time. This is precisely why real data structures like LRU caches (which need to move an arbitrary node to the front instantly) and text editor undo stacks are built on doubly linked lists rather than singly linked ones.
The tradeoff is memory: every node carries two pointers instead of one, so a doubly linked list uses roughly double the pointer overhead of a singly linked list holding the same values. For most real workloads that constant-factor cost is worth it for the backward traversal and O(1) deletion it buys you.
Time and Space Complexity
Let n be the number of nodes in the list. Complexity assumes the list maintains both a head and a tail pointer, which is standard practice.
| Operation | Time Complexity | Why |
|---|---|---|
| Access by index / search by value | O(n) | No random access — you must walk node by node from head or tail until you find the target. |
| Insert at head | O(1) | The head pointer gives direct access to the front; no traversal needed. |
| Insert at tail | O(1) | The tail pointer gives direct access to the back — this is the operation a plain singly linked list (without a tail pointer) cannot do in O(1). |
| Delete a node given a direct reference to it | O(1) | The node already has prev, so you don’t need to search for its predecessor — you can relink both neighbors immediately. |
| Delete by value | O(n) | Dominated by the O(n) search to find the matching node; the unlink step itself is O(1) once found. |
Space complexity is O(n) for n nodes. Each node stores one value and two references (prev and next), so the constant factor is larger than a singly linked list’s single-pointer nodes, but the asymptotic space class is the same: linear in the number of elements.
Examples
Example 1: Building a Doubly Linked List and Traversing Both Directions
This example implements a minimal DoublyLinkedList with append, prepend, and two print helpers that walk the list forward from head and backward from tail.
class Node:
def __init__(self, data: int) -> None:
self.data = data
self.prev: "Node | None" = None
self.next: "Node | None" = None
class DoublyLinkedList:
def __init__(self) -> None:
self.head: "Node | None" = None
self.tail: "Node | None" = None
self.size = 0
def append(self, data: int) -> None:
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
self.size += 1
def prepend(self, data: int) -> None:
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.size += 1
def print_forward(self) -> None:
values = []
current = self.head
while current is not None:
values.append(str(current.data))
current = current.next
print(" <-> ".join(values))
def print_backward(self) -> None:
values = []
current = self.tail
while current is not None:
values.append(str(current.data))
current = current.prev
print(" <-> ".join(values))
def main() -> None:
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)
dll.prepend(5)
print("Forward:", end=" ")
dll.print_forward()
print("Backward:", end=" ")
dll.print_backward()
print("Size:", dll.size)
if __name__ == "__main__":
main()Output:
Forward: 5 <-> 10 <-> 20 <-> 30
Backward: 30 <-> 20 <-> 10 <-> 5
Size: 4Tracing it: three append calls build 10 <-> 20 <-> 30 by chaining each new node onto tail and moving tail forward. Then prepend(5) links the new node’s next to the old head, points the old head’s prev back at it, and moves head. The result is 5 <-> 10 <-> 20 <-> 30. Walking backward from tail simply reverses the same chain, which is only possible because every node kept a prev pointer.
Example 2: Deleting from the Head, Tail, and Middle
Deletion is where a doubly linked list earns its keep. This example deletes by value from three different positions and shows a lookup for a missing value.
class Node:
def __init__(self, data: int) -> None:
self.data = data
self.prev: "Node | None" = None
self.next: "Node | None" = None
class DoublyLinkedList:
def __init__(self) -> None:
self.head: "Node | None" = None
self.tail: "Node | None" = None
def append(self, data: int) -> None:
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
def delete(self, data: int) -> bool:
current = self.head
while current is not None:
if current.data == data:
if current.prev is not None:
current.prev.next = current.next
else:
self.head = current.next
if current.next is not None:
current.next.prev = current.prev
else:
self.tail = current.prev
return True
current = current.next
return False
def to_list(self) -> list[int]:
values = []
current = self.head
while current is not None:
values.append(current.data)
current = current.next
return values
def main() -> None:
dll = DoublyLinkedList()
for value in [1, 2, 3, 4, 5]:
dll.append(value)
print("Before:", dll.to_list())
dll.delete(1)
print("After deleting head (1):", dll.to_list())
dll.delete(5)
print("After deleting tail (5):", dll.to_list())
dll.delete(3)
print("After deleting middle (3):", dll.to_list())
found = dll.delete(99)
print("Deleting missing value 99 returns:", found)
if __name__ == "__main__":
main()Output:
Before: [1, 2, 3, 4, 5]
After deleting head (1): [2, 3, 4, 5]
After deleting tail (5): [2, 3, 4]
After deleting middle (3): [2, 4]
Deleting missing value 99 returns: FalseDeleting the head (1) hits the current.prev is None branch, so self.head is reassigned to current.next (node 2), and node 2‘s prev is cleared. Deleting the tail (5) is the mirror case: self.tail moves to current.prev (node 4). Deleting the middle (3) touches neither head nor tail — it simply splices node 2‘s next and node 4‘s prev together, skipping over node 3 entirely. Deleting 99 walks the whole list, finds no match, and returns False.
Example 3: A Realistic Use Case — Browser History
Doubly linked lists are a natural fit whenever you need a cursor that can move both forward and backward through a sequence, like browser history. Here a current pointer tracks the active page, and visiting a new page after going back discards the old forward history — exactly like a real browser.
class HistoryNode:
def __init__(self, url: str) -> None:
self.url = url
self.prev: "HistoryNode | None" = None
self.next: "HistoryNode | None" = None
class BrowserHistory:
def __init__(self, homepage: str) -> None:
self.current = HistoryNode(homepage)
def visit(self, url: str) -> None:
new_node = HistoryNode(url)
new_node.prev = self.current
self.current.next = new_node
self.current = new_node
def back(self, steps: int) -> str:
while steps > 0 and self.current.prev is not None:
self.current = self.current.prev
steps -= 1
return self.current.url
def forward(self, steps: int) -> str:
while steps > 0 and self.current.next is not None:
self.current = self.current.next
steps -= 1
return self.current.url
def main() -> None:
history = BrowserHistory("home.com")
history.visit("docs.com")
history.visit("python.org")
history.visit("github.com")
print(history.back(1))
print(history.back(2))
print(history.forward(1))
history.visit("stackoverflow.com")
print(history.forward(5))
print(history.back(10))
if __name__ == "__main__":
main()Output:
python.org
home.com
docs.com
stackoverflow.com
home.comAfter three visits the chain is home.com <-> docs.com <-> python.org <-> github.com with current at github.com. back(1) moves to python.org. back(2) moves two steps further to home.com (stopping there because prev is None). forward(1) moves to docs.com. Then visit("stackoverflow.com") is called from docs.com, which overwrites docs.com‘s next pointer — the old forward path to python.org and github.com is now unreachable, just like a real browser losing forward history after you navigate somewhere new. forward(5) has nowhere to go (stackoverflow.com’s next is None) so it stays put, and back(10) walks back to home.com and stops.
How It Works Step by Step
Trace building 10 <-> 20 <-> 30, inserting 15 between 10 and 20, then deleting 20:
1. Start empty: head = None, tail = None.
2. Append 10: list is empty, so head = tail = Node(10).
3. Append 20: Node(10).next = Node(20), Node(20).prev = Node(10), tail = Node(20). List: 10 <-> 20.
4. Append 30: same pattern — tail becomes Node(30). List: 10 <-> 20 <-> 30.
5. Insert 15 after node 10: create Node(15). Set Node(15).prev = Node(10) and Node(15).next = Node(10).next (which is Node(20)) before overwriting anything. Then set Node(20).prev = Node(15), and finally Node(10).next = Node(15). List: 10 <-> 15 <-> 20 <-> 30.
6. Delete node 20: its neighbors are 15 and 30. Set Node(15).next = Node(30) and Node(30).prev = Node(15). Node 20 is now unreferenced. List: 10 <-> 15 <-> 30.
Step 5 is the reason insertion order matters: if you overwrote Node(10).next before reading it to set Node(15).next, you’d lose the pointer to Node(20) and corrupt the list. Always capture the pointers you still need before you reassign anything.
Common Mistakes
Mistake 1: Updating Only One Direction of the Link
The single most common doubly linked list bug is updating next without updating the matching prev (or vice versa). It’s easy to do because the forward-only version looks correct and even passes forward-traversal tests.
def append_broken(self, data: int) -> None:
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node # BUG: new_node.prev is never set
self.tail = new_nodeThis links tail.next to the new node, so forward traversal (print_forward) looks fine. But new_node.prev is left as None, so backward traversal from tail stops after a single step, and any future deletion of the new node will think it’s the head. The fix is to set both pointers together:
def append_fixed(self, data: int) -> None:
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_nodeMistake 2: Forgetting Boundary Checks on Both Ends
A singly linked list only has one edge to worry about (the head, since there’s no prev). A doubly linked list has two, and code that only handles one will crash the moment you delete the head or the tail.
def remove_all_broken(self, data: int) -> None:
current = self.head
while current is not None:
if current.data == data:
current.prev.next = current.next # crashes if current is head
current.next.prev = current.prev # crashes if current is tail
current = current.nextIf the matching node is the head, current.prev is None, and None.next raises AttributeError. If it’s the tail, current.next is None, and the second line fails the same way. The corrected version checks both sides independently and updates self.head / self.tail when a boundary is hit, mirroring the delete method from Example 2:
def remove_all_fixed(self, data: int) -> None:
current = self.head
while current is not None:
next_node = current.next
if current.data == data:
if current.prev is not None:
current.prev.next = current.next
else:
self.head = current.next
if current.next is not None:
current.next.prev = current.prev
else:
self.tail = current.prev
current = next_nodeNote the next_node = current.next saved before any mutation — a defensive habit worth keeping any time you unlink a node while a loop is mid-traversal, since it removes any doubt about whether the pointer you’re about to follow is still trustworthy.
Best Practices
- Always update
prevandnexttogether as a pair — never write code that sets one without the other in the same operation. - Keep an explicit
tailpointer if you need O(1) appends and backward traversal; without it you lose the main advantage of a doubly linked list. - When deleting, explicitly check both
current.prev is None(you’re at the head) andcurrent.next is None(you’re at the tail) — don’t assume a node has a neighbor on either side. - Reach for a doubly linked list when you need O(1) deletion given a node reference (LRU caches, undo/redo, browser history) or bidirectional traversal — not just because you need a generic sequence, where a plain
listis usually faster and simpler. - In real Python code, use
collections.dequefor a general-purpose double-ended queue — it’s a doubly linked list under the hood, already optimized in C. Build your ownNode-based version, as this lesson does, specifically to understand whatdequeis doing for you and for interview problems that require full control over node references (like LRU cache implementations). - Draw the pointers on paper (or a whiteboard) before coding a tricky insert or delete — doubly linked list bugs are almost always pointer-order mistakes that are obvious once drawn out but easy to miss in code.
Practice Exercises
- Exercise 1 — Reverse in place: Write a function that reverses a doubly linked list by swapping
prevandnexton every node (and swappinghead/tail), without allocating any new nodes. For input1 <-> 2 <-> 3, the result should traverse forward as3 <-> 2 <-> 1. - Exercise 2 — Detect a palindrome: Given a doubly linked list of integers, write a function that returns
Trueif the sequence reads the same forward and backward, using two pointers that start atheadandtailand move toward each other. Test it on1 <-> 2 <-> 3 <-> 2 <-> 1(expected:True) and1 <-> 2 <-> 3(expected:False). - Exercise 3 — Design an LRU cache: Using a doubly linked list plus a dictionary mapping keys to nodes, implement a fixed-capacity cache with O(1)
getandput, where every access moves the node to the front and, on overflow, the tail (least recently used) node is evicted. This is a very common interview question and is the canonical real-world reason doubly linked lists exist.
Summary
- A doubly linked list stores
prevandnextpointers on every node, enabling traversal and O(1) deletion given a node reference in both directions. - Access and search are O(n); insertion or deletion at a known head, tail, or node reference is O(1); deletion by value is O(n) overall because of the search.
- Space is O(n), with roughly double the per-node pointer overhead of a singly linked list.
- The classic bugs are updating only one of the two pointers per operation, and forgetting to special-case the head and tail boundaries where
prevornextisNone. - Reach for a doubly linked list when you need bidirectional traversal or O(1) removal of an arbitrary node you already hold a reference to — browser history, undo/redo, and LRU caches are the textbook examples.
