Linked Lists

So far in our journey to better understand data structures and algorithms from a web developer’s perspective we have been focusing mostly on some basic sorting algorithms, namely insertion and merge sorts. It’s time to shift gears away from the pure algorithms and have a look at some data structures and the algorithms associated with them.

As web developers we use data structures daily, usually arrays, because, well, they are easy to use and provided to us as built in data structures in nearly every language. In this post, however, we are going to take a look at a another basic data structure, the linked list. As a matter of fact, a good understanding of linked lists is critical, from it we can build implementations of arrays, stacks, queues, etc… The node of a linked list is also the fundamental piece in more complex structures like trees. Clearly, the linked list is fundamental to computer science so lets get started.

A complete Doubly Linked List implementation in Ruby can be found at the repo below. Although in this article we will be discussing Singly Linked Lists, you can see just how simple it is to make a Double Linked List by simply adding a prev pointer.

What is a linked list? It is, very simply, a linear collection of elements (nodes). The most basic linked list node consists of two pieces of information, data, and a reference to the next node in the sequence. More complex versions of the linked list, such as the doubly linked list, require nodes to have more information. See the image below.

Fairly simple, right? Let’s take a look at how we might implement a node in Ruby.

That’s it, really! We created a Node class that has both a value, which we set on initialization of an instance of the node, and a pointer called next, which will point to the next node, if it exists.

In order to manipulate a collection of these nodes we have to have an initial pointer that points to the first node. We typically call this pointer head. Keeping that in mind, let’s look at an implementation of a Linked List class in Ruby.

Again, that really is it! We create a new LinkedList class which has one attribute, it’s head, which we set to nil if it’s not provided on construction of the instance. So we can say to create a new linked list whose head points to nothing. Or, we can do something like, to create a new LinkedList whose head points to a Node whose value is 1. Cool!

That’s great and all but a data structure with no algorithms is pretty much useless. So lets create the first one to get you pointed in the right direction. We definitely need the ability to append to the list of nodes. How do we do that though with only a reference to the head node? Well, we pretty much just walk our way down the list until we reach the Node whose next is not pointing to another node and attach our new node.

So we create a pointer, currentNode, which we use as a pointer to walk through the list until we find the Node whose next == nil then we set to the newNode that was passed in to the method. We could also implement methods to insert a Node at the beginning of the list or after a particular node. I’ll leave those up to you, you can see solutions here,

There are numerous other methods you might be asked to implement for a linked list including delete and search. They will all use a variation of the algorithm above, in which, you walk the list looking for an element or the end, and then modify a pointer or return a node as required. I encourage you to try these out on your own. If you have any trouble you can see one possible solution here, Note that this implementation is a doubly linked list, although the algorithms are essentially the same.

There are a few advantages to using a linked list over an array. Most commonly cited is the fact that a linked list dynamically increases or decreases memory usage with the addition or subtraction of nodes. Arrays on the other hand, typically require more space than is necessary to avoid having to resize every time a new element is added.

Below are a few links concerning Linked Lists a little bit more in depth. Until next time.