Browser History#

Browser history LLD design centers on two stacks (back and forward) coordinated by a current-page pointer. Every visit(url) pushes onto back, clears forward, and moves the pointer. back(k) and forward(k) shuffle entries between the two stacks, respecting k bounded by stack size.

classDiagram
  class BrowserHistory {
    -back : Deque~string~
    -forward : Deque~string~
    -current : string
    +visit(url) void
    +back(k) string
    +forward(k) string
    +clear() void
  }
  class TabManager {
    -tabs : Map~tabId, BrowserHistory~
    +open(tabId)
    +close(tabId)
    +get(tabId) BrowserHistory
  }
  TabManager --> BrowserHistory : owns one per tab

Each tab owns its own history instance, so navigation in one tab cannot pop another's stack. A visit after several back() calls discards the forward branch, matching real browsers: once you click a new link, the redo path is gone.

Extensions worth mentioning in an interview: cap the back stack at a fixed size and evict the oldest entry (LRU on the deque tail); store a tuple (url, scrollY, formState) per entry to restore page state; persist to disk per session.

classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;

Browser history is the classic two-stack LLD interview problem. Get the invariants right and you also have the template for undo-redo, navigation drawers, and editor history. This guide covers the canonical design, edge cases interviewers love to probe, and the extension to bounded history with eviction.

Problem statement (interviewer prompt)

Design a browser history. Support visit(url), back(steps), forward(steps), and clear(). Each tab has its own history. back and forward return the current URL after moving. Visiting a new page from the middle of history discards the forward branch. Discuss extensions for bounded history (max N entries) with LRU eviction.

Requirements#

Functional

visit(url): navigate to a new URL, clearing the forward path.
back(k): go back up to k steps, return current URL.
forward(k): go forward up to k steps, return current URL.
clear(): wipe both stacks; keep the current URL.
Per-tab isolation: opening a new tab gets a fresh history.

Non-functional

O(1) for visit, amortized O(k) for back/forward.
Bounded memory: optionally cap at N entries; evict oldest.

Class design#

classDiagram
  class BrowserHistory {
    -back : Deque~Entry~
    -forward : Deque~Entry~
    -current : Entry
    -capacity : int
    +visit(url) void
    +back(k) string
    +forward(k) string
    +clear() void
    +currentUrl() string
  }
  class Entry {
    +url : string
    +visitedAt : long
    +scrollY : int
  }
  class TabManager {
    -tabs : Map~int, BrowserHistory~
    -nextTabId : AtomicInt
    +open() int
    +close(tabId) void
    +get(tabId) BrowserHistory
  }
  BrowserHistory --> Entry : holds many
  TabManager --> BrowserHistory : one per tab

Entry is intentionally richer than a raw string. Real browsers persist scroll position, form state, and session storage per entry; modelling it as a class makes the extension trivial.

Core flow#

sequenceDiagram
  participant U as User
  participant T as TabManager
  participant H as BrowserHistory
  U->>T: open()
  T-->>U: tabId=1
  U->>H: visit("a.com")
  Note over H: current=a, back=[], forward=[]
  U->>H: visit("b.com")
  Note over H: back=[a], current=b, forward=[]
  U->>H: back(1)
  H-->>U: "a.com"
  Note over H: back=[], current=a, forward=[b]
  U->>H: visit("c.com")
  Note over H: back=[a], current=c, forward=[] (b discarded)
  U->>H: forward(1)
  H-->>U: "c.com" (no-op, forward empty)

The destructive visit from the middle of history is the rule everyone forgets: it must clear the forward stack.

Code#

import java.util.*;

public class BrowserHistory {
    private final Deque<String> back = new ArrayDeque<>();
    private final Deque<String> forward = new ArrayDeque<>();
    private String current;
    private final int capacity;

    public BrowserHistory(String homepage, int capacity) {
        this.current = homepage;
        this.capacity = capacity;
    }

    public void visit(String url) {
        back.push(current);
        current = url;
        forward.clear();
        if (capacity > 0 && back.size() >= capacity) {
            back.pollLast();  // LRU eviction from the tail
        }
    }

    public String back(int steps) {
        while (steps-- > 0 && !back.isEmpty()) {
            forward.push(current);
            current = back.pop();
        }
        return current;
    }

    public String forward(int steps) {
        while (steps-- > 0 && !forward.isEmpty()) {
            back.push(current);
            current = forward.pop();
        }
        return current;
    }

    public void clear() {
        back.clear();
        forward.clear();
    }
}

ArrayDeque is the right choice: O(1) push/pop on both ends, no synchronization overhead, no null entries. The pollLast() call gives bounded history with LRU eviction by dropping the oldest back entry once we exceed capacity.

Per-tab isolation#

public class TabManager {
    private final Map<Integer, BrowserHistory> tabs = new ConcurrentHashMap<>();
    private final AtomicInteger nextTabId = new AtomicInteger(1);
    private static final int HISTORY_CAP = 100;

    public int open(String homepage) {
        int id = nextTabId.getAndIncrement();
        tabs.put(id, new BrowserHistory(homepage, HISTORY_CAP));
        return id;
    }

    public void close(int tabId) {
        tabs.remove(tabId);
    }

    public BrowserHistory get(int tabId) {
        BrowserHistory h = tabs.get(tabId);
        if (h == null) throw new NoSuchElementException("tab " + tabId);
        return h;
    }
}

Each tab owns a BrowserHistory. TabManager is the only place we need a concurrent map; individual histories are usually thread-confined to the tab's UI thread.

Concurrency and edge cases#

Single-tab is single-threaded. Browser UIs serialize navigation on the main thread. No locking needed inside BrowserHistory unless you expose it to background tasks like prefetch or scroll restoration.

Multi-tab concurrency lives in TabManager. Use ConcurrentHashMap so tab open/close races don't corrupt state. AtomicInteger for tab IDs.

Undo-redo extension is the same pattern but typically concurrent: collaborative editors run history on a background thread. Then BrowserHistory itself needs a ReentrantLock around all four operations, treating the three fields (back, forward, current) as one atomic unit.

Edge cases interviewers probe

Case	Expected behaviour
`back(0)`	No-op, return current
`back(1000)` when back stack has 3 entries	Move to oldest, return it
`forward()` after `visit()`	No-op (forward was cleared)
`visit(currentUrl)`	Still pushes a new entry (some browsers dedupe; clarify with interviewer)
Cap = 0	Unbounded; document explicitly
`clear()` while iterating	Not supported, undefined

Extensions#

Bounded with LRU eviction. Cap back size at N. On overflow, drop the deepest entry. This is exactly the pollLast() line above. Memory becomes O(N) per tab; with 100 tabs and N=100 that's 10k entries: fine.

Persisted history. Append every visit to a write-ahead log; on tab restore, replay the log. Cap the log file with rotation. SQLite is what Chrome and Firefox use.

Search across history. Maintain a separate trie or inverted index over URL/title. See Trie Autocomplete LLD.

State machine view. Treat the tab as a state machine over {pristine, navigating, loaded, errored}. See State Machines. Useful when modelling the full browser, not just history.

flowchart LR
  BH((Browser<br/>history))
  SM[State machines<br/>tab lifecycle]
  BP[Behavioral patterns<br/>memento, command]
  TR[Trie autocomplete<br/>history search]
  SM --> BH
  BP -. memento per entry .-> BH
  BH -. extends to .-> TR

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    class BH service;
    class SM,BP,TR datastore;

Quick reference#

Key classes#

BrowserHistory: back deque, forward deque, current pointer
Entry: URL + optional scrollY, formState, visitedAt
TabManager: Map<tabId, BrowserHistory>, owns one history per tab

Invariant#

back is the path you came from, top is most-recent prior page
forward is the redo path, top is the page you just came back from
current is neither in back nor forward

Operations#

visit(url): push current to back; current = url; clear forward
back(k): while k-- and back not empty: push current to forward; current = back.pop()
forward(k): mirror image of back
clear(): empty both stacks; keep current

Complexity#

Op	Time	Space
`visit`	O(1) amortized (+forward.clear)	O(1)
`back(k)`	O(k)	O(1)
`forward(k)`	O(k)	O(1)
`clear()`	O(N)	O(1)

Bounded history#

Cap back stack at N; on overflow drop tail (LRU eviction)
ArrayDeque.pollLast() is the one-liner
Forward is naturally bounded by back size

Interview questions to expect#

Why use ArrayDeque not Stack? Stack is synchronized + legacy
What if back(k) exceeds stack size? Return oldest, don't throw
Does visit(currentUrl) dedupe? Clarify; Chrome does not, Safari does
How do you persist? WAL append per visit; SQLite is what real browsers use
Multi-tab concurrency? Per-tab is single-threaded; TabManager map needs concurrent

Extensions#

Undo-redo (collaborative editors): same shape but needs locking
History search: build a trie over URLs/titles, rank by visit count
Session restore: serialize each tab's deque to disk on close

Pitfalls#

Forgetting to clear forward on visit (the classic LeetCode bug)
Using LinkedList instead of ArrayDeque (extra node allocations)
Sharing one history across tabs (per-tab isolation is required)
Locking individual history when only TabManager needs concurrency

Refs#

LeetCode 1472 - Design Browser History
Chrome history.cc source (Chromium git)
Gamma Memento pattern (GoF) for the undo-redo generalization

FAQ#

How do you design browser back/forward history?#

Use two stacks: back holds visited pages and forward holds pages popped by back. A current pointer marks the active page. visit pushes to back and clears forward.

Why does visit clear the forward stack?#

When the user clicks a new link after pressing back, the redo branch is gone in real browsers. Clearing forward matches this UX and prevents stale forward history from reappearing.

How are back(k) and forward(k) implemented?#

Both pop up to k entries from one stack and push them on the other while updating the current pointer. If k exceeds stack size, you stop at the boundary instead of erroring.

How do you bound memory for very long sessions?#

Cap the back stack at a fixed size; on overflow, evict the oldest entry from the deque tail. This is effectively an LRU on visit recency for the back direction.

How do you support multiple tabs?#

A TabManager maps tabId to its own BrowserHistory instance. Each tab gets isolated stacks so back in tab A does not affect tab B.

State Machines: tab lifecycle as a state machine
Behavioral Patterns: memento and command underpin undo-redo
Trie Autocomplete LLD: how history search ranks by frequency

Browser History#

Requirements#

Class design#

Core flow#

Code#

Per-tab isolation#

Concurrency and edge cases#

Extensions#

Quick reference#

Key classes#

Invariant#

Operations#

Complexity#

Bounded history#

Interview questions to expect#

Extensions#

Pitfalls#

Refs#

FAQ#

How do you design browser back/forward history?#

Why does visit clear the forward stack?#

How are back(k) and forward(k) implemented?#

How do you bound memory for very long sessions?#

How do you support multiple tabs?#

Related Topics#