Beyond the Single Direction

Singly Linked Lists are efficient but frustrating: you can’t look back. If you are at Node 5 and need something from Node 4, you have to start over from the Head.

Enter the Doubly Linked List (DLL).

Analogy: The Browser History Think of a Singly Linked List like a book. You can read the next page, but to re-read the previous page, you have to start from the beginning. A Doubly Linked List is like your web browser’s history: you have a “Forward” button (Next) and a “Back” button (Prev).

1. Doubly Linked List

Each node now carries two pointers:

  1. Next: Points forward.
  2. Prev: Points backward.

Memory Trade-off

  • Singly: 4 bytes (int) + 8 bytes (next) = 12 bytes per node.
  • Doubly: 4 bytes (int) + 8 bytes (next) + 8 bytes (prev) = 20 bytes per node.
  • Cost: ~66% more memory overhead per node.
  • Benefit: O(1) deletion if you have the node (no need to search for the previous node).

Complexity Analysis

| Operation | Singly Linked List | Doubly Linked List | Notes | | :— | :— | :— | :— | | Search | O(N) | O(N) | Must still traverse to find a value. | | Delete (at head) | O(1) | O(1) | Just update head pointer. | | Delete (given node) | O(N) | O(1) | Singly requires scanning for predecessor. Doubly uses .prev. | | Space Overhead | O(N) | O(2N) | Doubly uses an extra pointer per node. |

Implementation

Java & Go

class DoublyNode {
  int val;
  DoublyNode next;
  DoublyNode prev;

  public DoublyNode(int val) {
    this.val = val;
  }
}

type DoublyNode struct {
  Val  int
  Next *DoublyNode
  Prev *DoublyNode
}

2. Interactive: DLL Navigator

Experience bidirectional traversal. Toggle “Circular Mode” to connect Tail to Head.

Node: 0
Start at Head.

3. Circular Linked Lists

A Circular Linked List is a list where the Tail points back to the Head instead of null.

Why?

  • Round Robin Scheduling: Operating Systems use this to cycle through running applications.
  • Music Playlists: “Repeat All” functionality.
  • Multiplayer Games: Turns pass from Player 1 → 2 → 3 → 1.

War Story: The Frozen Spotify Queue Early streaming apps had a bug where hitting “Next” on the last song crashed the app if it reached a null node. By switching to a Circular Linked List, the tail node’s next automatically pointed to the head. It eliminated null pointer exceptions and implicitly enabled the “Loop Playlist” feature with zero extra code logic.

Implementation Tip

In a Circular List, you never reach null.

  • Danger: while(current ≠ null) will be an infinite loop.
  • Fix: do { ... } while (current ≠ head).

4. Deleting a Node (The DLL Superpower)

In a Singly Linked List, to delete Node B, you need a pointer to Node A (its predecessor). This requires scanning from the Head (O(N)).

In a Doubly Linked List, B knows about A via B.prev. We can delete B in O(1) if we have a reference to it.

// O(1) Deletion
node.prev.next = node.next;
node.next.prev = node.prev;
Warning

Always check for null. If you delete the Head or Tail, prev or next might not exist.

5. Common Pitfalls

  1. Dangling Pointers in Deletion: When deleting a node from a DLL, always verify prev and next are not null before updating their pointers. Failing to do so causes a NullPointerException.
  2. Memory Leaks in GC Languages: In languages like C++, if you don’t explicitly break the prev and next links of a deleted node, it might not be properly deallocated.
  3. Infinite Loops in Circular Lists: Forgetting the termination condition do { ... } while (current != head) will cause your traversal to spin forever.

In the next chapter, we will tackle the most common interview operations: Reversing and Merging.