Circular Linked List

A Circular Linked List (CLL) is similar to a singular linked list, except that the next to the last node points to the first node. Simply put, a circular linked list doesn’t have ends. What we must be aware of in traversing the circular linked list is when to terminate, as we might end up in an infinite loop.

Circular linked lists have real-life use cases, like in the famous scheduling algorithm, Round Robin Algorithm, used to make sure no process gets too much CPU time and assure that no process accesses the resources before all other processes.

Below is the structure of our CLLNode:

1
2
3
4
struct CLLNode {
  int data;
  CLLNode * next;
}

Now that we have a bit of knowledge about circular linked lists, let us get familiar with some basic methods of it.

When we talk about a dynamic data structure, the most important aspects are the basic operations like inserting, deleting, and retrieving. In CLL we have many different scenarios when it comes to the above operations, we will look at them one by one.

Inserting a Node in Circular Linked List

We will be inserting a node with data = ‘X,
who’s next pointer is pointing to it.

At Front

When adding a node to the front of the circular linked list, it also becomes the new head of the CLL.

Now after creating our new node, we need to update the next pointer of our head node. After doing this we traverse to the end of the CLL and update the next tail node to our new node.

Now we make the new node the head,

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void insertAtFront(CLLNode * head, int X) {

  CLLNode * ptr, * temp;
  ptr = new CLLNode();
  if (ptr == NULL)
    return;

  ptr - > data = X;
  if (head == NULL) {
    head = ptr;
    ptr - > next = head;
  } else {
    temp = head;
    while (temp - > next != head)
      temp = temp - > next;
    ptr - > next = head;
    temp - > next = ptr;
    head = ptr;
  }
}

At End

Adding at the end is similar to adding at the front. Create a new node and point it next to the head, as it is going to add to the end, which means it becomes the tail and the tail next contains the head pointer.

Now traverse to the tail of the CLL (node->next == head) and point the next pointer of the tail to our new node.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void insertAtEnd(CLLNode * head, int X) {

  CLLNode * ptr, * temp;
  int item;
  ptr = new CLLNode();
  if (ptr == NULL)
    return;

  ptr - > data = X;
  if (head == NULL) {
    head = ptr;
    ptr - > next = head;
  } else {
    temp = head;
    while (temp - > next != head) {
      temp = temp - > next;
    }

    temp - > next = ptr;
    ptr - > next = head;
  }
}

Deleting a Node in a Circular Linked List

At front:

To delete the node at the front we simply replace the next pointer of the tail node with the next field of the first node.

First, we traverse to the tail of the CLL and update the next pointer of the tail with the node next to the first node. Note, we must store the first node in some temp node to delete it at last.

Now just move the head pointer to the next node and delete the temp node.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void deleteAtEnd(CLLNode * head) {
  CLLNode * ptr;
  if (head == NULL)
    return;

  if (head - > next == head) {
    head = NULL;
    free(head);
  } else {
    ptr = head;
    while (ptr - > next != head)
      ptr = ptr - > next;
    ptr - > next = head - > next;
    free(head);
    head = ptr - > next;
  }
}

At last:

Deletion of the tail is very easy, we just have to traverse to the second to the last node, update its next pointer to the head, and delete the tail.

Here we traverse until the node with value 68, update it next to our head, and delete the node with value 25. We will do the stated operation in one step which is going to be almost the same as deleting at the front.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void deleteAtEnd(CLLNode * head) {

  CLLNode * ptr, * preptr;
  if (head == NULL)
    return;

  if (head - > next == head) {
    head = NULL;
    free(head);
  } else {
    ptr = head;
    while (ptr - > next != head) {
      preptr = ptr;
      ptr = ptr - > next;
    }
    preptr - > next = ptr - > next;
    free(ptr);
  }
}

Complexity:

• Runtime complexity of all the above operations is O(n) for scanning the complete list of size n.

• Space complexity O(1) for temporary variable and other variables