Day 9: Doubly Linked List Explained Simply

What happens when a one-way street turns into a two-way highway—and why do your browser's Back and Forward buttons depend on it?


In 30 Seconds

A Doubly Linked List is an upgraded linked list where every node carries two pointers instead of one: a next pointer aiming forward to the following node, and a prev pointer [a reference pointing backward to the preceding node]. Because every node knows both its neighbors, you can walk forward from the head or backward from the tail [the pointer tracking the very last node]. You trade a tiny bit of extra memory per node for effortless two-way navigation and instant deletions.


The Real-World Analogy: Coupled Train Cars

Imagine a passenger train sitting on the tracks where every train car is linked to the car in front of it and the car behind it with heavy steel couplers.

  • If you are standing in Car 3, you can walk forward into Car 4 or step backward into Car 2.
  • The locomotive at the front is the Head, and the caboose at the rear is the Tail.
  • If workers need to unhook Car 3 for repairs, they don't have to walk all the way from the locomotive to figure out which car sits ahead of Car 3; Car 3 is already directly coupled to both Car 2 and Car 4!

Picture This

Here is the anatomy of a 3-node Doubly Linked List with head and tail pointers and bidirectional arrows:

HEAD TAIL None | 10 | * * | 20 | * * | 30 | None Blue Arrows: next pointer (forward) | Red Arrows: prev pointer (backward)
   HEAD                                                TAIL
    |                                                   |
    v                                                   v
+------+----+------+     +------+----+------+     +------+----+------+
| None | 10 |  *---+---->|  *   | 20 |  *---+---->|  *   | 30 | None |
+------+----+------+     +--+---+----+------+     +--+---+----+------+
  prev  data  next          |                        |
                            +---> points back to 10  +---> points back to 20

And here is what happens when you delete the middle node (20) directly:

  Before:  [10] <===> [20] <===> [30]

  Step 1:  node_20.prev.next = node_20.next   (10's next skips over 20 to 30)
  Step 2:  node_20.next.prev = node_20.prev   (30's prev skips over 20 to 10)

  After:   [10] <==============> [30]   (Node 20 is cleanly detached!)

How It Actually Works

  1. Upgrade the Node Structure: Give each Node three fields: data, prev (default None), and next (default None).
  2. Maintain Both Ends: Keep both a head pointer (front) and a tail pointer (end) so appending items takes $O(1)$ instant time.
  3. Wire Two Links on Insertion: Update four pointers when inserting between A and B: new.prev = A, new.next = B, A.next = new, and B.prev = new.
  4. Delete Without Searching Backward ($O(1)$): Given a direct reference to any node X, stitch X.prev directly to X.next without traversing from the start.

Show Me The Code

# Day 9: Doubly Linked List Implemented from Scratch in Python

class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None    # Points to the previous node
        self.next = None    # Points to the next node


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        """Adds a new node to the end (tail) in O(1) constant time."""
        new_node = DNode(data)
        if self.head is None:
            self.head = self.tail = new_node
            return

        new_node.prev = self.tail
        self.tail.next = new_node
        self.tail = new_node

    def delete_node(self, node):
        """Removes a specific node reference in O(1) time without searching."""
        if node is None:
            return

        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next

        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev

    def print_forward(self):
        vals = []
        curr = self.head
        while curr:
            vals.append(str(curr.data))
            curr = curr.next
        print("Forward:  " + " <-> ".join(vals))

    def print_backward(self):
        vals = []
        curr = self.tail
        while curr:
            vals.append(str(curr.data))
            curr = curr.prev
        print("Backward: " + " <-> ".join(vals))


if __name__ == "__main__":
    dll = DoublyLinkedList()
    dll.append("Page A")
    dll.append("Page B")
    dll.append("Page C")
    dll.print_forward()   # Output: Forward:  Page A <-> Page B <-> Page C
    dll.print_backward()  # Output: Backward: Page C <-> Page B <-> Page A

Dry Run

StepAction TakenCurrent Data Structure StatePointer Status
1Create new_node = DNode("Page B")["Page A"], ["Page B"]head = A, tail = A
2Set new_node.prev = self.tail["Page A"] <--- ["Page B"]B.prev points to A
3Set self.tail.next = new_node["Page A"] <---> ["Page B"]A.next points to B
4Update self.tail = new_nodehead -> ["Page A"] <---> ["Page B"] <- tailBoth ends updated!

Speed & Memory

OperationBest CaseAverage CaseWorst CaseWhy?
Search by Value$O(1)$$O(N)$$O(N)$Still must scan node by node from head or tail.
Insert at Head / Tail$O(1)$$O(1)$$O(1)$Direct access via head and tail pointers.
Delete Known Node$O(1)$$O(1)$$O(1)$node.prev gives instant access to the preceding node.

Where You'll See It In Real Life

  • Web Browser History: Clicking Back follows current.prev, and Forward follows current.next.
  • Music & Video Playlists: Media players use doubly linked lists for Previous/Next track navigation and drag-and-drop reordering.
  • LRU Cache Eviction Engines: High-speed caches pair a hash map with a doubly linked list to evict the oldest item in $O(1)$ time.

Traps To Avoid

  • Trap 1: Updating only next pointers and forgetting prev pointers.
    Fix: Always treat links as pairs; if A.next = B, set B.prev = A.
  • Trap 2: Crashing when deleting the head or tail node.
    Fix: Check if node.prev is None and if node.next is None before dereferencing neighbors.
  • Trap 3: Leaving dangling references on deleted nodes.
    Fix: Set node.prev = None and node.next = None upon removal.

Practice

  1. Easy: Add an insert_at_front(data) method to DoublyLinkedList.
  2. Medium: Write a method reverse() that reverses a doubly linked list in-place by swapping prev and next pointers.
  3. Hard: Design a browser history tracker class supporting visit(url), back(steps), and forward(steps).

TL;DR

  • Doubly Linked Lists give every node both a next and a prev pointer for two-way traversal.
  • Keeping a tail pointer makes insertions at both ends $O(1)$, and knowing a node lets you delete it in $O(1)$.
  • You trade a small amount of extra memory per node for huge flexibility in navigation and cache design.

References Consulted


Covered Log Update

Already covered: [Big-O notation, Arrays, Two Pointers, Strings, Sliding Window, Prefix Sums, Recursion basics, Singly Linked List, Doubly Linked List]