How do I actually structure the Node class so it knows about both directions?

In a singly linked list, you only care about what comes next. But for a doubly linked list, each node needs to be "aware" of its neighbor on both sides. I always recommend keeping the Node as a dead-simple data object. It shouldn't contain any logic for managing the list; it just holds the value and the pointers.

class Node
  attr_accessor :value, :next, :prev

  def initialize(value)
    @value = value
    @next = nil
    @prev = nil
  end
end

By using attr_accessor, we make it easy to "stitch" nodes together later. When you're starting out, it's easy to forget to initialize these to nil, but being explicit here saves you from head-scratching debugging sessions when you hit the end of your list.

What's the trick to handling the head and tail without crashing?

The biggest headache with linked lists is the "edge case"—specifically, when the list is empty or only has one item. To handle this, I wrap the nodes in a DoublyLinkedList class that keeps track of both the @head (the start) and the @tail (the end).

When you append a node, you aren't just updating the next pointer of the old tail; you're also updating the prev pointer of the new node. Here is how I usually handle the push logic:

class DoublyLinkedList
  attr_reader :head, :tail

  def initialize
    @head = nil
    @tail = nil
  end

  def push(value)
    new_node = Node.new(value)

    if @head.nil?
      @head = new_node
      @tail = new_node
    else
      new_node.prev = @tail
      @tail.next = new_node
      @tail = new_node
    end
  end
end

Notice that if @head.nil? check. Without that, you'd be trying to call .next on a nil object, and Ruby will throw a NoMethodError immediately. Always account for the "empty list" state first.

How do I handle the "stitching" logic when deleting a node from the middle?

This is where the doubly linked list really shines over the singly linked version. If you have a reference to a node, you don't have to traverse the entire list from the start to find the element before it—the node already knows who its predecessor is.

Imagine you're building a music playlist and you want to remove a song from the middle. You just need to tell the previous node to skip over the current one and point to the next one, and vice versa. It's like removing a link from a physical chain and snapping the two remaining ends together.

def delete(node)
  return if node.nil?

  # Patch the node before the one being deleted
  node.prev.next = node.next if node.prev

  # Patch the node after the one being deleted
  node.next.prev = node.prev if node.next

  # Update head or tail if we deleted the boundaries
  @head = node.next if node == @head
  @tail = node.prev if node == @tail
end

I'll be honest: the first time I wrote this, I forgot to update the @head and @tail pointers. My list seemed to work, but as soon as I tried to append a new item, the whole thing collapsed because the @tail was still pointing to a node I had "deleted." Always double-check your boundary updates.

Why bother with this when Ruby Arrays are so powerful?

You're probably thinking, "Why am I doing this when I can just use Array#push or Array#shift?" In a high-level language like Ruby, you rarely need to build your own linked list for production code. However, the performance characteristics are fundamentally different.

When you remove the first element of a massive Ruby Array using shift, Ruby has to re-index every single remaining element in that array. That's an O(n) operation. In a doubly linked list, removing the head is O(1)—you just move the head pointer. If you're building something like a LRU (Least Recently Used) cache or a complex undo/redo system where you're constantly adding and removing from both ends, the linked list is an absolute beast compared to an array.

📋 Practical Task

Exercise: Build a Browser History Navigator

Your task is to implement a BrowserHistory class using the DoublyLinkedList and Node concepts from this lesson. This class should simulate how a web browser handles the "Back" and "Forward" buttons.

• Create a BrowserHistory class that maintains a pointer to the current_page (a Node).
• Implement a method visit(url): This should add a new page to the end of the list and move the current_page pointer to this new page. Crucial: If the user was in the middle of their history (they hit "Back" a few times) and then visits a new page, all "forward" history after the current page should be deleted.
• Implement a method back(): This should move the current_page pointer to the previous node and return the URL. Return nil if no previous page exists.
• Implement a method forward(): This should move the current_page pointer to the next node and return the URL. Return nil if no next page exists.
• Implement a method current_url(): Return the URL of the page the user is currently on.

Test your implementation by visiting "google.com", "github.com", and "ruby-lang.org", then going back twice, visiting "stackoverflow.com", and ensuring that you can no longer go "forward" to "ruby-lang.org".