A doubly linked list gives every node two pointers instead of one: next to the node on its right and prev to the node on its left. That second pointer is what makes deletion and "step backward" cheap — you never have to scan from the head to find what came before. A circular linked list closes the loop so the tail links back to the head, which is handy for round-robins and ring buffers.
Core idea. Each node stores val, prev, and next. To splice a new node in between two neighbors
you rewire exactly four pointers; to splice one out you rewire exactly two. No element ever moves
in memory — only pointers change — so both operations are O(1) once you hold the node. For
10 <-> 20 <-> 30 <-> 40, inserting 25 after 20 gives 10 <-> 20 <-> 25 <-> 30 <-> 40.
In a singly linked list you can only move forward, and deleting a node means walking from the head to find its predecessor. The prev pointer removes that scan. The price is one extra pointer of memory per node and the discipline of keeping both directions consistent on every edit.
Intuition
Picture a row of train cars coupled on both ends. The forward coupling is next; the backward coupling is prev. To add a car in the middle you don't shove every other car down the track — you just unhook the two couplings between the neighbors and hook the new car to each side. Four hooks, done. To remove a car, the two neighbors reach past it and couple directly: two hooks.
A circular list is the same train bent into a loop: the last car couples to the first. Walking next forever cycles through the list instead of hitting a None terminator — which is exactly what you want for something like a CPU scheduler cycling through processes.
Walk through it
Step through the animation on the right. The four nodes 10, 20, 30, 40 each show two arcs to each neighbor: a next arc on top and a prev arc on the bottom. First watch the circular step add a next link from the tail (40) back to the head (10) and a prev link the other way — the loop closes.
Then watch the insert. A new node 25 fades in below the gap between 20 and 30. Four links wire up one at a time: x.prev to 20, then x.next to 30, then 30.prev over to x, then 20.next over to x. As the last two land, the old 20 <-> 30 arcs retire — 25 is now fully spliced in.
Finally watch the delete. We rewire only two links: 20.next jumps straight to 30, and 30.prev jumps straight back to 20. Nothing references 25 anymore, so it disappears. The list is back to four nodes, and every edit was O(1).
The code, line by line
class Node:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
def insert_after(node, val):
x = Node(val)
x.prev = node # new.prev -> left
x.next = node.next # new.next -> right
node.next.prev = x # right.prev -> new
node.next = x # left.next -> new
def delete(node):
node.prev.next = node.next # left.next -> right
node.next.prev = node.prev # right.prev -> leftNodecarries three fields: the value plus bothprevandnext, each starting asNone.- In
insert_after, line 9 points the new node back at the left neighbor, and line 10 points it forward at the right neighbor (node.next). The new node is now joined to both sides. - Order matters. Line 11 sets
node.next.prev = xbefore line 12 overwritesnode.next. If you flipped these two lines,node.nextwould already bexand you would setx.prev = x— corrupting the list. deleteneeds no search: the node already knows its neighbors. Line 15 makes the left neighbor skip forward to the right one; line 16 makes the right neighbor skip back to the left one. The deleted node is now unreferenced.
Complexity
| Case | Time | Notes |
|---|---|---|
| Insert / delete (have the node) | O(1) (fast) | a fixed number of pointer writes, no shifting |
| Search by value | O(n) (moderate) | still must walk the chain to find a node |
| Step backward | O(1) (fast) | follow prev — impossible in a singly linked list |
O(n) (moderate)The win over an array is structural: inserting or deleting in the middle of an array is O(n) because every later element shifts, while here it is O(1) once you hold the node. The win over a singly linked list is the prev pointer — it makes deletion and backward traversal O(1) instead of needing a scan from the head. The cost is one extra pointer per node.
When to use / pitfalls
Reach for a doubly linked list when you need O(1) removal of a node you already hold, or O(1) moves at both ends — this is the backbone of an LRU cache (hash map to node, doubly linked list for recency order) and of a deque. Reach for the circular variant for round-robin scheduling, ring buffers, or any "wrap around to the start" loop. A sentinel / dummy head-tail node removes most null-edge cases.
Two classic bugs. First, rewire order: in insert_after, touch node.next.prev before you
overwrite node.next, or you lose the reference to the right neighbor. Second, in a circular list
a naive while node: loop never terminates — there is no None end — so iterate a fixed count or stop
when you return to the node you started from. Also remember to update both directions on every edit:
a forgotten prev write leaves the list walkable forward but broken backward.
Practice
To insert a node between two existing nodes in a doubly linked list, how many pointers must you rewire, and how many to delete a node you already hold?
1. What does the prev pointer give a doubly linked list that a singly linked list lacks?
2. How many pointers are rewired to insert one node between two existing nodes?
3. In insert_after, why must node.next.prev = x run before node.next = x?
4. Why can a naive while loop walking next forever fail on a circular linked list?