Design Browser History — Doubly Linked List Implementation Explained

Problem Statement#

LeetCode 1472 — Design Browser History Difficulty: Medium | Pattern: Doubly Linked List Design

You are designing a browser with one tab. Implement the BrowserHistory class:

• BrowserHistory(homepage): Initialize the browser with the given homepage URL.
• visit(url): Visit url from the current page. Any forward history is discarded.
• back(steps): Move steps back in history. Move only as many steps as available. Return the current URL.
• forward(steps): Move steps forward in history. Move only as many steps as available. Return the current URL.

Constraints:

• 1 <= homepage.length, url.length <= 20
• 1 <= steps <= 100
• At most 5000 calls will be made to visit, back, and forward.

Example:

BrowserHistory browser = new BrowserHistory("leetcode.com");
browser.visit("google.com");       // current: google.com
browser.visit("facebook.com");     // current: facebook.com
browser.visit("youtube.com");      // current: youtube.com
browser.back(1);                   // returns "facebook.com"
browser.back(1);                   // returns "google.com"
browser.forward(1);                // returns "facebook.com"
browser.visit("linkedin.com");     // visits linkedin, clears youtube forward history
browser.forward(2);                // can't move forward, returns "linkedin.com"
browser.back(2);                   // returns "google.com"
browser.back(7);                   // only 1 step possible, returns "leetcode.com"

Why This Problem Matters#

This problem is a practical application of the doubly linked list that directly models how browser history actually works. Amazon, Microsoft, and Google use it in interviews to test whether you can translate a real-world system — one you use every day — into a clean data structure implementation.

The doubly linked list is the natural choice because:

• Moving forward means following next pointers.
• Moving backward means following prev pointers.
• Visiting a new page means inserting after the current node and discarding everything after the new node.

The "discard forward history on visit" rule is the key insight: you do not delete nodes one by one — you simply set curr.next = new_node (the new page). This effectively orphans all forward history nodes (they become unreachable and get garbage collected), which mirrors exactly how real browsers work.

This problem is also a clean stepping stone to the LRU Cache (LC 146) — both use doubly linked lists for O(1) navigation, but browser history does not need the HashMap component.

In system design interviews, understanding how a browser implements history using a doubly linked list with a current-page cursor is foundational knowledge. Interviewers at Amazon routinely ask "how would you design browser history to support infinite undo?" — and this problem is the technical foundation for that discussion.

The Core Insight#

Model browser history as a doubly linked list with a curr pointer:

• Each node holds a URL string and prev/next pointers.
• curr always points to the current page.
• visit(url): Create a new node. Link it after curr. Move curr to the new node. The old curr.next (forward history) is now unreachable — garbage collected automatically.
• back(steps): Move curr backward up to steps times (stop when curr.prev is null). Return curr.url.
• forward(steps): Move curr forward up to steps times (stop when curr.next is null). Return curr.url.

The beauty of this design: all three operations are O(steps) — which is O(1) amortized for single-step operations and O(steps) in the worst case. The visit operation is always O(1).

Visual Dry Run#

Starting state: curr -> [leetcode.com]

visit("google.com"):
  new_node = [google.com]
  curr.next = new_node
  new_node.prev = curr
  curr = new_node
  State: [leetcode.com] <-> [google.com](curr)
 
visit("facebook.com"):
  State: [leetcode.com] <-> [google.com] <-> [facebook.com](curr)
 
visit("youtube.com"):
  State: [leetcode.com] <-> [google.com] <-> [facebook.com] <-> [youtube.com](curr)
 
back(1):
  curr = curr.prev = [facebook.com]
  return "facebook.com"
 
back(1):
  curr = curr.prev = [google.com]
  return "google.com"
 
forward(1):
  curr = curr.next = [facebook.com]
  return "facebook.com"
 
visit("linkedin.com"):
  new_node = [linkedin.com]
  curr.next = new_node  (youtube.com is now orphaned/discarded)
  new_node.prev = curr
  curr = new_node
  State: [leetcode.com] <-> [google.com] <-> [facebook.com] <-> [linkedin.com](curr)
 
forward(2):
  curr.next is null (no forward history after linkedin)
  return "linkedin.com"
 
back(2):
  curr = curr.prev = [facebook.com]
  curr = curr.prev = [google.com]
  return "google.com"
 
back(7):
  curr = curr.prev = [leetcode.com]
  curr.prev is null (can't go further back)
  return "leetcode.com"

Solution (Optimal)#

class Node:
    def __init__(self, url: str):
        self.url = url
        self.prev = None
        self.next = None
 
class BrowserHistory:
    def __init__(self, homepage: str):
        self.curr = Node(homepage)
 
    def visit(self, url: str) -> None:
        new_node = Node(url)
        new_node.prev = self.curr
        self.curr.next = new_node
        self.curr = new_node
        # Old curr.next is now orphaned (forward history discarded)
 
    def back(self, steps: int) -> str:
        while steps > 0 and self.curr.prev:
            self.curr = self.curr.prev
            steps -= 1
        return self.curr.url
 
    def forward(self, steps: int) -> str:
        while steps > 0 and self.curr.next:
            self.curr = self.curr.next
            steps -= 1
        return self.curr.url

class Node {
    constructor(url) {
        this.url = url;
        this.prev = null;
        this.next = null;
    }
}
 
class BrowserHistory {
    constructor(homepage) {
        this.curr = new Node(homepage);
    }
 
    visit(url) {
        const newNode = new Node(url);
        newNode.prev = this.curr;
        this.curr.next = newNode;
        this.curr = newNode;
        // Forward history (old curr.next) is now orphaned
    }
 
    back(steps) {
        while (steps > 0 && this.curr.prev !== null) {
            this.curr = this.curr.prev;
            steps--;
        }
        return this.curr.url;
    }
 
    forward(steps) {
        while (steps > 0 && this.curr.next !== null) {
            this.curr = this.curr.next;
            steps--;
        }
        return this.curr.url;
    }
}

Complexity:

Array-based alternative (simpler, same complexity):

class BrowserHistory:
    def __init__(self, homepage):
        self.history = [homepage]
        self.curr = 0
 
    def visit(self, url):
        self.history = self.history[:self.curr + 1]  # discard forward
        self.history.append(url)
        self.curr += 1
 
    def back(self, steps):
        self.curr = max(0, self.curr - steps)
        return self.history[self.curr]
 
    def forward(self, steps):
        self.curr = min(len(self.history) - 1, self.curr + steps)
        return self.history[self.curr]

Common Mistakes#

1. Not discarding forward history on visit: The most critical rule — when you visit a new page, curr.next must be set to the new node (overwriting the old forward chain). Simply adding the node to the end of the list would preserve stale forward history.
2. Setting curr.next to null before linking: If you null out curr.next before creating the new node, you lose the pointer temporarily. Link the new node first, then advance curr.
3. Off-by-one in back/forward loops: The while conditions are steps > 0 AND curr.prev/next is not null. Both conditions must be checked — checking only one causes crashes or incorrect termination.
4. Forgetting to return curr.url from back/forward: Both methods must return the current URL after moving, not the URL of the last successfully traversed node.
5. Not handling the "can't move further" gracefully: If steps = 7 but only 2 steps are possible, move 2 steps and stop. The clamp logic (stop when prev/next is null) handles this naturally.

Interview Tips#

• Start with the real-world model: "This is literally how browser history works — a doubly linked list with a current page pointer. Visiting a new URL creates a new node and orphans forward history."
• Explain the discard mechanism: "I don't explicitly delete forward history — I just point curr.next to the new node. The old forward chain becomes unreachable and gets garbage collected."
• Offer the array alternative: "A simpler implementation uses an array with a curr index. It is easier to implement but uses O(n) space per visit since you copy the array slice. The DLL approach is O(1) per visit."
• Draw the state transitions: Walk through the example step by step on the whiteboard. The visual makes the pointer logic immediately clear.
• Discuss when DLL is preferred: "The DLL approach is better when you have millions of history entries and frequent back/forward — no array slicing needed."

Follow-up Questions#

1. LeetCode 146 — LRU Cache: The next level up — doubly linked list plus HashMap. Can you implement that?
2. Infinite undo/redo: Browser history is a special case of undo/redo stacks. How would you generalize to arbitrary command history?
3. How does a real browser implement history? Most browsers use a combination of in-memory DLL for the current session and persistent storage (disk) for history across sessions.
4. Thread-safe browser history: Multiple tabs share a history. Discuss locking strategies.
5. Add a bookmark feature: Each node should also have a bookmarked boolean. How does back change if it should stop at bookmarks?
6. LeetCode 895 — Maximum Frequency Stack: Another design problem where you design a stack with specialized pop behavior — tests similar "custom data structure" thinking.

Key Takeaways#

• Browser history is naturally modeled as a doubly linked list with a curr pointer representing the current page.
• visit(url): Create a new node, link it after curr, advance curr. Old forward history becomes orphaned (no explicit deletion needed).
• back(steps) and forward(steps): Walk curr in the respective direction up to steps times, stopping when the list boundary is reached.
• The "discard forward history" invariant is maintained purely by overwriting curr.next — no explicit deletion of old nodes.
• Array-based alternative is simpler to code (array slicing for discard) but copies O(n) elements on every visit. DLL approach is O(1) per visit.
• This problem is a stepping stone to LRU Cache (LC 146), undo/redo systems, and any interview question about pointer-based state navigation.