We've already covered singly linked lists, but they have a glaring limitation: they're a one-way street. If you're at the end of the list and want to see the previous element, you're out of luck unless you start all the way back at the head. In the real world, we often need to traverse in both directions. Think of your browser's back and forward buttons—that's a classic Doubly Linked List (DLL) use case.

Let's build a simple BrowserHistory manager. We want to be able to visit new pages, go back a few steps, and then move forward again.

Defining the bidirectional node

First, we need a node that knows about both its successor and its predecessor. I usually keep the node class as slim as possible. It doesn't need any logic; it just needs to hold data and two pointers.

class PageNode:
    def __init__(self, url):
        self.url = url
        self.next = None
        self.prev = None

Now we can build the main manager. I'll track the current page specifically, because in a browser, the "active" page isn't always the most recent one you visited—it depends on how many times you've hit the back button.

Navigating the history chain

I'll start by implementing the visit and back methods. The idea is that every time we visit a new page, we attach it to the current node and shift our focus forward.

class BrowserHistory:
    def __init__(self, homepage):
        self.current = PageNode(homepage)

    def visit(self, url):
        new_page = PageNode(url)
        self.current.next = new_page
        new_page.prev = self.current
        self.current = new_page

    def back(self, steps):
        while steps > 0 and self.current.prev:
            self.current = self.current.prev
            steps -= 1
        return self.current.url

    def forward(self, steps):
        while steps > 0 and self.current.next:
            self.current = self.current.next
            steps -= 1
        return self.current.url

Fixing the "Ghost History" bug

I just noticed a problem. If I visit Page A, then Page B, then go back() to Page A, and then visit Page C... my current code just attaches Page C to Page A. But Page B is still hanging out there in memory as Page A's next. In a real browser, if you go back and then visit a new site, you effectively "wipe" the forward history. My visit method is currently ignoring that.

I need to make sure that when we visit a new page, we explicitly break the link to any existing "forward" pages. Here is the correction:

    def visit(self, url):
        new_page = PageNode(url)
        # The fix: we don't just link; we overwrite any existing 'next'
        self.current.next = new_page
        new_page.prev = self.current
        
        # Now the old forward chain is orphaned and will be garbage collected
        self.current = new_page

It looks like the same code, but the mental shift is important: self.current.next = new_page doesn't just add a link; it destroys the path to everything that used to come after the current node. That's exactly what we want for a browser history.

Testing the flow

If we run this, we can see the bidirectional movement in action. We can jump back and forth, and the prev and next pointers handle the heavy lifting without us needing to manage an array or a list of indices.

history = BrowserHistory("google.com")
history.visit("github.com")
history.visit("stackoverflow.com")
print(history.back(1))    # Output: github.com
print(history.back(1))    # Output: google.com
print(history.forward(1)) # Output: github.com
history.visit("python.org") # This wipes stackoverflow.com
print(history.forward(1)) # Nothing happens, we are at the end
print(history.current.url) # Output: python.org

The beauty of the DLL here is that back and forward are extremely efficient. We aren't shifting elements in an array; we're just sliding a pointer along a chain.

---

📋 Practical Task

Implementing a Music Playlist Navigator

You are building a music player. Unlike a browser history, a playlist is often a "Circular Doubly Linked List"—meaning the last song points back to the first, and the first song points back to the last.

Your Task: Implement a Playlist class. It should have:

• A add_song(song_name) method that adds a song to the end of the list.
• A next_song() method that moves to the next song (and wraps around to the start if at the end).
• A prev_song() method that moves to the previous song (and wraps around to the end if at the start).

Ensure that your add_song method correctly maintains the circular links between the head and the tail of the list. Test it by adding three songs and calling next_song() four times to see if it wraps around correctly.