1.9 Circular Linked List
1.9.1 Circular Linked List- Introduction and Applications
Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.
Applications of Circular Linked Lists:
1) Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again.
2) Useful for implementation of queue. We don’t need to maintain two pointers for front and rear if we use circular linked list. We can maintain a pointer to the last inserted node and front can always be obtained as next of last.
3) Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list.
4) Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap.
Runnable Code Snippet_1.9.1 – Circular Linked List
#include<iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
Node* Insert(int x,Node *head){
Node* temp=new Node;
temp->data=x;
temp->next=NULL;
if(head==NULL){
head=temp;
temp->next=head;
}else{
Node* temp1=head;
do{
temp1=temp1->next;
}while(temp1->next!=head);
temp->next=head;
temp1->next=temp;
}
return head;
}
void Print(Node* head){
if(head!=NULL){
Node* temp=head;
do{
cout<<temp->data<<" ";
temp=temp->next;
}while(temp!=head);
}cout<<endl;
}
void Check(Node* head){
if(head!=NULL){
Node* temp=head;
do{
temp=temp->next;
}while(temp!=head);
if(temp==head) cout<<"Circular..\n";
else cout<<"Linear..\n";
}
}
int main(){
Node* head=NULL; //empty
int n,x;
cout<<"Enter Size: ";
cin>>n;
cout<<"enter elements:\n";
for(int i=0;i<n;i++){
cin>>x;
head=Insert(x,head);
}
Print(head);
Check(head);
return 0;
}
1.9.2 – Circular Linked List (Traversal):
In a conventional linked list, we traverse the list from the head node and stop the traversal when we reach NULL. In a circular linked list, we stop traversal when we reach the first node again. Following is C code for linked list traversal.
/* Function to traverse a given Circular linked list and print nodes */
void printList(struct Node *first)
{
struct Node *temp = first;
// If linked list is not empty
if (first != NULL)
{
// Keep printing nodes till we reach the first node again
do
{
printf("%d ", temp->data);
temp = temp->next;
}
while (temp != first);
}
}
Demonstrating Traversal:
Following program demonstrates the traversal of circular linked list.
Runnable Code Snippet_1.9.2 – Circular Linked List – Traversal
/*Circular Linked List - Traversal*/
#include<stdio.h>
#include<stdlib.h>
/* structure for a node */
struct Node
{
int data;
struct Node *next;
};
/* Function to insert a node at the begining of a Circular
linked list */
void push(struct Node **head_ref, int data)
{
struct Node *ptr1 = (struct Node *)malloc(sizeof(struct Node));
struct Node *temp = *head_ref;
ptr1->data = data;
ptr1->next = *head_ref;
/* If linked list is not NULL then set the next of last node */
if (*head_ref != NULL)
{
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1; /*For the first node */
*head_ref = ptr1;
}
/* Function to print nodes in a given Circular linked list */
void printList(struct Node *head)
{
struct Node *temp = head;
if (head != NULL)
{
do
{
printf("%d ", temp->data);
temp = temp->next;
}
while (temp != head);
}
}
/* Driver program to test above functions */
int main()
{
/* Initialize lists as empty */
struct Node *head = NULL;
/* Created linked list will be 11->2->56->12 */
push(&head, 12);
push(&head, 56);
push(&head, 2);
push(&head, 11);
printf("Contents of Circular Linked List\n ");
printList(head);
return 0;
}
1.9.3 Circular Linked List – Insertion:
Split the given Circular Linked List into two halves, for example
if the above Circular linked List is given. then split is as below
and
Follow the below algorithm.
1) Store the mid and last pointers of the circular linked list using tortoise and hare algorithm.
2) Make the second half circular.
3) Make the first half circular.
4) Set head (or start) pointers of the two linked lists.
In the below implementation, if there are odd nodes in the given circular linked list then the first result list has 1 more node than the second result list.
Runnable Code Snippet_1.9.3 Circular Linked List – Insertion
/* 1.9.3 Circular Linked List - Insertion */
#include<stdio.h>
#include<stdlib.h>
/* structure for a node */
struct Node
{
int data;
struct Node *next;
};
/* Function to split a list (starting with head) into two lists.
head1_ref and head2_ref are references to head nodes of
the two resultant linked lists */
void splitList(struct Node *head, struct Node **head1_ref,
struct Node **head2_ref)
{
struct Node *slow_ptr = head;
struct Node *fast_ptr = head;
if(head == NULL)
return;
/* If there are odd nodes in the circular list then
fast_ptr->next becomes head and for even nodes
fast_ptr->next->next becomes head */
while(fast_ptr->next != head &&
fast_ptr->next->next != head)
{
fast_ptr = fast_ptr->next->next;
slow_ptr = slow_ptr->next;
}
/* If there are even elements in list then move fast_ptr */
if(fast_ptr->next->next == head)
fast_ptr = fast_ptr->next;
/* Set the head pointer of first half */
*head1_ref = head;
/* Set the head pointer of second half */
if(head->next != head)
*head2_ref = slow_ptr->next;
/* Make second half circular */
fast_ptr->next = slow_ptr->next;
/* Make first half circular */
slow_ptr->next = head;
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the begining of a Circular
linked lsit */
void push(struct Node **head_ref, int data)
{
struct Node *ptr1 = (struct Node *)malloc(sizeof(struct Node));
struct Node *temp = *head_ref;
ptr1->data = data;
ptr1->next = *head_ref;
/* If linked list is not NULL then set the next of
last node */
if(*head_ref != NULL)
{
while(temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1; /*For the first node */
*head_ref = ptr1;
}
/* Function to print nodes in a given Circular linked list */
void printList(struct Node *head)
{
struct Node *temp = head;
if(head != NULL)
{
printf("\n");
do {
printf("%d ", temp->data);
temp = temp->next;
} while(temp != head);
}
}
/* Driver program to test above functions */
int main()
{
int list_size, i;
/* Initialize lists as empty */
struct Node *head = NULL;
struct Node *head1 = NULL;
struct Node *head2 = NULL;
/* Created linked list will be 12->56->2->11 */
push(&head, 12);
push(&head, 56);
push(&head, 2);
push(&head, 11);
printf("Original Circular Linked List");
printList(head);
/* Split the list */
splitList(head, &head1, &head2);
printf("\nFirst Circular Linked List");
printList(head1);
printf("\nSecond Circular Linked List");
printList(head2);
getchar();
return 0;
}
1.9.4 – Sorted insertion for circular linked list
After Sorted Insertion of Circular Linked List, the elements must be in sorted order. For example, if we have a Circular Linked List
After inserting an element 7, the above Circular Linked List should be changed to the following
Algorithm:
Allocate memory for the newly inserted node and put data in the newly allocated node. Let the pointer to the new node be new_node. After memory allocation, following are the three cases that need to be handled.
1) Linked List is empty:
a) since new_node is the only node in CLL, make a self loop.
new_node->next = new_node;
b) change the head pointer to point to new node.
*head_ref = new_node;
2) New node is to be inserted just before the head node:
(a) Find out the last node using a loop.
while(current->next != *head_ref)
current = current->next;
(b) Change the next of last node.
current->next = new_node;
(c) Change next of new node to point to head.
new_node->next = *head_ref;
(d) change the head pointer to point to new node.
*head_ref = new_node;
3) New node is to be inserted somewhere after the head:
(a) Locate the node after which new node is to be inserted.
while ( current->next!= *head_ref &&
current->next->data < new_node->data)
{ current = current->next; }
(b) Make next of new_node as next of the located pointer
new_node->next = current->next;
(c) Change the next of the located pointer
current->next = new_node;
Runnable Code Snippet_1.9.4 – Sorted insertion for circular linked list
/* 1.9.4 - Sorted insertion for circular linked list */
#include<stdio.h>
#include<stdlib.h>
/* structure for a node */
struct Node
{
int data;
struct Node *next;
};
/* function to insert a new_node in a list in sorted way.
Note that this function expects a pointer to head node
as this can modify the head of the input linked list */
void sortedInsert(struct Node** head_ref, struct Node* new_node)
{
struct Node* current = *head_ref;
// Case 1 of the above algo
if (current == NULL)
{
new_node->next = new_node;
*head_ref = new_node;
}
// Case 2 of the above algo
else if (current->data >= new_node->data)
{
/*If value is smaller than head's value then
we need to change next of last node */
while(current->next != *head_ref)
current = current->next;
current->next = new_node;
new_node->next = *head_ref;
*head_ref = new_node;
}
// Case 3 of the above algo
else
{
/* Locate the node before the point of insertion */
while (current->next!= *head_ref &&
current->next->data < new_node->data)
current = current->next;
new_node->next = current->next;
current->next = new_node;
}
}
/* Function to print nodes in a given linked list */
void printList(struct Node *start)
{
struct Node *temp;
if(start != NULL)
{
temp = start;
printf("\n");
do {
printf("%d ", temp->data);
temp = temp->next;
} while(temp != start);
}
}
/* Driver program to test above functions */
int main()
{
int arr[] = {12, 56, 2, 11, 1, 90};
int list_size, i;
/* start with empty linked list */
struct Node *start = NULL;
struct Node *temp;
/* Create linked list from the array arr[].
Created linked list will be 1->2->11->12->56->90 */
for (i = 0; i< 6; i++)
{
temp = (struct Node *)malloc(sizeof(struct Node));
temp->data = arr[i];
sortedInsert(&start, temp);
}
printList(start);
return 0;
}
/*
Case 2 of the above algorithm/code can be optimized.
To implement the suggested change we need to modify the case 2 to following.
// Case 2 of the above algo
else if (current->data >= new_node->data)
{
// swap the data part of head node and new node
// assuming that we have a function swap(int *, int *)
swap(&(current->data), &(new_node->data));
new_node->next = (*head_ref)->next;
(*head_ref)->next = new_node;
}*/
1.9.5 – To check a Linked List is Circular:
Runnable Code Snippet_1.9.5 – To check a Linked List is Circular
/* 1.9.5 - To check a Linked List is Circular */
/* circular L.L */
#include<iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
/*utility function*/
Node* newNode(int data){
Node* temp=new Node;
temp->data=data;
temp->next=NULL;
return temp;
}
bool isCircular(Node* head){
if(head==NULL) return true;
Node* node=head->next;
while(node!=NULL && node!= head)
node=node->next;
return (node==head);
}
/*driver code to test the implementation*/
int main()
{
Node* head=newNode(1);
head->next=newNode(2);
head->next->next=newNode(3);
head->next->next->next=newNode(4);
isCircular(head)? cout<<"yes\n": cout<<"no\n";
/*making ll circular*/
head->next->next->next->next=head;
isCircular(head)? cout<<"yes\n": cout<<"no\n";
return 0;
}
Alternate method to check Circular:
/* Alternate method to check Circular */
/*ftn to check circular
bool IsCircular(Node* head)
{
bool circleFound = false;
bool tailFound = false;
if (head && head->next)
{
Node* slower = head;
Node* faster = head;
do
{
slower = slower->next;
faster = faster->next->next;
tailFound = ! (faster && faster->next);
if ( ! tailFound )
{
circleFound = (slower == faster || slower == faster->next);
}
}
while ( ! tailFound && ! circleFound)
}
return ( circleFound );
}
With this we finish the Linked Lists module. In the next module, we will cover some Stack concepts. Please follow the blog to stay updated with the upcoming modules.
love,
<R.S>
For Complete Sourcecode visit my Github repo: Link provided in the final module
RS-codes
RS-codes 
3 thoughts on “Data Structures & Algorithms – Circular Linked List”