If you've already spent some time with singly linked lists, you know the drill: you have a head pointer, and you follow the breadcrumbs to the end. But the moment I've seen developers struggle is when they realize they need to go backward. Imagine we're building a browser history manager. You can't just have a "Forward" button if your data structure only knows how to look ahead; you need a way to retreat to the previous page without traversing the entire list from the start.

The chaos of manual pointer wiring

The naive way to approach a doubly linked list is to treat it as a collection of loose nodes that you wire up manually in your main logic. I've seen this a lot in early academic projects. You create a Node struct with next and prev pointers, and then you write a bunch of messy if statements in your main() function to handle the connections. It looks something like this:

struct Node {
    std::string url;
    Node* next = nullptr;
    Node* prev = nullptr;
};

// Naive manual wiring
Node* page1 = new Node{"google.com"};
Node* page2 = new Node{"github.com"};
page1->next = page2;
page2->prev = page1;

This feels fine when you have two nodes. It feels okay when you have three. But the moment you try to delete a node from the middle of the list or clear the history, you're in for a world of hurt. You have to remember to update the next pointer of the previous node AND the prev pointer of the next node. If you miss one, you've created a "ghost" reference, and your program will likely crash the next time you try to navigate backward. Plus, who is responsible for calling delete? If you're just passing pointers around, you'll almost certainly leak memory.

Encapsulating the boundary dance

The professional way to handle this is to hide that "pointer dance" inside a manager class. You shouldn't be touching next and prev in your business logic; you should be calling push_back() or pop_front(). The real challenge here isn't the middle of the list—it's the edges. When you add the very first element, both the head and the tail point to the same thing. When you remove the last remaining element, both become nullptr.

I prefer to handle these boundary conditions explicitly. Instead of writing a generic "insert" function and then trying to fix the edges with a dozen if statements, I separate the logic. Here is how I'd structure the core of the list to ensure the tail is always tracked, making "backward" navigation O(1) instead of O(n):

class BrowserHistory {
    struct Node {
        std::string url;
        Node *next, *prev;
        Node(std::string u) : url(u), next(nullptr), prev(nullptr) {}
    };

    Node *head = nullptr, *tail = nullptr;

public:
    void visit(std::string url) {
        Node* newNode = new Node(url);
        if (!head) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
    }

    ~BrowserHistory() {
        Node* current = head;
        while (current) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }
};

The cost of the extra pointer

You might wonder if the extra prev pointer is actually worth it. In a 64-bit system, every pointer is 8 bytes. If you have a million small nodes, that's an extra 8MB of RAM. For a browser history or a music playlist, that's a rounding error. But if you're working in a deeply embedded environment with only a few kilobytes of SRAM, that's a significant trade-off. However, for almost every other software engineering use case, the ability to traverse backward and delete nodes in constant time far outweighs the memory cost.

The most critical part of the code above is the destructor. In a singly linked list, you just go forward and delete. In a doubly linked list, it's the same, but you have to be careful not to access a node's prev pointer after you've already deleted the node it points to. Always capture the next pointer in a temporary variable before calling delete on the current node.

📋 Practical Task

Implementing Browser History Navigation

You have been provided with the BrowserHistory class skeleton from the lesson. Your task is to implement two specific member functions: std::string goBack() and std::string goForward().

To do this, you will need to add a Node* current pointer to the class to track which page the user is currently viewing.

• goBack(): Should move the current pointer to the previous node and return the URL. If there is no previous page, it should return "START_OF_HISTORY".
• goForward(): Should move the current pointer to the next node and return the URL. If there is no next page, it should return "END_OF_HISTORY".
• Requirement: Ensure that calling visit() updates the current pointer to the newly added page.

Test your implementation by visiting "google.com", "github.com", and "stackoverflow.com", then navigating back twice and forward once to ensure the pointers are updating correctly.