Circular lists

A circular list is a special case of a linked list. It is a list where the endpoints are connected. That is, the last node in the list points back to the first node. Circular lists can be based on both singly and doubly linked lists. In the case of a doubly linked circular list, the first node also needs to point to the last node.

Here we are going to look at an implementation of a singly linked circular list. It should be straightforward to implement a doubly linked circular list, once you have grasped the basic concepts.

We can reuse the node class that we created in the section on singly linked lists. As a matter of fact, we can reuse most parts of the SinglyLinkedList class as well. So we are going to focus on the methods where the circular list implementation differs from the normal singly linked list.

Appending elements

When we append an element to the circular list, we need to make sure that the new node points back to the tail node. This is demonstrated in the following...