Browser History Simulator

Problem Statement

Write a Java program that simulates a browser’s navigation history using a doubly linked list. Each node in the list represents a webpage with a string URL. The program should support adding new pages (insert at tail), navigating back (delete the current tail and move to the previous page), and navigating forward (re-insert a previously deleted page). A current pointer tracks the current page, and forward navigation is only possible if pages were previously removed via back navigation. Test the implementation with sequences of operations, including adding pages, navigating back and forward, and handling edge cases like empty history or navigating beyond available pages. You can visualize this as managing a browser’s history where new pages are added to the end, going back removes the current page, and going forward restores a previously visited page.

Input:

• A sequence of operations, where each operation is:
  • visit(url): Add a new page (URL) at the tail, clear forward history.
  • back(): Move to the previous page, remove current page, return URL or "null" if not possible.
  • forward(): Move to the next page (re-insert removed page), return URL or "null" if not possible.
  • printHistory(): Print the current history from head to current page. Output: For each operation, print the action performed (e.g., "Visited URL", "Navigated back to URL", "Navigated forward to URL", or the current history). Return "null" for invalid back/forward navigations. Constraints:
• The history size is between 0 and 10^5.
• URLs are non-empty strings of length up to 100 characters.
• The history may be empty or have no forward/backward pages. Example:
• Input: Operations = [visit("page1"), visit("page2"), visit("page3"), printHistory, back, printHistory, forward, printHistory]
• Output:

  Visited page1
  Visited page2
  Visited page3
  History: page1 page2 page3
  Navigated back to page2
  History: page1 page2
  Navigated forward to page3
  History: page1 page2 page3
  

• Input: Operations = [back, printHistory]
• Output:

  Navigated back to null
  History: []
  

Pseudocode

CLASS DoublyNode
    SET url to string
    SET next to DoublyNode (null by default)
    SET prev to DoublyNode (null by default)
ENDCLASS

CLASS BrowserHistory
    SET head to null
    SET current to null

    FUNCTION visit(url)
        CREATE newNode as new DoublyNode(url)
        IF head is null THEN
            SET head to newNode
            SET current to newNode
        ELSE
            SET current.next to newNode
            SET newNode.prev to current
            SET current to newNode
        ENDIF
    ENDFUNCTION

    FUNCTION back()
        IF current is null OR current.prev is null THEN
            RETURN "null"
        ENDIF
        SET url to current.url
        SET current to current.prev
        SET current.next to null
        RETURN url
    ENDFUNCTION

    FUNCTION forward(forwardList)
        IF forwardList is empty THEN
            RETURN "null"
        ENDIF
        SET url to forwardList.removeLast()
        CREATE newNode as new DoublyNode(url)
        SET newNode.prev to current
        IF current is not null THEN
            SET current.next to newNode
        ELSE
            SET head to newNode
        ENDIF
        SET current to newNode
        RETURN url
    ENDFUNCTION

    FUNCTION toString()
        IF head is null THEN
            RETURN "[]"
        ENDIF
        CREATE result as new StringBuilder
        SET temp to head
        WHILE temp is not null AND temp is not current.next
            APPEND temp.url to result
            IF temp.next is not null AND temp.next is not current.next THEN
                APPEND " " to result
            ENDIF
            SET temp to temp.next
        ENDWHILE
        RETURN result as string
    ENDFUNCTION
ENDCLASS

FUNCTION testBrowserHistory(operations)
    CREATE browser as new BrowserHistory
    CREATE forwardList as new list
    FOR each operation in operations
        IF operation.type equals "visit" THEN
            CLEAR forwardList
            CALL browser.visit(operation.url)
            PRINT visited url
        ELSE IF operation.type equals "back" THEN
            SET url to browser.back()
            IF url is not "null" THEN
                ADD url to forwardList
            ENDIF
            PRINT navigated back to url
        ELSE IF operation.type equals "forward" THEN
            SET url to browser.forward(forwardList)
            PRINT navigated forward to url
        ELSE IF operation.type equals "print" THEN
            PRINT history using browser.toString
        ENDIF
    ENDFOR
ENDFUNCTION

FUNCTION main()
    SET testCases to array of operation sequences
    FOR each testCase in testCases
        PRINT test case details
        CALL testBrowserHistory(testCase)
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define a DoublyNode class with: a. A string url for the webpage. b. A next pointer to the next node. c. A prev pointer to the previous node.
2. Define a BrowserHistory class with: a. head and current pointers to track the list and current page. b. visit: Add new node at tail, clear forward history, update current. c. back: Move current to previous node, remove current tail, store URL for forward. d. forward: Re-insert last removed URL from forward list, update current. e. toString: Print history from head to current page.
3. In testBrowserHistory: a. Create a BrowserHistory and a forwardList to store back-navigated URLs. b. For each operation:
   • visit: Clear forward list, call visit, print action.
   • back: Call back, store URL in forward list, print URL.
   • forward: Call forward with forward list, print URL.
   • print: Call toString, print history.
4. In main, test with sequences including visits, back/forward navigations, and edge cases.

Java Implementation

import java.util.*;

public class BrowserHistorySimulator {
    // Node class for the doubly linked list
    static class DoublyNode {
        String url;
        DoublyNode next;
        DoublyNode prev;

        DoublyNode(String url) {
            this.url = url;
            this.next = null;
            this.prev = null;
        }
    }

    // BrowserHistory class to simulate navigation
    static class BrowserHistory {
        private DoublyNode head;
        private DoublyNode current;

        public void visit(String url) {
            DoublyNode newNode = new DoublyNode(url);
            if (head == null) {
                head = newNode;
                current = newNode;
            } else {
                current.next = newNode;
                newNode.prev = current;
                current = newNode;
            }
        }

        public String back() {
            if (current == null || current.prev == null) {
                return "null";
            }
            String url = current.url;
            current = current.prev;
            current.next = null;
            return url;
        }

        public String forward(List<String> forwardList) {
            if (forwardList.isEmpty()) {
                return "null";
            }
            String url = forwardList.remove(forwardList.size() - 1);
            DoublyNode newNode = new DoublyNode(url);
            newNode.prev = current;
            if (current != null) {
                current.next = newNode;
            } else {
                head = newNode;
            }
            current = newNode;
            return url;
        }

        public String toString() {
            if (head == null) {
                return "[]";
            }
            StringBuilder result = new StringBuilder();
            DoublyNode temp = head;
            while (temp != null && temp != current.next) {
                result.append(temp.url);
                if (temp.next != null && temp.next != current.next) {
                    result.append(" ");
                }
                temp = temp.next;
            }
            return result.toString();
        }
    }

    // Helper class for operations
    static class Operation {
        String type;
        String url;

        Operation(String type, String url) {
            this.type = type;
            this.url = url;
        }
    }

    // Tests browser history operations
    public void testBrowserHistory(List<Operation> operations) {
        BrowserHistory browser = new BrowserHistory();
        List<String> forwardList = new ArrayList<>();
        for (Operation op : operations) {
            if (op.type.equals("visit")) {
                forwardList.clear();
                browser.visit(op.url);
                System.out.println("Visited " + op.url);
            } else if (op.type.equals("back")) {
                String url = browser.back();
                if (!url.equals("null")) {
                    forwardList.add(url);
                }
                System.out.println("Navigated back to " + url);
            } else if (op.type.equals("forward")) {
                String url = browser.forward(forwardList);
                System.out.println("Navigated forward to " + url);
            } else if (op.type.equals("print")) {
                System.out.println("History: " + browser.toString());
            }
        }
    }

    // Main method to test browser history simulator
    public static void main(String[] args) {
        BrowserHistorySimulator simulator = new BrowserHistorySimulator();

        // Test cases
        List<List<Operation>> testCases = new ArrayList<>();
        
        // Test case 1: Normal navigation
        testCases.add(Arrays.asList(
            new Operation("visit", "page1"),
            new Operation("visit", "page2"),
            new Operation("visit", "page3"),
            new Operation("print", null),
            new Operation("back", null),
            new Operation("print", null),
            new Operation("forward", null),
            new Operation("print", null)
        ));
        
        // Test case 2: Empty history
        testCases.add(Arrays.asList(
            new Operation("back", null),
            new Operation("forward", null),
            new Operation("print", null)
        ));
        
        // Test case 3: Single page
        testCases.add(Arrays.asList(
            new Operation("visit", "page1"),
            new Operation("print", null),
            new Operation("back", null),
            new Operation("print", null),
            new Operation("forward", null),
            new Operation("print", null)
        ));
        
        // Test case 4: Multiple back/forward
        testCases.add(Arrays.asList(
            new Operation("visit", "page1"),
            new Operation("visit", "page2"),
            new Operation("visit", "page3"),
            new Operation("back", null),
            new Operation("back", null),
            new Operation("forward", null),
            new Operation("forward", null),
            new Operation("print", null)
        ));

        // Run test cases
        for (int i = 0; i < testCases.size(); i++) {
            System.out.println("Test case " + (i + 1) + ":");
            simulator.testBrowserHistory(testCases.get(i));
            System.out.println();
        }
    }
}

Output

Running the main method produces:

Test case 1:
Visited page1
Visited page2
Visited page3
History: page1 page2 page3
Navigated back to page3
History: page1 page2
Navigated forward to page3
History: page1 page2 page3

Test case 2:
Navigated back to null
Navigated forward to null
History: []

Test case 3:
Visited page1
History: page1
Navigated back to null
History: []
Navigated forward to page1
History: page1

Test case 4:
Visited page1
Visited page2
Visited page3
Navigated back to page3
Navigated back to page2
Navigated forward to page3
Navigated forward to page2
History: page1 page2

Explanation:

• Test case 1: Visits page1, page2, page3, prints "page1 page2 page3", goes back (removes page3), prints "page1 page2", goes forward (restores page3), prints "page1 page2 page3".
• Test case 2: Attempts back/forward on empty history, prints "null" and "[]".
• Test case 3: Visits page1, prints "page1", goes back (removes page1), prints "[]", goes forward (restores page1), prints "page1".
• Test case 4: Visits page1, page2, page3, goes back twice (removes page3, page2), goes forward twice (restores page3, page2), prints "page1 page2".

How It Works

• DoublyNode: Stores a string URL, a next pointer, and a prev pointer.
• BrowserHistory:
  • visit: Adds new node at tail, clears forward history, updates current.
  • back: Moves current to previous node, removes tail, stores URL for forward.
  • forward: Re-inserts last removed URL from forward list, updates current.
  • toString: Prints history from head to current, returns "[]" if empty.
• testBrowserHistory: Manages operations, uses forwardList to store back-navigated URLs.
• Example Trace (Test case 1):
  • visit("page1"): head=page1, current=page1.
  • visit("page2"): head=page1↔page2, current=page2.
  • visit("page3"): head=page1↔page2↔page3, current=page3.
  • print: "page1 page2 page3".
  • back: current=page2, forwardList=[page3], returns "page3".
  • print: "page1 page2".
  • forward: Re-inserts page3, current=page3, returns "page3".
  • print: "page1 page2 page3".
• Main Method: Tests normal navigation, empty history, single page, and multiple back/forward operations.

Complexity Analysis Table

Note:

• n is the number of nodes in the history.
• Time complexity: O(1) for visit, back, forward (constant-time operations); O(n) for toString (traverse to current).
• Space complexity: O(1) for visit, back, forward (constant pointers); O(n) for toString (StringBuilder) and forwardList storage.
• Worst case: O(n) time, O(n) space for output or forward history with large lists.

✅ Tip: Use a doubly linked list with a current pointer to efficiently manage browser history. Clear the forward history on new visits to simulate browser behavior accurately.

⚠ Warning: Maintain the current pointer and forward list correctly to avoid losing navigation history. Handle edge cases like empty history or no forward pages.