DataStructures Series #9 – The Circular LinkedList Datastructure

Originally posted on my medium page: https://medium.com/@otarutunde

The Circular LinkedList Datastructure

The circular linkedlist is a variation of the linkedList datastructure (an implementation of the List ADT), both the singly linkedlist and the doubly linkedlist can be modified to become a circular singly linkedlist or a circular doubly linkedlist.

A circular linked list is a linked list that has the last node’s next element pointing to the first node. A good thing to note here is that you will never hit a null element when traversing a circular linked list. The next element of each node always points to another node or itself (when you have just one element).

Modifying the LinkedList to Conform to a Circular Linked List

To modify the linked list (both singly DataStructures Series #7 – The LinkedList ADT and doubly DataStructures Series #8 – The Doubly LinkedList ADT), we need to set the last node in the list to the first one as shown in the images below for singly and doubly linked lists:

Circular Singly Linked List (Image source: http://quora.com)

Circular Doubly Linked List (Image source: https://social.technet.microsoft.com)

Implementation

The implementation details is similar to LinkedList (DataStructures Series #7 – The LinkedList ADT) and Doubly LinkedList (DataStructures Series #8 – The Doubly LinkedList ADT). The differences are:

  • during list iteration in the circular linked list, we check if the currentNode is the firstNode to indicate the end of the list instead of null has shown in the singly and doubly linked lists.
  • when inserting/deleting in a circular linked list, we always cater for the end and first nodes by linking them together.

Real life Applications

  • A music playlist in a loop — Music playlist in a loop