- Using an Array as a Linked List
- Adding New Elements to a List – Shifting Array Elements
- Adding More Elements to a List – Resizing Array Capacity
- The Linked List as a Functional Data Structure
- Copy on Write Optimization in Ruby Arrays
- Implementing Your Own Linked List
- Frequently Asked Questions (FAQs) about Ruby’s Missing Data Structure
![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/linked-list2.png)
Using an Array as a Linked List
When I think of linked lists, I think of the Lisp programming language, short for “List Processor.” In his classic article, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, Lisp inventor John McCarthy defined the “cons cell” as the basic building block of linked lists, and a corresponding “(cons …)” Lisp function to create these cons cells. For example, to create a list (2, 3) in Lisp you would call:![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/lisp1b.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/list3b.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/unshift1.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/array1b.png)
Adding New Elements to a List – Shifting Array Elements
However, arrays and lists are very different things. Arrays are designed for random access of data across a large set, while linked lists instead work well inserting, removing or reordering elements. Let’s imagine that I want to add a third value to my list – in Lisp I just call “cons” again:![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/lisp2b.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/03/list2.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/unshift2.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/03/array2.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/push.png)
Adding More Elements to a List – Resizing Array Capacity
Now suppose I add a fourth element. In Lisp, I could continue to just call the “cons” function, adding more and more elements in precisely the same way. In Ruby, however, notice that my array has filled up and there’s no room for a fourth element:![](https://uploads.sitepoint.com/wp-content/uploads/2013/03/array3.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/array4b.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/push2.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/array5b.png)
The Linked List as a Functional Data Structure
So far, we’ve seen that Ruby arrays can function as linked lists. Ruby provides the push, unshift and insert methods to add a new element to a list, and the pop or shift methods to remove an element from a list. Not only that, with an array you also get direct, random access to all of the elements of the array, which a pure linked list structure can’t offer. The only downside with using an array as a linked list seems to be performance: if you had many 1000s of elements Ruby would theoretically slow down repeatedly resizing the array to accommodate all of the elements as you added them. Also, if you needed to add or remove elements to the head of the list or somewhere in the middle, then Ruby would also slow down shifting the remaining elements to the right or left. But remember, since Ruby is implemented with C internally, it is able to use very efficient C functions to move the elements around. Memmove and similar low level C functions are often implemented directly by the microprocessor hardware and work very, very quickly. However, there’s another important feature of linked lists which isn’t immediately apparent: they work nicely as functional data structures. What does this mean? In functional programming language such as Lisp, you specify your program as a series of “pure functions;” these are bits of code that always return the same output given the same input. Functional programming languages also discourage the use of “mutable values” – variables or objects that can change from one value to another in place. The primary benefit of using pure functions and immutable values is to allow your software to run more reliably and robustly since your code will have no side effects. Functional languages also work well in multithreaded environments since there’s no need to synchronize or lock code that modifies data – you just don’t modify data at all. Data structures that exclusively use immutable values are known as “functional data structures.” Aside from the large benefits of robustness and removing the need to synchronize access different threads, functional data structures also allow for data to be easily shared. Since you never modify data in place, it’s easy for many different functional data structures to use the same copy of data internally. The linked list is a great example of this: different lists can share the same “cons” cells or data values internally. For example, suppose in Lisp I create one list:![](https://uploads.sitepoint.com/wp-content/uploads/2013/03/list3.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/03/list4.png)
Copy on Write Optimization in Ruby Arrays
At first glance, it seems that using arrays as lists in Ruby makes space optimization impossible. In the first place, the array in Ruby is not a functional data structure – you can, of course, change any value in an array whenever you want. But let’s suppose, for a moment, that Ruby arrays were immutable – or that there was an “ImmutableArray” object in Ruby. How could two separate arrays even share the same data? For example, suppose I created an array with six elements:![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/array-cow1.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/array-cow2.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/array-cow3.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/array-cow4.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/array-cow5.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/array-cow6.png)
Implementing Your Own Linked List
To wrap things up today, let’s take a look at how you would actually implement a linked list in Ruby. As we’ve seen, arrays can often serve quite well as lists. Sometimes, however, you may actually need to repeatedly insert, remove and reorder elements in a large list. To avoid the performance penalties associated with array resizing and shifting, a real linked list might be what you need. One simple way to create linked list would be to use the Struct object to represent a cons cell, like this:![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/list1b.png)
![](https://uploads.sitepoint.com/wp-content/uploads/2013/04/list2b.png)
Frequently Asked Questions (FAQs) about Ruby’s Missing Data Structure
What is the difference between an Array and a Set in Ruby?
In Ruby, both Array and Set are used to store multiple values. However, they have some key differences. An Array is an ordered collection of objects, meaning that each element has a specific position or index in the Array. On the other hand, a Set is an unordered collection of unique elements. This means that a Set does not keep track of the order of elements and does not allow duplicate values. This makes Sets particularly useful when you need to quickly check if a collection includes a certain element, as Sets can do this much faster than Arrays.
How can I convert an Array to a Set in Ruby?
Converting an Array to a Set in Ruby is quite straightforward. You can use the to_set
method provided by the Set class. Here’s an example:require 'set'
array = [1, 2, 3, 4, 5]
set = array.to_set
In this code, we first require the ‘set’ library. Then we define an Array and convert it to a Set using the to_set
method.
Can I use a Set as a key in a Hash in Ruby?
No, you cannot use a Set as a key in a Hash in Ruby. This is because Hash keys in Ruby need to be immutable, meaning they cannot be changed once they are set. However, Sets in Ruby are mutable, meaning you can add, remove, or change elements in a Set. Therefore, Sets cannot be used as Hash keys in Ruby.
How can I add an element to a Set in Ruby?
You can add an element to a Set in Ruby using the add
method or the <<
operator. Here’s an example:set = Set.new
set.add("element")
# or
set << "element"
In this code, we first create a new Set. Then we add an element to the Set using the add
method or the <<
operator.
How can I remove an element from a Set in Ruby?
You can remove an element from a Set in Ruby using the delete
method. Here’s an example:set = Set.new(["element"])
set.delete("element")
In this code, we first create a new Set with an element. Then we remove the element from the Set using the delete
method.
How can I check if a Set includes a certain element in Ruby?
You can check if a Set includes a certain element in Ruby using the include?
method. Here’s an example:set = Set.new(["element"])
set.include?("element") # returns true
In this code, we first create a new Set with an element. Then we check if the Set includes the element using the include?
method.
How can I find the intersection of two Sets in Ruby?
You can find the intersection of two Sets in Ruby using the intersect?
method. Here’s an example:set1 = Set.new([1, 2, 3])
set2 = Set.new([2, 3, 4])
intersection = set1 & set2 # returns Set: {2, 3}
In this code, we first create two Sets. Then we find the intersection of the two Sets using the &
operator.
How can I find the union of two Sets in Ruby?
You can find the union of two Sets in Ruby using the union
method or the |
operator. Here’s an example:set1 = Set.new([1, 2, 3])
set2 = Set.new([2, 3, 4])
union = set1 | set2 # returns Set: {1, 2, 3, 4}
In this code, we first create two Sets. Then we find the union of the two Sets using the |
operator.
How can I find the difference between two Sets in Ruby?
You can find the difference between two Sets in Ruby using the -
operator. Here’s an example:set1 = Set.new([1, 2, 3])
set2 = Set.new([2, 3, 4])
difference = set1 - set2 # returns Set: {1}
In this code, we first create two Sets. Then we find the difference between the two Sets using the -
operator.
How can I iterate over a Set in Ruby?
You can iterate over a Set in Ruby using the each
method, just like you would with an Array. Here’s an example:set = Set.new([1, 2, 3])
set.each do |element|
puts element
end
In this code, we first create a new Set. Then we iterate over the Set using the each
method and print each element.
Pat Shaughnessy writes a blog about Ruby development and recently self-published an eBook called Ruby Under a Microscope. When he's not at the keyboard, Pat enjoys spending time with his wife and two kids. Pat is also a fluent Spanish speaker and travels frequently to Spain to visit his wife's family.