Circular Linked list is a linked list where all the node’s are connected to form a circle, the last node of the list points to the first node of the list.
In the last node of a singly linked list, the link field often points to NULL to indicate the end of the list. A less common convention is to make it point to the first node of the list; in that case the list is said to be ‘circular’ or ‘circularly linked’; otherwise it is said to be ‘open’ or ‘linear’.
A circular singly linked list can visually be represented by a group of people putting their arm over the other person.
A circular doubly linked list can visually be represented by a group of people holding the other person’s hand.
Advantages of Circular Linked Lists over Singly Linked Lists:
- The whole list can be traversed from any starting point; traversal is completed when the node with which we started with is visited again.
- Useful for implementation of circular queue, as we don’t need to maintain two pointers FRONT and REAR rather just maintain a pointer to the first node or the last node. If the pointer points to the last node, the first node is obtained as next of last.
Applications of Circular Linked lists:
- The real life application where circular linked lists are used is our Computers, where multiple applications are running simultaneously. All the applications are kept in a circular linked list and the OS gives a fixed time slot for all the running applications, the OS keeps iterating over the linked list until all the applications are completed.
- They are also used in multiplayer games. All the players currently playing the game are kept in a circular linked list and the pointer keeps on moving forward as a player’s chance ends.
- Circular Doubly linked lists are used for implementation of advanced data structures like Fibonacci Heap.
Circular Singly Linked List Operations:
Creating a node using MALLOC function
/*C Function to create a node*/
struct node //Creating a self-referential structure
{
int info;
struct node * link;
};
typedef struct node * NODE;
void MALLOC(NODE temp,int i,struct node); //User defined function
/*NODE temp is the temporary pointer variable that is getting dynamically allocated,
int i is the variable that stores how many new nodes is to be created */
{
int j=0;
for(j=0; j<i; j++) //Each iteration dynamically allocates a single node
{
temp=(NODE)malloc(sizeof(struct node)); //Library function to dynamically allocate memory.
if(temp==NULL) //If dynamic allocation fails then malloc() returns NULL
{
printf(“Insufficient Memory.”);
exit(0);
}
}
}
Insertion
Insertion at the front end:
Steps to insert a node at the beginning of the linked list:
- Create a new node.
- Set the new node’s info field to ITEM.
- Check if the list is empty, if it is then the new node’s link should point to itself.
- Else set new node’s link field to first.
- Traverse the list to reach the last the node.
- Set the last node’s link to the new node.
- Return the new node, which is now the first node.
/* C function for Insertion at the front end. */
NODE insert_front(int item, NODE first)
{
NODE temp,cur;
MALLOC( temp, 1 , struct node); //Creating new node temp
temp->info=ITEM; //Assigning the data to the new node
if(first==NULL) // Checking if the list is empty
{
temp->link=temp; //the node should point to temp itself as it is the only node
first=temp;
return first;
}
temp->link=first;
cur=first;
while(cur-link != first) //Traversing the list to reach the last node
{
cur=cur->link;
}
cur->link=temp; //Setting the last node to point to the first node
return temp;
}
Insertion at the rear end:
Steps to insert a node at the end of the linked list:
- Create a new node.
- Set new node’s info field to ITEM
- Check if the list is empty, if it is then set the new node’s link field to itself.
- Else, set cur=first and traverse the list using cur.
- Set the new node’s link field to the last node’s link field. Then set the penultimate node’s link field to the last node.
- Return first.
/* C function for Insertion at the rear end. */
NODE insert_rear(int item, NODE first)
{
NODE temp,cur;
MALLOC( temp, 1 , struct node); //Creating new node temp
temp->info=ITEM;
if(first==NULL) //Checking if the list is empty
{
temp->link=temp; //the new node should point to itself as it is the only node in the list
first=temp;
return first;
}
cur=first;
while(cur-link != first) //Traversing the list to reach the last node
{
cur=cur->link;
}
temp->link=cur->link; //Setting the new node’s link field to the first node.
cur->link=temp; //Setting the penultimate node’s link field to the last node
return first;
}
Deletion
Deletion at the front end:
Steps to delete a node from the front end of the linked list:
- Check if the list is empty, if yes then exit.
- Check if there is only one node present in the list, then delete the node and return NULL.
- Else set temp to first and cur to first.
- Set temp to temp->link.
- Traverse to the end of the list using cur.
- Set cur->link to temp.
- Delete first.
- Return temp.
/*Delete a node from the front end*/
Node delete_front(Node first)
{
Node temp,cur;
cur=first;
temp=first;
if(first==NULL) //Checking if the list is empty
{
printf(“List is empty \n”);
return;
}
else if(first->link==first) // Checking if there is only one element in the list.
{
printf(“Item deleted=%d”,first->info); //Displaying the deleted node’s contents.
free(first);
return NULL; //List is empty
}
temp=temp->link;
printf(“Item deleted=%d”,first->info); //Displaying the deleted node’s contents
while(cur->link !=first) //Traversing the list
{
cur=cur-link;
}
cur->link=temp; //Setting the last node’s link field to the new first node(temp).
free(first); // Deleting the first node.
return temp;
}
Deletion at the rear end:
Steps to delete a node from the rear end of the linked list:
- Check if the list is empty, if yes then exit.
- Check if there is only one node present in the list, if yes then delete the node and return NULL.
- Else set temp to first.
- Traverse to the end of the list using temp, set prev= temp to store previous node’s address.
- Set prev->link to temp->link.
- Delete temp
- Return first.
/* C function for deletion at the rear end. */
Node delete_rear(Node first)
{
node temp,prev;
if(first==NULL) // Checking if the list is empty
{
printf(“The list is empty”);
return;
}
if(first->link==first) //Checking if there is only one element in the list.
{
printf(“Item deleted=%d”,first->info); //Displaying the deleted node’s contents.
free(first);
return NULL; //List is empty
}
temp=first;
while(temp->link !=first) // Traversing the list
{
prev=temp; //Stores the current node’s address
temp=temp->link; //Stores the next node’s address
}
printf(“Item deleted=%d”,temp->info); //Displaying the deleted node’s contents.
prev->link=first; //Setting the penultimate node’s link field to point to the first node as it is now the last node.
free(temp); // Deleting the last node.
return first;
}
Display
Steps to display the contents of the linked list:
- Check if list is empty, if yes then exit.
- Display the contents of the first node: print first->info
- Set temp to first->link
- Traverse as long as temp != first
- Display temp->info
- Set temp to temp->link
/* C function for displaying the circular linked list. */
void display(node first)
{
node temp;
if(first==NULL) // Checking if the list is empty
{
printf(“List is empty.”);
return;
}
printf(“Contents of the list \n”);
printf(“%d \n”,first->info); // Displays the contents of the first node
temp=first->link;
while(temp != first) // Traversing the list
{
printf(“%d \n”,temp->info); // Displays the content of the current node
temp=temp->link; //Stores the next node’s address
}
}
Insertion using a pointer pointing to the last node
In all the function stated above, we have been using a pointer pointing to the first node of the list namely ‘first’, we use this pointer as a reference for traversing as well as all the other operations.
All the above operations can also be done by taking a pointer pointing to the last node of the list, ‘last’, and the first node of the list can always be obtained as last->link.
Insertion in an empty list:
Initially when the list is empty, the last pointer will be NULL. After inserting a node T, T is the first and last node so last points to node T, and node T points to itself.
/* C function for Insertion in an empty list using last pointer. */
Node addToEmpty(Node last, int data)
{
// This function is only for empty list
if (last != NULL)
return last;
Node T;
MALLOC(T,1,struct Node); // Creating a node dynamically
// Assigning the data.
T-> data = data;
// Note : list was empty. We link single node
// to itself.
T-> next = last;
return last;
}
Insertion at the beginning of the list:
Steps:
- Create a node, say T.
- Make T->next=last->next.
- Last->next=T.
Node addBegin(Node last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
Node temp;
MALLOC(temp,1,struct Node); // Creating a node dynamically.
// Assigning the data.
temp -> data = data;
// Adjusting the links.
temp -> next = last -> next;
last -> next = temp;
return last;
}
Before Insertion
After Insertion
Insertion at the end of the list:
Steps:
- Create a node, say T.
- Make T->next=last->next.
- Last->next=T.
- Last=T
/* C function for Insertion at the rear end using last pointer. */
Node addEnd(Node last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
Node temp;
MALLOC(temp,1,struct Node); // Creating a node dynamically.
// Assigning the data.
temp -> data = data;
// Adjusting the links.
temp -> next = last -> next;
last -> next = temp;
last = temp;
return last;
}
Before Insertion
After Insertion
–
Dhanish.V
1CR16IS030
Life In Data Structures and Algorithms 
Well explained !
LikeLiked by 2 people
An interesting explanation of Circular Linked Lists!
LikeLiked by 2 people
The concept circular queues is itself so interesting and so is this article!
LikeLike
Linked Lists are beautiful! The article depicts an artist’s work in capturing the beauty and displaying it with such an ease. The accuracy of the portrait is remarkable! Bravo!
LikeLike