Doubly Linked List

A singly linked list is like a treasure hunt where each clue only tells you where to go next. A doubly linked list is like a treasure hunt where each clue also tells you how to go back to where you came from.

Every node now carries three things: a value, a next pointer pointing to the node ahead, and a prev pointer pointing to the node behind. The list has both a head (front) and a tail (back), and you can traverse it in either direction.

What changes compared to singly linked?

The extra prev pointer unlocks two key improvements:

\(O(1)\) insert at tail — since you always know where the tail is, inserting there is just pointer updates, not a full traversal.
\(O(1)\) delete given the node — if you have a direct reference to a node, you can unlink it instantly. In a singly linked list, you'd need to find its predecessor first (\(O(n)\)) because you can't walk backwards.

Both of these come from the same root cause: you can now move backwards through the chain, so you never need to re-traverse from the head just to find a predecessor.

Doubly Linked List Operations

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = self.next = None

class DoublyLinkedList:
    def __init__(self): self.head = self.tail = None
    def push_front(self, v):
        n = Node(v)
        if not self.head: self.head = self.tail = n; return
        n.next = self.head; self.head.prev = n; self.head = n
    def push_back(self, v):
        n = Node(v)
        if not self.tail: self.head = self.tail = n; return
        n.prev = self.tail; self.tail.next = n; self.tail = n
    def pop_front(self):
        if not self.head: return None
        v = self.head.val; self.head = self.head.next
        if self.head: self.head.prev = None
        else: self.tail = None
        return v
    def to_list(self):
        res, cur = [], self.head
        while cur: res.append(cur.val); cur = cur.next
        return res

dll = DoublyLinkedList()
dll.push_back(2); dll.push_back(3); dll.push_front(1)
print(dll.to_list())    # [1, 2, 3]
print(dll.pop_front())  # 1
print(dll.to_list())    # [2, 3]

Output

[1, 2, 3]
1
[2, 3]

Insert at head (\(O(1)\))

To add a new node at the front:

Set the new node's next to the current head.
Set the current head's prev to the new node.
Move the head pointer to the new node.

Three pointer changes. Done.

Insert at tail (\(O(1)\))

Because we track the tail explicitly, inserting at the back is equally simple:

Set the current tail's next to the new node.
Set the new node's prev to the current tail.
Move the tail pointer to the new node.

This is something a singly linked list cannot do in \(O(1)\) without a tail pointer — and even with a tail pointer, deletion from the tail still requires \(O(n)\) to find the new tail. With a doubly linked list, the new tail is just old_tail.prev.

Delete given a node reference (\(O(1)\))

If you already have a pointer to the node you want to delete:

Set node.prev.next = node.next
Set node.next.prev = node.prev

The node is now unlinked from both directions. No traversal needed.

Real-world uses

Doubly linked lists are the backbone of several important data structures:

LRU Cache — move recently used items to the front in \(O(1)\)
Deque (double-ended queue) — push and pop from both ends in \(O(1)\)
Browser history — navigate back and forward
Undo/Redo — move through command history in both directions

Complexity

Access by positionStill must traverse from head or tail

Slow\(O(n)\)

Insert at headThree pointer updates

Instant\(O(1)\)

Insert at tailTail pointer makes this instant

Instant\(O(1)\)

Delete with node referenceprev pointer removes need to re-traverse

Instant\(O(1)\)

SpaceTwo pointers per node vs one in singly

Grows with n\(O(n)\)

Reverse a Doubly Linked List

class Node:
    def __init__(self, v): self.val=v; self.prev=self.next=None

def build(vals):
    head = None; tail = None
    for v in vals:
        n = Node(v)
        if not tail: head = tail = n
        else: n.prev=tail; tail.next=n; tail=n
    return head

def reverse(head):
    cur = head; new_head = None
    while cur:
        cur.prev, cur.next = cur.next, cur.prev
        new_head = cur
        cur = cur.prev  # was next before swap
    return new_head

def to_list(head):
    res=[]; cur=head
    while cur: res.append(cur.val); cur=cur.next
    return res

head = build([1, 2, 3, 4, 5])
head = reverse(head)
print(to_list(head))  # [5, 4, 3, 2, 1]

Output

[5, 4, 3, 2, 1]

What changes compared to singly linked?