Linked Lists and How to Implement Them in Ruby

Linked lists are the foundation of other data structures and can be used to create stacks, queues, and more. They can be very efficient when used correctly and can also be inefficient when used incorrectly. Random access is very expensive for a Linked List.

A linked list is a collection of data where each data is contained in a node and this node points to the next node. In Ruby, we will have two classes. A Node class that holds the data and reference to the next Node, and a LinkedList class that holds a reference to the first node and methods for inserting/deleting/traversing the entire list.

Here is a model of a node. The data (‘data’ attribute) can be any object and the pointer (‘next’ attribute) can be any other node.

The LinkedList class is a collection of all of the nodes. All that the LinkedList class needs to track is the first element (‘first’ attribute). The relation between each node after that is stored on the node (in the ‘next’ attribute). This tutorial will use a singly-linked list. This means that each node only points to the next node, whereas a doubly-linked list would also point to the preceding node. For this reason, given a node, we can only find what comes after it, since no reference points to the node before it.

Here is how we define the LinkedList class. Its very simple, all it needs is a getter method for ‘first’.

Accessing Data in a Linked List (non-destructive)

Linked lists do not have indices like arrays, nor does it have keys like hashes. The only way to access data is to chain ‘.next’s starting at ‘first’. For example, if you wanted the third element of LinkedList ll, you would find it by using ‘ll.first.next.next’.

Here we create a pointer named ‘current’. This is just like the ‘Node.next’ or ‘LinkedList.first’ pointer, it is just a way to keep track of a node. Current is changed to ‘current.next’ until either the list is traversed or the data is found.

Finding the last element is as easy as going from ‘first’ to ‘next’ to ‘next’ etc., until there is no ‘next’ left.

Adding Data

Data can be added to the front (unshift), or added to the back (push). Note that these methods are just like the array methods native to Ruby.

Here is a model of ‘unshifting’ object ‘D’ to a linked list with elements (in order) ‘A’, ‘B’, and ‘C’:

And here is how we do that in Ruby:

Adding to the front (unshifting) means that this node should be the new first node. A new node is created with the data and assigned to ‘front’. This ‘node.next’ now becomes the original ‘first’ node.

Adding to the back (popping) means that the last node should now point to this new Node:

Inserting after a node of given data is fairly straightforward. Inserting before a node is more complex, but not by much.

To insert after, search until ‘current.next’ is the data you are looking for. Then make ‘current’ point to the new node, and the new node point at current.next. After refactoring, #find has the job of finding the correct element.

To insert before, you must keep ‘current’ one ‘next’ behind. Remember that you cannot reference a node behind a node, so if you want to insert something before a certain node, you need to keep track of the node before the one that you are looking for. You are doing the same as #insert_after, but you are tracking the node before the desired node, while searching ‘.next’ for the data.

Removing Data

To shift is the opposite of unshift (removes the first element and returns it), and to pop is the opposite of push (removes the last element and returns it).

Shift sets ‘first’ to ‘first.next’, and returns the original first node. Pop traverses the list until there is no node two steps ahead of ‘current’. This is similar to #insert_before in the sense that the element before the element we need needs to be tracked. The reason we are chaining ‘.next’ twice is because we really need to keep track of three nodes:

• current: the node before last element (we will set this to nil to ‘delete’ the node)
• current.next: the last node in the list, we are returning this node
• current.next.next: what is the last node pointing at? If any node is pointing at nil, then that node is the last node.

Other Methods

To create an array from a linked list, just traverse the array, shoveling the data from each node into an array.

Final Thoughts

The methods included are not exhaustive. Many other useful methods can be added as you see fit. You can view my repo in full on GitHub.