The Rambling Programmer

Linked Lists

Data Structures & Algorithms

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.

https://github.com/SYoung82/linked-lists

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.

class Node
  attr_accessor :value, :next, :prev

  def initialize(value)
    @value = value
  end
end

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.

class LinkedList
  attr_accessor :head

  def initialize(headNode = nil)
    @head = headNode
  end
end

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 LinkedList.new() to create a new linked list whose head points to nothing. Or, we can do something like, LinkedList.new(Node.new(1)) 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.

def insertTail(node)
  currentNode = @head

  if currentNode == nil
    @head = node
    return self
  end

  while currentNode.next != nil
    currentNode = currentNode.next
  end

  currentNode.next = node
  return self
end

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 currentNode.next 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, https://github.com/SYoung82/linked-lists/blob/master/linked_list.rb.

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, https://github.com/SYoung82/linked-lists/blob/master/linked_list.rb. 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.

https://en.wikipedia.org/wiki/Linked_list

http://www.geeksforgeeks.org/data-structures/linked-list/

MmmMmm, I'm loving it!

Posted by Scott over 7 years ago