L28. Design a Browser History | LinkedList Implementation
Designing a browser history system is a classic data structures and algorithms problem that simulates how web browsers (like Google Chrome, Safari, or Firefox) manage forward and backward navigation tabs. This chapter breaks down how to implement this system from scratch using a Doubly Linked List to achieve optimal time and space efficiency.
1. Why Do We Need a Custom Data Structure? (The Status Quo)
When building a browsing history tracker, users perform four core operations:
- Initialize a browser session with a starting homepage.
- Visit a new URL (which clears any forward history).
- Go Back by a given number of steps .
- Go Forward by a given number of steps .
Why Dynamic Arrays Fail Here
- Memory Shifting Overhead: If we used a dynamic array (like a list or vector) and went back to an older page before visiting a new one, all subsequent forward history would need to be deleted and rewritten.
- Dynamic Length Unknowns: We never know beforehand how many pages a user will visit, making fixed-size arrays impractical and resizing arrays computationally expensive ( for insertions/deletions in the middle).
2. Core Mental Model: The Chrome Tab Analogy
Real-Life Analogy: Imagine opening a brand-new browser tab.
- You type
takeuforward.org(Homepage). This is your starting point.- You click a link to
google.com.- Then you click a link to
instagram.com.- Then you click a link to
facebook.com.At this point, your history forms a linear chain where you can walk backward to check previous pages or walk forward if you haven't branched off to a new URL.
The Golden Rule of Browsing: If you are currently standing on
instagram.comand you visit a brand-future URL liketakeuforward.org, all forward history (likefacebook.com) is instantly erased. You cannot return tofacebook.combecause you branched off onto a new timeline.
3. Choosing the Right Data Structure: Doubly Linked List
To support moving seamlessly in both directions (backward and forward) while dynamically adding new nodes without shifting indices, we require a Doubly Linked List (DLL).
- Singly Linked List: Only allows traversal in one direction (next). If you are on page and need to go back to page , a singly linked list gives you no way to walk backward because nodes only point forward.
- Doubly Linked List: Each node contains a
nextpointer, aback(orprev) pointer, and adatapayload storing the URL string.
4. Designing the Custom Node Structure
Instead of storing integers (like standard DSA linked list problems), our custom node stores a string representing the web URL, alongside two pointers (next and back).
class Node {
string data; // Stores the URL (e.g., "google.com")
Node* next; // Pointer to the next page
Node* back; // Pointer to the previous page
// Constructor to initialize a node with a URL
Node(string url) {
data = url;
next = nullptr;
back = nullptr;
}
}
5. Step-by-Step Flow of Browser Operations
Let's trace how the browser executes a sequence of queries using our Doubly Linked List approach.
Query Walkthrough Example
Browser("takeuforward.org"): Initializes the browser with the homepage.CODE[takeuforward.org] (Current)visit("google.com"): Navigates to Google.Structure & Concept Flowvisit("instagram.com"): Navigates to Instagram.Structure & Concept Flowvisit("facebook.com"): Navigates to Facebook.Structure & Concept Flowback(1): Steps back 1 page. Returns"instagram.com".Structure & Concept Flowback(1): Steps back 1 page. Returns"google.com".Structure & Concept Flowforward(1): Steps forward 1 page. Returns"instagram.com".Structure & Concept Flowvisit("takeuforward.org"): Visits a new URL from Instagram. Facebook node is dropped.Structure & Concept Flow
6. Implementation Code (C++ Solution)
Below is the complete, production-ready class implementation covering the Constructor, visit, back, and forward methods.
class Node {
public:
string data;
Node* next;
Node* back;
Node(string val) {
data = val;
next = nullptr;
back = nullptr;
}
};
class BrowserHistory {
private:
Node* current;
public:
// 1. Constructor: Initializes browser with homepage
BrowserHistory(string homepage) {
current = new Node(homepage);
}
// 2. Visit: Clears forward history and links new URL
void visit(string url) {
Node* newNode = new Node(url);
current->next = newNode;
newNode->back = current;
current = newNode; // Move current pointer to the new page
}
// 3. Back: Moves backward by 'steps' or until bounds are hit
string back(int steps) {
while (steps > 0) {
// Check if there is a previous page to go to
if (current->back != nullptr) {
current = current->back;
} else {
break; // Stop if we hit the start of history (homepage)
}
steps--;
}
return current->data;
}
// 4. Forward: Moves forward by 'steps' or until bounds are hit
string forward(int steps) {
while (steps > 0) {
// Check if there is a next page to go to
if (current->next != nullptr) {
current = current->next;
} else {
break; // Stop if we hit the end of history
}
steps--;
}
return current->data;
}
};
7. Real-World Practical Pitfalls & Edge Cases
When coding this in interviews or production environments, keep these edge cases in mind:
- Reaching the Homepage Boundary: If a user requests
back(100)but there is only 1 page in history (the homepage), thewhileloop must checkcurrent->back != nullptrso it doesn't trigger aNullPointerException(or segmentation fault in C++). It should safely halt at the homepage and return the homepage URL. - Reaching the Forward Boundary: Similarly, requesting
forward(5)when no future pages exist will cause the pointer to evaluatecurrent->next == nullptr, at which point it breaks out of the loop safely. - Branching Loss of Data: When
visit()is called from the middle of the history chain, the oldcurrent->nextis overwritten. Garbage collection languages (like Java or Python) automatically reclaim the orphaned nodes, while C++ developers must be mindful of memory leaks if persistent node pooling is required.
8. Complexity Analysis Summary
Summary and Key Takeaways
- Problem Domain: Designing a browser history requires tracking bidirectional traversal (going back and forth) while dynamically adding new states.
- Data Structure Choice: A Doubly Linked List is optimal because it supports node insertion and bidirectional pointer movement.
- Node Structure: Replaced integer payloads with string URLs (
data), alongsidenextandbackpointers. - The Visit Action: Visiting a new page from an intermediate history state truncates (deletes) all forward history timelines.
- Boundary Checks: Always validate that
current->backorcurrent->nextis notnullptrbefore decrementing or incrementing step counters. - Time Complexity: Navigation operations (
back/forward) scale linearly with the number of steps requested: . - Space Efficiency: New nodes consume memory proportional to the number of unique URLs visited.