Design Browser History

How it works

A doubly linked list provides a natural representation of browser history where each node contains a URL and pointers to the previous and next pages. We maintain a pointer to the current node. Navigating back follows the prev pointer, navigating forward follows the next pointer, and visiting a new URL creates a new node linked to the current one while discarding any forward history.

Steps

1. Initialize a single node with the homepage and set cur to point to it.
2. For visit(url): Create a new node with the URL, link it as the next node of cur with cur as its prev pointer, then move cur to this new node. This automatically discards forward history since the new node has no next.
3. For back(steps): While steps remain and cur.prev exists, move cur to cur.prev. Return cur.val.
4. For forward(steps): While steps remain and cur.next exists, move cur to cur.next. Return cur.val.

Complexity

• Time complexity:
  • O(1) time for initialization.
  • O(1) time for each visit() function call.
  • O(min(n, steps)) time for each back() and forward() function calls.
• Space complexity: O(m * n)

Where n is the number of visited urls, m is the average length of each url, and steps is the number of steps we go forward or back.

Things to watch for

Not Clearing Forward History on Visit

When visiting a new URL, the forward history must be invalidated. A common mistake is forgetting to clear the forward stack or reset the logical end pointer.

Allowing Back to Go Before Homepage

The homepage is always the first page and cannot be navigated before. A common mistake is not preserving at least one element in the back history.

Confusing Array Index with Logical Size

In the optimal dynamic array approach, using len(history) instead of n (logical size) for forward navigation causes accessing stale elements that should be considered deleted.

class ListNode:
    def __init__(self, val, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

class BrowserHistory:

    def __init__(self, homepage: str):
        self.cur = ListNode(homepage)

    def visit(self, url: str) -> None:
        self.cur.next = ListNode(url, self.cur)
        self.cur = self.cur.next

    def back(self, steps: int) -> str:
        while self.cur.prev and steps > 0:
            self.cur = self.cur.prev
            steps -= 1
        return self.cur.val

    def forward(self, steps: int) -> str:
        while self.cur.next and steps > 0:
            self.cur = self.cur.next
            steps -= 1
        return self.cur.val

class BrowserHistory {
    struct ListNode {
    public:
        string val;
        ListNode* prev;
        ListNode* next;

        ListNode(string val, ListNode* prev = nullptr, ListNode* next = nullptr)
            : val(val), prev(prev), next(next) {}
    };

    ListNode* cur;

public:
    BrowserHistory(string homepage) {
        cur = new ListNode(homepage);
    }

    void visit(string url) {
        cur->next = new ListNode(url, cur, nullptr);
        cur = cur->next;
    }

    string back(int steps) {
        while (cur->prev != nullptr && steps > 0) {
            cur = cur->prev;
            steps--;
        }
        return cur->val;
    }

    string forward(int steps) {
        while (cur->next != nullptr && steps > 0) {
            cur = cur->next;
            steps--;
        }
        return cur->val;
    }
};