Circular Linked Lists

A circular linked list has one slight modification over the singly linked list, the last element in the list points back to the first of the list. This allows for reaching the first element without starting over while traversing. There is no NULL pointer to mark the end of a linked list.

Any node in a Circular Linked List can be taken as a starting point. The whole list can be traversed by starting from this one node.

Defining the Node

struct Node
{
   int data;
   struct Node *next;
} *head = NULL;

Operations in a Linked List

The few basic operations in a linked list including adding, deleting and modifying.

Insertion at the end of the list

New data can be added to the end of the linked list by creating a new node with the data to be used, traversing to the end of the list and then appending this data to the end.

Steps

void insertAtEnd(int value)
{
   struct Node *newNode;
   newNode = (struct Node*)malloc(sizeof(struct Node));
   newNode -> data = value;
   if(head == NULL)
   {
      head = newNode;
      newNode -> next = head;
   }
   else
   {
      struct Node *temp = head;
      while(temp -> next != head)
         temp = temp -> next;
      temp -> next = newNode;
      newNode -> next = head;
   }
   printf("\nInsertion successful");
}

Insertion at the beginning of the list

New data can be added to the beginning of the linked list by creating a new node with the data to be used, replacing the head pointer to the new node and replacing the connections.

Steps

void insertAtBeginning(int value)
{
    struct Node *newNode;
    newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode -> data = value;
    if(head == NULL)
    {
       head = newNode;
       newNode -> next = head;
    }
    else
    {
       struct Node *temp = head;
       while(temp -> next != head)
          temp = temp -> next;
       newNode -> next = head;
       head = newNode;
       temp -> next = head;
    }
    printf("\nInsertion successful");
}

Insertion after an element in the list

New data can be added at any position in the list by traversing to that position using a loop, creating a new Node and then manipulating the links to insert it at that position.

Steps

void insertAfter(int value, int location)
{
   struct Node *newNode;
   newNode = (struct Node*)malloc(sizeof(struct Node));
   newNode -> data = value;
   if(head == NULL)
   {
      head = newNode;
      newNode -> next = head;
   }
   else
   {
      struct Node *temp = head;
      while(temp -> data != location)
      {
         if(temp -> next == head)
         {
            printf("Given node is not found in the list");
         }
         else
         {
            temp = temp -> next;
         }
      }
      newNode -> next = temp -> next;
      temp -> next = newNode;
      printf("\nInsertion successful");
   }
}

Deletion from the end of the list

New data can be added to the end of the linked list by creating a new node with the data to be used, traversing to the end of the list and then appending this data to the end.

Steps

void deleteEnd()
{
   if(head == NULL)
      printf("List is Empty");
   else
   {
      struct Node *temp1 = head, *temp2;
      if(temp1 -> next == head)
      {
         head = NULL;
         free(temp1);
      }
      else{
         while(temp1 -> next != head){
            temp2 = temp1;
            temp1 = temp1 -> next;
         }
         temp2 -> next = head;
         free(temp1);
      }
      printf("\nDeletion successful");
   }
}

Deletion from the beginning of the list

New data can be added to the beginning of the linked list by creating a new node with the data to be used, replacing the head pointer to the new node and replacing the connections.

Steps

void deleteBeginning()
{
   if(head == NULL)
      printf("List is Empty");
   else
   {
      struct Node *temp = head, *last = NULL;
      if(temp -> next == head)
      {
         head = NULL;
         free(temp);
      }
      else{
        while(temp -> next != head)
            temp = temp -> next;
        last = temp;
        temp = head;
        head = head -> next;
        free(temp);
        last -> next = head;
      }
      printf("\nDeletion successful");
   }
}

Deletion of a specific element in the list

New data can be deleted at any position in the list by traversing to that position using a loop, deleting the required Node and then manipulating the links to make the list continuous.

Steps

void deleteSpecific(int delValue)
{
   if(head == NULL)
      printf("List is Empty");
   else
   {
      struct Node *temp1 = head, *temp2;
      while(temp1 -> data != delValue)
      {
         if(temp1 -> next == head)
         {
            printf("\nGiven node is not found in the list");
         }
         else
         {
            temp2 = temp1;
            temp1 = temp1 -> next;
         }
      }
      if(temp1 -> next == head){
         head = NULL;
         free(temp1);
      }
      else{
         if(temp1 == head)
         {
            temp2 = head;
            while(temp2 -> next != head)
               temp2 = temp2 -> next;
            head = head -> next;
            temp2 -> next = head;
            free(temp1);
         }
         else
         {
            if(temp1 -> next == head)
            {
               temp2 -> next = head;
            }
            else
            {
               temp2 -> next = temp1 -> next;
            }
            free(temp1);
         }
      }
      printf("\nDeletion successful");
   }
}

Applications in Programming

1. Operating Systems: The Operating System keeps track of all the currently running processes in the system in a circular list. These processes are given a fixed time slot by the processor to perform its operations. The circular list allows the OS to repeatedly iterate over the linked list until all the processes have completed execution.
2. Implementing Circular Queue: A circular queue reduces the complexity of maintaining 2 pointers in the regular linear queue.