AlgoMaster Logo

Design Browser History

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

The task is to simulate browser navigation: maintain a history of visited pages and move backward and forward through it. The defining behavior is what happens when you visit a new page from the middle of the history: all forward history is discarded.

Visit pages A, B, C, D, then go back twice to B. Visiting E from there discards C and D for good. The history becomes A, B, E, with nothing to move forward to. This clear-forward-on-visit rule is the core design challenge.

The question becomes: what data structure supports appending, truncating forward entries, and moving a pointer back and forth?

Key Constraints:

  • 1 <= steps <= 100 -> Steps are small, so a loop that moves the pointer one position at a time is fast enough.
  • At most 5000 calls to visit, back, and forward -> With so few operations, even O(n) work per call is acceptable.
  • URL lengths are at most 20 characters -> Storing every visited URL is cheap, so memory does not constrain the design.

Approach 1: Doubly Linked List

Intuition

Browser history maps directly onto a doubly linked list. Each node stores a URL, and you keep a pointer to the current node. Going back follows the prev pointer, going forward follows the next pointer, and visiting a new page creates a node after the current one and severs everything that came after.

The structure matches the problem one-to-one, but it carries overhead: a node allocation on every visit, pointer bookkeeping, and node-by-node traversal during back and forward.

Algorithm

  1. Create a doubly linked list node class with url, prev, and next fields.
  2. Initialize the list with a single node containing the homepage. Set current to this node.
  3. On visit(url), create a new node, set current.next to the new node and the new node's prev to current. Move current to the new node. This automatically discards all forward history because nothing points to the old next chain anymore.
  4. On back(steps), move current backward by following prev pointers up to steps times, stopping if prev is null.
  5. On forward(steps), move current forward by following next pointers up to steps times, stopping if next is null.

Example Walkthrough

1Constructor: single node "leetcode.com", current points here
leetcode.com
current
null
1/10

Code

The next approach stores the history in a contiguous array, which replaces node-by-node traversal with index arithmetic and removes per-visit allocations.

Approach 2: Array with Pointer (Optimal)

Intuition

Store the URLs in a dynamic array in visit order, with an integer index marking the current page.

Clearing forward history does not require deleting anything. On a visit from the middle of the history, write the new URL at position current + 1 and update a boundary variable, last, that marks the last valid index. Entries beyond last are dead history that back and forward never touch.

Every operation becomes O(1): visit writes one array slot and updates two integers, while back and forward reduce to clamped index arithmetic.

Algorithm

  1. Initialize an array with the homepage at index 0. Set current = 0 and last = 0 (the index of the last valid page).
  2. On visit(url), increment current by 1. If current equals the array size, append the URL. Otherwise, overwrite the URL at current. Set last = current to invalidate all forward history.
  3. On back(steps), set current = max(0, current - steps). Return the URL at the new current.
  4. On forward(steps), set current = min(last, current + steps). Return the URL at the new current.

Example Walkthrough

1Constructor: history=["leetcode.com"], current=0, last=0
0
last
leetcode.com
current
1/10

Code