Lists Part IV: Circular Linked-Lists

Data Structures in Ruby

Lists Part IV: Circular Linked-Lists

Previously

I recommend reading part I, part II and part III of this series if you haven’t already. Part I introduces lists, part II details their basic operations, and part III compares them to arrays.


Circular Linked-Lists

In a circular linked-list, the tail of the list points back to the head of the list. It’s a simple change conceptually, but there are some concrete ramifications for the three basic operations performed on such lists.

Circular Linked-list

Searching

Given that the tail of a circular linked-list points back to its head, it is necessary to terminate a search against such a list when it’s tail is reached. Otherwise, the search will spark an infinite loop.

Notice that in contrast to the recursive iteration we leveraged so far in this series, we’re using an iterative approach here. Hence the Enumerable mixin.

Searching a Circular Linked-list: Match found
Searching a Circular Linked-list: Match not found

Insertion

When inserting into a circular linked-list, the current head of the list must be shifted one position to the right while still maintaining a pointer from the tail of the list to its head.

There are two cases to be considered here.

In the first, general case, the new node is adopted into the list by first pointing the new node at the head node’s successor, then pointing the head node’s successor at the new node, finally swapping the data of the head node with the data of the new node.

In the second, special case, insertion into an empty list is accomplished by first designating the new node as its own successor, then pointing the list’s head at the new node.

Insertion into a Circular Linked-list ( the general case )
Insertion into an empty Circular Linked-list ( a special case )

Deletion

The deletion operation for a circular linked-list is accomplished by shifting the nodes around a doomed node in such a way that that the tail pointer to the head of the list is properly maintained.

There are three cases to consider.

The first, general case, is accomplished by first having the doomed node copy the data of its successor, then pointing the doomed node to its successor’s next node.

The second, special case, in which a deletion occurs at a list’s tail, is accomplished by first having the doomed tail node copy the head node’s data, then having the doomed tail node point to the head node’s successor, finally having the list’s head point at the doomed node (which has now been repurposed as the head of the list).

The third, special case, in which the deletion of the only node in a list occurs, is accomplished by merely setting the list’s head to nil.

Deletion from a Circular Linked-list ( the general case )
Deletion of the tail of a Circular Linked-list ( a special case )
Deletion from a single-node Circular Linked-list ( a special case )

Recap

A circular-linked list differs from a standard list in that the tail of a circular linked-list must maintain a pointer back to its list. This difference, though small, necessitates several modifications of the basic operations for such lists. Because of this, operations of the circular linked-list should be carefully studied until they are intuitively understood.


Q & A

What is a circular linked-list?

A circular linked-list is a list whose tail points back to its head.

How does circular linked-list iteration compare to standard list iteration?

Circular linked-list iteration is terminated when the current node being visited points to the head of the list. In standard lists, iteration is terminated when the visited node points to nil.

How does insertion into a circular linked-list compare to insertion into a standard list?

A standard list allows us to insert a new node by assigning the list’s head to the new node, then pointing the new node’s successor at the list’s previous head node. A circular linked-list requires us to first point the new node at the head node’s successor, then point the head node’s successor at the new node, then swap the data of the head node with the data of the new node.

What must be done when inserting into an empty circular linked-list?

The new node must be pointed at itself, then the list’s head must be pointed at the new node.

How does searching a circular linked-list compare to searching a standard list?

Searching a circular linked-list is the same as searching a standard list, except for one thing: a circular linked-list search terminates when it reaches a node pointing to the list’s head; a standard list search terminates when it reaches a node pointing to nil.

How does the deletion operation of a circular linked-list compare to the deletion operation of a standard list?

The deletion operation of a circular linked-list differs from the deletion operation of a standard list in that instead of removing a doomed node directly, the nodes around the doomed node are shifted in such a way that the pointer from the tail back to the head of the list is properly maintained.

What must be done when deleting a node at the tail of a circular linked-list?

When a deletion occurs at a list’s tail, first the doomed tail node must copy the head node’s data, then the doomed tail node must point to the head node’s successor, finally the list’s head must be pointed at the doomed node.

What must be done when deleting a node from a circular linked-list made up of only one node?

Deletion from a single-node circular-linked list is a special case. In such a case, the head of the list must be set to nil, effectively emptying the list.


Up Next

Stay tuned for part V of this series, in which we’ll explore doubly linked-lists. If you enjoyed this post and want to stay current on updates to this series, please be sure to recommend this post and follow me below. Check out part V now.