Ruby’s Missing Data Structure

Have you ever noticed Ruby doesn’t include support for linked lists? Most computer science textbooks are filled with algorithms, examples and exercises based on linked lists: inserting or removing elements, sorting lists, reversing lists, etc. Strangely, however, there is no linked list object in Ruby.

Recently after studying Haskell and Lisp for a couple of months, I returned to Ruby and tried to use some of the functional programming ideas I had learned about. But how do I create a list in Ruby? How do I add or remove an element from a list in Ruby? Ruby contains fast, internal C implementations of the Array and Hash classes, and in the standard library you can find Ruby code implementing the Set, Matrix, and Vector classes among many other things. But no linked lists – why?

The answer is simple: Matz included features you would normally associate with linked lists in the Ruby Array class. For example, you can use Array#push and Array#unshift to add an element to an array, or Array#pop and Array#shift to remove an element from an array.

Today on RubySource.com I wrote about a few common operations you would normally use a linked list for, and then took a look at how you would implement them using an array. I also looked into how Ruby’s array object works internally.