Doubly Linked Lists
Arrows both ways.
In a doubly linked list, every node points to the next node and to the previous one. It uses a little more memory, but you can walk in both directions, and remove any node you're holding in O of one.

- Next and previous
- Walk both ways
- Remove a node in O(1)
A node with two arrows
Each node now has prev and next. To remove a node, its neighbours simply point at each other, and that takes O of one, with no searching. Here we link A, B, and C, then remove B. Run it. Walking forwards and backwards both skip B now.
class Node:
def __init__(self, value):
self.value, self.prev, self.next = value, None, None
a, b, c = Node("A"), Node("B"), Node("C")
a.next, b.prev, b.next, c.prev = b, a, c, b
b.prev.next = b.next
b.next.prev = b.prev
print(a.value, a.next.value)
print(c.value, c.prev.value)A C C A
Which list when?
Here's how to choose. Python's list is best for most work, with fast indexing. Deque is best for adding and removing at both ends. A singly linked list is simple, and good for stacks and interview questions. A doubly linked list shines when you must remove items from the middle quickly, like in a least recently used cache.
| Structure | Best for |
|---|---|
| list | indexing, most everyday work |
| deque | fast at both ends |
| singly linked | simple chains, interviews |
| doubly linked | O(1) removal anywhere, LRU caches |
Summary
A doubly linked list has arrows both ways, so removing a node is O of one. Next, a new section. Recursion, when a function calls itself.
Key takeaways- prev and next
- O(1) removal
- Used in LRU caches