Mastering data structures in Ruby — Circular linked lists
The defining factor for circular linked lists is that they allow us to traverse them infinitely. Since they had no tail, whenever a list reaches its “end” it wraps around and restarts from its head over and over again.
Circular lists can be singly or doubly linked, and like their closest relatives, they are just sequences of connected nodes.
If you haven’t read my previous posts on this series, I recommend you to do so because in this post I’m going to gloss over some important concepts that were discussed thoroughly on previous posts.
As I was saying, circular lists can be, singly or doubly linked. This time, I’m going to build a singly linked one. However, if you have to implement a circular list that supports backward navigation, you will be able to do so by combining the contents of this post with what I’ve shown you previously on mastering doubly linked lists.
The elements in our list will have two attributes.
- The value that the element holds.
- A pointer to next node.
In contrast to what happens with regular linked lists, circular lists have no hard boundaries. Let’s say that since they have no tail, you can’t tell where they end. (Of course, you can, but bear with me.)
+--> [data|next] -> [data|next] -> [data|next] ---+| |+-------------------------------------------------+
Circular linked lists interface
As opposed to what I did with doubly linked lists, this time instead of extending singly linked lists I’m going to start from scratch and reshape the interface a little bit.
I’m not doing that because I like to waste keystrokes, but because there are some methods from regular linked lists that make no sense on circular linked ones. For instance, it’ll be natural for a Ruby programmer to make calls to “each” method to traverse a list. The problem is that on circular linked lists traversals run indefinitely so those calls would end up blowing the stack.
Using a bang sign (!) at the end of the method name is a widely used Ruby convention to indicate that the method is dangerous. Maybe using such a convention would have been another way to go. However, I think this method is way beyond what is reasonably dangerous and we will be better off by doing something else.
Anyway, what I decided to do was to adapt the interface to avoid accidental infinite loops.
The result is a “C-stylish” interface that tries to keep the elegance of Ruby at its core.
(I highlighted in bold text the methods that we haven’t seen before and also the ones that significantly diverge from what we see on regular linked lists).
Circular linked lists interface: Methods names, summaries and time complexity.
Implementation details
What follows is brief description of each method, its complexity and its source code.
Initialize
This method is the list constructor. The only thing it does is to create an empty list setting the head to nil and the list length to 0.
The complexity of this method is O(1).
def initialize
self.head = nil
self.length = 0
end
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 end of the list.
Since circular lists keep no pointers to their last node, the complexity of this method is O(n).
def insert data
return insert_next(nil, data) if (self.length == 0)
return insert_next(self.head, data) if (self.length == 1)
# Finds the last node.
self.current = head
i = 0;
while ((i += 1) < self.length)
move_next
end
# Inserts the new node right after the last node.
return insert_next(self.current, data)
end
Insert Next
Since inserts in circular linked are O(n), having a method that allows us to insert items in constant time is a nice feature to have.
Insert next allow you to insert elements in constant time as long as you hold a pointer to the node that will precede the new node. (Usually, it’ll be a pointer to the last node, but that’s not required. You can insert elements in any place.)
If the list has no nodes, the argument “previous node” is ignored, and the newly created node becomes the head of the list. In this particular case, the next pointer of the head node points to itself.
If the list contains nodes already, we have to do two things:
Set the next pointer of the new element to point to the next pointer of the node that precedes it.
Set the next pointer of the previous node to point to the new node.
And finally, we have to adjust the list’s length before return.
The complexity of this method is O(1).
def insert_next prev_node, data
new_node = Node.new data
if self.length == 0
self.head = new_node.next = new_node
else
new_node.next = prev_node.next
prev_node.next = new_node
end
self.length += 1
end
Remove
Removes the given node from the linked list and adjusts pointers to keep the elements together.
If the node to be removed is not the of the list, this method has to find the node that precedes the node to be deleted and then call remove_next.
The complexity of this method is O(n).
def remove node
return nil unless node
return nil unless self.length > 0
# head?
return remove_next node if (self.length == 1)
# Find the precedent node to the node we
# want to remove.
prev = nil
self.current = self.head
while ((prev = self.move_next) != node)
end
remove_next prev
end
Remove Next
This method allows us to remove elements in constant time as long as we have a pointer to the node that precedes the item to be removed.
If the element to be removed is the only element in the lits, we just need to point head to nil, and we are done.
If the argument previous node is nil, we have to set head to point to the node that is next to it, and we are done.
If the element to remove is not the only element in the list, nor the previous node is nil, we have to:
- “Capture” the next to the previous node.
- Point the next pointer of the captured node to that follows the next pointer of the previous node.
- Check if the node we captured before is the head of the list. If so, we have to point the head of the list to the node that is next to the captured node.
(Don’t worry, it’ll be easy to follow once you get to see the code.)
Since we have a pointer to the element that precedes the target element and a pointer to the element that follows it, the complexity of this method is O(1).
def remove_next prev_node
return nil unless self.length > 0
unless prev_node
self.head = self.head.next
else
if prev_node.next == prev_node
self.head = nil
else
old = prev_node.next
prev_node.next = prev_node.next&.next
if (old == self.head)
self.head = old.next
end
end
end
self.length -= 1
end
Clear
This method removes all elements from the list. Since we have to walk the whole list.
The complexity of this method is O(n).
def clear
while self.length > 0
remove self.head
end
end
Move Next
Points the current node to the node that follows it in the list.
Since we already have a pointer to the current node, the complexity of this method is O(1).
def move_next
self.current = self.current&.next
end
Full Scan
It traverses all elements in the list without wrapping around.
This method starts from the head of the list and moves next (yielding one element at a time) until it gets back to the head of the list.
This method is handy in those cases where you want to traverse the list from head to tail as if it was a regular linked list.
The complexity of this method is O(n).
def full_scan
return nil unless block_given?
self.current = self.head
loop do
yield self.current
break if (move_next == self.head)
end
end
Find First
This method allows us to get the first element of the list that satisfies a given predicate.
The way the list finds the first element that matches the predicate is by walking its elements and applying the predicate to each one of them until one matches or it gets back to its head.
The complexity of this method is O(n).
This method prints the contents of the current list. It’s a nice helper method and also a neat way to show full_scan in action.
The complexity of this method is O(n).
def print
if self.length == 0
puts "empty"
else
self.full_scan { |item| puts item.data }
end
end
When to use a circular linked list
You should consider circular linked list in those cases were linked lists will do well, but you also need to wraparound when the list gets exhausted.
For instance, if you are working on a windows manager that allows users to cycle thru windows by pressing Cmd+Tab, a circular linked list will work great.
def on_key_press e
windows.move_next if (e.Super && e.Tab)
end
If you need to support backward cycling (i.e., when users press Cmd + Shift + Tab), you can use doubly linked circular lists instead.
Another thing to consider about circular lists is that random inserts/removes are O(n). If you have to do lots of inserts/delete on reasonably large data sets, this data structure might not help you to pull that off.
That’s about it for circular linked lists. In fact, all list I’m going to cover. I hope you enjoyed!
Next time, queues. Stay tuned!
Thanks for reading!
