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!

You can get the source code from here.

Next time, circular linked lists.

Thanks for reading! and stay tuned.

PS: Don’t forget to clap if you like this post :)

PS2: If you are a member of the Kindle Unlimited program, you can read a bit polished version of this series for free on your Kindle device.

Data Structures From Scratch — Ruby Edition.