Reversing a Linked List in Ruby

2012-12-23

Feeling pretty good about my last exercise with C and reversing a linked list, I showed my code to a C veteran. Long story short, the old school guys know a ton of good stuff. Although the algorithm from my last post worked, it was most definitely not the best way to solve the problem. As a follow up, I decided to refactor my code and switch languages, this time using Ruby.

Aside from the various details involved in moving from a procedural to an object-oriented paradigm, the biggest change is how I've handled common list operations. The aforesaid C veteran advised me to write three simple functions: one for 1) putting an entry at the top of the list, 2) putting an entry at the bottom of the list, and 3) removing an entry from the top of the list. In effect, the idea is to implement common stack and queue behavior. The result makes manipulating the list much easier.

In what follows, I'm going to walk through my current implementation of a linked list in Ruby. Then, I'll explain how to reverse that list both destructively and non-destructively.

First, we start with code for a list entry.

class Entry
  attr_accessor :next, :data

  def initialize(data)
    @next = nil
    @data = data
  end
end

The next variable will be a pointer to the following entry in the list. For demonstration purposes, I've also included a data variable, which as the name suggests holds data within each entry. We won't concern ourselves with the data aspect of the linked list for now.

Our list will take the form of a class called List.

class List
  attr_accessor :name

  def initialize
    @head = nil
    @tail = nil
  end
end

For convenience sake, I've included a variable to keep track of the list's name. More importantly, though, we start off with a head and tail pointer set to nil. Unlike my last implementation which exposed the head and tail pointers, this time we'll make @head and @tail accessible only to other methods within the class. In other words, there will not be a setter or a getter for either variable.

Now that we have a basic setup, the next step is to add the three methods named above: 1) adding to the top of a list, 2) adding to the bottom of the list, and 3) removing from the top of a list. There are likely more idiomatic names in Ruby for these methods, but here I choose to follow the C veteran and use ptq ("put on top of queue"), pbq ("put on bottom of queue"), and rtq ("remove from top of queue").

We'll start with ptq.

def ptq(entry)
  if @head.nil?
    @head = entry
    @tail = entry
  else
    entry.next = @head
    @head = entry
  end
end

The implementation for ptq is fairly straightforward. We have two states to consider: 1) the head pointer is set to nil, or 2) the head pointer holds an entry. In the first case, we simply assign our new entry to @head and @tail. Because the new method on Entry has already assigned entry.next to nil, we have nothing more to do in this case. The linked list is terminated with the present entry.

In the second case, i.e., we already have some number of entries in the list, we first have our new entry to point to the list's current head. The next step is simply to move the @head pointer to point to the new entry. Now we have a working ptq.

The implementation of pbq follows much the same logic.

def pbq(entry)
  if @head.nil?
    @head = entry
    @tail = entry
  else
    @tail.next = entry
    @tail = entry
  end
end

First, we deal with the situation when there isn't an entry pointed to by @head, just as above. In the second situation, i.e., a number of entries already exist in the list, we simply have @tail.next point to our new entry, and then reassign @tail to point to the new entry. Done.

Before getting to our destructive and non-destructive reverse methods, there is one more important function to deal with: rtq. The function here will remove an entry from the top of the list and return the entry.

def rtq
  return nil if @head.nil?
  entry = @head
  @head = @head.next
  return entry
end

If nothing exists in the list, we will return nil. Otherwise, we grab ahold of the head entry, set @head to point to the next entry in the list, and then return the old head entry.

Now that we have the means to build a linked list, we're ready to implement a non-destructive and destructive reverse method. The destructive method is the more challenging one, so let's start with that.

Following the Ruby idiom, we'll name the method reverse!. The basic idea behind reverse! is that we'll pop all the entries of the current list and put them on a stack. Once we have all the entries on the stack, we'll just assign @head to the top entry on the stack, which will have been the old @tail.

def reverse!
  return if @head.nil?

  @tmp_head = self.rtq
  @tmp_head.next = nil
  @tail = @tmp_head

  until @head.nil?
    entry = self.rtq
    entry.next = @tmp_head
    @tmp_head = entry
  end

  @head = @tmp_head
end

If the reverse! method is called on an empty list, we'll return nil. Otherwise, we start by popping the top entry off the current list and assigning it to @tmp_head. We then reassign the next pointer of that entry to nil. This next pointer will terminate the reversed list and so we assign @tail to the same entry.

The next until loop is at the heart of the reverse! method. We'll pop an entry off the current list and assign its next pointer to the entry in @tmp_head. Each time through the loop @tmp_head will point to the entry which used to precede the current entry. By reassigning next to @tmp_head, we're basically reversing the thread of the linked list. Once we have that thread reversed between two entries, we move @tmp_head in preparation for the next time through the loop.

The loop will continue until we empty the list. Once that happens, we only have to reassign @head to the entry in @tmp_head. Now we've destructively reversed the linked list.

Reversing the linked list non-destructively is much simpler by comparison, especially since we've implemented ptq above. We'll create a new list, iterate over the old one, while pushing each entry onto the top of the new list. The result will be a new list, with the order of entries reversed. Assigning a sequence of numbers to the data attribute of Entry above is a good way to confirm that reverse does in fact work.

Before we can proceed, though, we need to implement the each method in our List class. We start by including Enumerable within our class.

include Enumerable

def each
  return nil if @head.nil?
  entry = @head
  until entry.nil?
    yield entry
    entry = entry.next
  end
end

After making sure we don't have an empty list, the each method starts with @head and spits out an entry. Then, it moves to the next entry and repeats. Once we've reached nil, we're at the end of the list, and each is done with its enumeration.

We're almost done. The non-destructive reverse is as follows:

def reverse
  new_list = List.new
  self.each { |entry| new_list.ptq(Entry.new(entry.data)) }
  return new_list
end

We make a new list, copy all the data in the old list to the new, and then return the new list. Finally, we're done.

After having done this exercise twice, once in C and now once in Ruby, it's perfectly clear that functions like ptq, pbq, and rtq are what makes the process dramatically easier. Rather than trying to do gymnastics with pointers, it's much simpler to implement stack-like and queue-like behavior. Reversing a linked list becomes simply a manipulation of those basic functions.