A few years ago, I was reviewing a colleague's code for a task scheduler. They were using a standard Ruby Array to manage a queue of pending jobs, and whenever a high-priority job came in, they used unshift to push it to the front. It worked fine in development, but once we hit production with thousands of concurrent tasks, the performance tanked. The problem is that arrays are contiguous blocks of memory; every time you unshift, Ruby has to physically move every other element in the array one slot to the right. It's a silent killer of performance. I spent an afternoon showing them how to implement a Linked List, and the "aha!" moment happened when they realized we could just change one pointer instead of shifting ten thousand elements.

Building the Node Foundation

To build a linked list, you first have to stop thinking about a "list" as a single container. Instead, think of it as a series of independent objects—Nodes—that happen to know who their neighbor is. In Ruby, this is straightforward. We create a Node class that holds two things: the actual data (the value) and a reference to the next node in the chain.

class Node
  attr_accessor :value, :next_node

  def initialize(value)
    @value = value
    @next_node = nil
  end
end

Notice that @next_node defaults to nil. This is crucial because the very last node in your list—the tail—has nowhere else to go. It's the "stop" sign for any loop traversing the list.

Orchestrating the List

Now we need a wrapper class to manage these nodes. The LinkedList class doesn't actually hold the data itself; it only needs to know where the list starts. We call this the head. If the head is nil, the list is empty. If you have a head, you have a thread to pull that leads you to every other piece of data in the sequence.

One of the biggest advantages here is how we handle insertions. To add an item to the front (the equivalent of unshift), we don't move existing data. We simply create a new node, tell it that its next_node is the current head, and then declare this new node as the new head.

class LinkedList
  attr_reader :head

  def initialize
    @head = nil
  end

  def prepend(value)
    new_node = Node.new(value)
    new_node.next_node = @head
    @head = new_node
  end

  def append(value)
    new_node = Node.new(value)
    
    if @head.nil?
      @head = new_node
      return
    end

    current = @head
    current = current.next_node while current.next_node
    current.next_node = new_node
  end
end

I'll be honest: append is slower than prepend in a singly linked list because you have to walk the entire chain to find the end. If you find yourself appending constantly, you might eventually want to keep a reference to a @tail node to make it an O(1) operation, but for now, let's keep it simple.

Traversing the Chain

Since you can't access a linked list element by index (like list[5]), you have to iterate. You start at the head and follow the next_node pointers until you hit nil. This is a classic pattern in software engineering: the "while" loop traversal.

class LinkedList
  # ... previous methods ...

  def print_list
    current = @head
    while current
      print "#{current.value} -> "
      current = current.next_node
    end
    puts "nil"
  end
end

# Usage:
list = LinkedList.new
list.append("Clean room")
list.append("Buy groceries")
list.prepend("Fix critical bug")
list.print_list 
# Output: Fix critical bug -> Clean room -> Buy groceries -> nil

It feels a bit primitive compared to Ruby's powerful Array methods, but understanding this structure is vital. It's the foundation for more complex structures like Queues, Stacks, and Graphs. You're no longer relying on the language's magic; you're managing memory references yourself.

📋 Practical Task

Exercise: Build a Music Playlist Sequencer

Imagine you are building a simple music player. You need a way to manage a queue of songs where you can easily add a "Next Up" song to the end of the list or "Jump the Queue" by adding a song to the very front.

Your task: Implement a Playlist class based on the Linked List logic learned in this lesson. Your class must include the following:

• A Node class to store the song title.
• A add_to_end(song_title) method to queue a song.
• A play_next(song_title) method that prepends a song to the front of the list.
• A show_queue method that prints the songs in the order they will be played, formatted as: "Playing: [Song A], Next: [Song B], Next: [Song C]..."

Test your implementation by adding three songs to the end and one song to the front, then printing the queue to verify the order.