More fun with linked lists: implementing each and sort

A little while ago I posted about my indulgent use of a linked list in a Ruby on Rails project I’m working on. The list allowed me to define the linked objects’ methods in the recursive case analysis style I’ve learned from programming in Scheme. I wrote that I was surprised that this decision hasn’t felt unnatural and has proven fairly easy to build upon. Each object in the list is also the head of the remainder of list (from that object to the end), so you can call methods on that single object and all the recursion necessary to find the information you want is abstracted behind the object’s interface.

Today I got a few minutes to play around with an idea I had while on vacation: implementing an each method on the grade range class so that I can include the Enumerable module, in case I wanted to use Ruby’s rich set of functional structures on the list. It turns out to be a piece of cake!

My grade range object has as an instance variable @nxt, a reference to the next object in the list. So implementing each is only a matter of setting a pointer that can be moved down the linked list.

def each
  i = self
  while i != nil
    yield i
    i = i.nxt

There’s no need to set up an iterator object, as I’ve seen in some implementations of each for collections classes, because the concept of iteration/recursion is already in the linked list’s structure.

The great thing about having an each method is that now we get nearly all of Ruby’s Enumerable module’s methods as mixins just by including the method: they’re based on each.

range.collect{|r| r.min_number_grade}
=> [98, 92, 90, 88, 82, 80, 78, 72, 70, 60, 0]

I don’t get all the Enumerable methods by implementing each. To get max, min, and sort, I need a spaceship operator, <=>. How about sorting by minimum number score?

def <=>(other)
  self.min_number_grade <=> other.min_number_grade

This will make it even simpler to sort a list of grades prior to linking them. But here is an interesting wrinkle. Once the list is sorted and linked, the objects that would be returned by max and min are already in known positions: the head and the tail of the linked list. And sorting the list would be a strange exercise. I’ll look into these nuances next.