DataStructures Series — 9

N.B. This article would make more sense if you read previous articles in this series.

In case you missed last week on the data-structures series here.

We discussed the Doubly Linked List data structure, a type of Linked List and we wrote some pseudocode to implement the operations of a doubly linked list data structure.

This week, we would be discussing another type of linked list, the Circular Linked List.

The circular Linked List

Both the singly and doubly linked list can be modified to become a circular linked list.

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 would 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 Linked List to Conform to a Circular Linked List

To modify the linked list (both singly and doubly), 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

We would take the singly linked list as our case study but the same concept applies to the doubly linked list. We would modify both the insert and delete operations by linking the last node to the first node.

Insert ():

Node head; // already in memory
Node tail; // already in memory
Node newElement = new Node(elementData, null);
if head is null: // no element in list yet
   head = newElement;
   tail = newElement;
   head.nextNode = tail;
   tail.nextNode = head;
else
   Node previousTail = tail;
   tail = newElement;
   tail.nextNode = head;
   previousTail.nextNode = tail;

delete ():

Node head; // already in memory
Node tail; // already in memory
Node nodeBeforeTail = headNode;
while (nodeBeforeTail.nextNode is not tail) { //get node before tail
   nodeBeforeTail = nodeBeforeTail.nextNode;
}
nodeBeforeTail.nextNode = head; // set nextNode to first node.

The same concept applies to other operations in the linked list data structure.

Linked List Usages

We discussed about the stack and queue data structures earlier in this series and we used an array data structure to implement them internally. A linked list would have been a better data structure to use for its internal implementation to improve performance on their operations. As shown above, a deletion and insertion also happens in constant time and you don’t need to resize because the linked list size is not bounded unlike an array where you need to specify the size and resize when full.

Applications

• If you are building a music player application or an advert player module in your application where you need to continuously play a music or show an advert, the circular singly or doubly linked list depending on your use case is the ideal data structure to use.

Next week, we would be discussing a new abstract data type Trees.

You can drop questions and comments on any article in this series and I would do well to give a reply.

REFERENCES:

https://en.wikipedia.org/wiki/Linked_list