Mastering data structures in Ruby — Doubly linked lists

The main difference between single and doubly linked lists is that in the later each element holds a pointer to the element that precedes it. This allows us to traverse the list from tail to head and remove elements in constant time.

If you haven’t read my previous post on singly linked lists, I recommend you to do so, because this time we are going to work on top of what we built last time.

On doubly linked lists elements are represented by nodes that contain three attributes:

• The value that the element holds.
• A pointer to the next node in the list.
• A pointer to the previous node in the list.

As well as with singly linked lists, the first element of the list is called “head” and the last one is called “tail”.

The boundaries of doubly linked lists are delimited by the previous pointer of the first element and the next pointer of the last one. Both pointers must be set to nil.

X <-[prev|data|next] <-> [prev|data|next] <-> [prev|data|next] -> X

As far as the complexity of operations concerns, singly and doubly linked lists perform almost the same, the only difference lays in the remove method. Since in doubly linked list each node holds a pointer to the previous node, removals are O(1).

* Note: If you are not familiar with Big O notation or don’t know for sure what “complexity of operations” means, you may want to check my previous post where I glossed over these concepts.

Doubly linked lists interface

If you take a look at the table below, you will notice that the interface definition for doubly linked lists it’s almost the same as the one for singly linked lists. This is good news for us because since we are going to create doubly linked list extending singly linked ones, most of the code is already done 

(The methods we have to add or override are highlighted in bold text ).

To avoid repeating myself (and waste your time while doing so), I’m not going to include details about methods inherited from the singly linked list because you can see those in the previous post. I will concentrate on doubly linked lists, only.

Insert

Creates a new node to insert a value into the list. If the list has no nodes, the new node becomes the head of the list; otherwise, it’s appended at the tail of the list.

Since the list keeps pointers to its head and its tail, the complexity of this method is O(1).

Note that when the list contains elements we have to set the previous pointer of the node we are about to insert to point to the tail of the list.

def insert data
  node = Node.new data
  unless head 
    self.head = node
  else
    node.prev = self.tail
    self.tail.next = node 
  end
  self.tail = node
  self.length += 1
end

Remove

Removes the given node from the linked list and adjusts pointers to keep the elements together.

If the node we have to remove is the head of the list, we need to cover two situations:

1. Head is the only node in the list. We set head and tail to nil and we are done.
2. Head is not the only node in the list. The node that’s next to head becomes the new head and the original head goes out of scope.

If the node we have to remove is not at the head of the list, we only need to adjust to pointers to left the target node out of scope. First, we have to set the next pointer of the node that precedes the target node to point to the node that is next to the target. Second, we have to set the previous pointer of the node that is next to the target node to point to the node that precedes it.

As it happens with almost all of the methods on doubly linked lists, a piece of code is worth a thousand words. So, let’s check the code instead.

def remove node
  return nil unless node
  if node == head
    if head.next.nil?
      self.head = self.tail = nil
    else
      self.head = self.head.next
    end
  else
    p = node.prev
    n = node.next 
    p&.next = n
    n&.prev = p
  end
  self.length -= 1
end

In case you didn’t notice it, this time we didn’t have to walk the list to find the node that precedes the element that we want to remove and hence this operation O(1).

Cat

This method allows us two join two lists together and it’s divided into 4 steps:

1. Point the previous pointer of the head of the list we are appending to the tail of the current list.
2. Point the next pointer of the tail of the current list to the head of the list we are appending.
3. Set the tail of the current list to the tail of the list we are appending.
4. Adjust current list length.

The complexity of this method is O(1).

def cat list
  return nil unless list
  
  list.head.prev = self.tail
  self.tail.next = list.head
  self.tail      = list.tail
  self.length += list.length
end

Find Last

This method allows us to get the last element of the list that satisfies a given predicate. (Or the first occurrence starting from the tail.)

The way we find the last element is by walking the list from tail to head applying the predicate to each element until the result of that operation is true or the list gets exhausted.

The complexity of this method is O(n) because we may have to walk the whole list.

def find_last &predicate
  return nil unless block_given?
  current = self.tail
  while current
    return current if predicate.call(current)
    current = current.prev
  end
end

To see this method in action, suppose you have a list of numbers and you want to find the last occurrence of the number 3.

As well as we did with singly linked lists, let’s try the “rudimentary” way first:

e = nil
current = list.tail
while current
  if current.data == 3
    e = current.data
    break
  end
  current = current.prev
end

Now, the elegant and Ruby “idiomatic” way:

e = list.find_last { |item| item.data == 3; }

Reverse Each

This method traverses the list from tail to head yielding one item at a time until it reaches the end of the list.

Unsurprisingly, the implementation of this method is similar to what we did with singly linked lists; the difference is that in this case instead of starting from to the head of the list we start from the tail and move backward until the current node is nil.

• The complexity to yield the previous element is O(1).
• The complexity to yield the whole list is O(n).

def reverse_each
  return nil unless block_given?
  current = self.tail
  while current
    yield current
    current = current.prev
  end
end

Reverse Print

This method prints the contents of the current list backward.

def reverse_print
  if self.length == 0
    puts "empty"
  else
    self.reverse_each { |item| puts item.data }
  end
end

When to use doubly linked lists

Doubly linked lists work great when you have to move back and forth over a (small) sequence of elements without wraparound.

For instance, the frame manager of a video editing app where the user can move back and forth (frame by frame) from the start to the movie to the end, could be a good fit for this data structure.

And last but not least, since removals are O(1), doubly linked lists could be a good choice for those cases where you have to handle lots of delete operations.

So, that’s about it for doubly linked lists. I hope you enjoyed it!
Next time, Circulary Linked Lists. Stay tunned!

Thanks for reading!