Below is a depiction of a circular linked list with 3 nodes.
Here, you can see that each node is retraceable to itself. The example shown above is a circular singly linked list. Note: The most simple circular linked list, is a node which traces only to itself as shown
In this circular linked list tutorial, you will learn:
What is a Circular Linked List? Basic Operations in Circular Linked lists Insertion Operation Deletion Operation Traversal of a Circular Linked List Advantages of Circular Linked List Disadvantages of Circular Linked List Singly-linked list as a Circular Linked List Applications of the Circular Linked List
Basic Operations in Circular Linked lists
The basic operations on a circular linked list are:
Insertion Deletion and Traversal
Insertion is the process of placing a node at a specified position in the circular linked list. Deletion is the process of removing an existing node from the linked list. The node can be identified by the occurrence of its value or by its position. Traversal of a circular linked list is the process of displaying the entire linked list’s contents and retracing back to the source node.
In the next section, you will understand insertion of a node, and the types of insertion possible in a Circular Singly Linked List.
Insertion Operation
Initially, you need to create one node which points to itself as shown in this image. Without this node, insertion creates the first node.
Next, there are two possibilities:
Insertion at the current position of the circular linked list. This corresponds to insertion at the beginning of the end of a regular singular linked list. In a circular linked list, the beginning and the end are the same. Insertion after an indexed node. The node should be identified by an index number corresponding to its element value.
For inserting at the beginning/end of the circular linked list, that is at the position where the first-ever node was added,
You will have to break the existing self-link to the existing node The new node’s next pointer will link to the existing node. The last node’s next pointer will point to the inserted node.
NOTE: The pointer that is the token master or the beginning/end of the circle can be changed. It will still return to the same node on a traversal, discussed ahead. Steps in (a) i-iii are shown below:
(Existing node)
STEP 1) Break the existing link
STEP 2) Create a forward link (from new node to an existing node)
STEP 3) Create a loop link to the first node Next, you will try insertion after a node. For example, let us insert “VALUE2” after the node with “VALUE0”. Let us assume that the starting point is the node with “VALUE0”.
You will have to break the line between the first and second node and place the node with “VALUE2” in between. The first node’s next pointer must link to this node, and this node’s next pointer must link to the earlier second node. The rest of the arrangement remains unchanged. All nodes are retraceable to themselves.
NOTE: Since there is a cyclic arrangement, inserting a node involves the same procedure for any node. The pointer that completes a cycle completes the cycle just like any other node. This is shown below:
(Let us say there are only two nodes. This is a trivial case)
STEP 1) Remove the inner link between the connected nodes
STEP 2) Connect the left-hand side node to the new node
STEP 3) Connect the new node to the right hand side node.
Deletion Operation
Let us assume a 3-node circular linked list. The cases for deletion are given below:
Deleting the current element Deletion after an element.
Deletion at the beginning/end:
Traverse to the first node from the last node. To delete from the end, there should be only one traversal step, from the last node to the first node. Delete the link between the last node and the next node. Link the last node to the next element of the first node. Free the first node.
(Existing setup)
STEP 1) Remove the circular link
STEPS 2) Remove the link between the first and next, link the last node, to the node following the first
STEP 3) Free /deallocate the first node Deletion after a node:
Traverse till the next node is the node to be deleted. Traverse to the next node, placing a pointer on the previous node. Connect the previous node to the node after the present node, using its next pointer. Free the current (delinked) node.
STEP 1) Let us say that we need to delete a node with “VALUE1.”
STEP 2) Remove the link between the previous node and the current node. Link its previous node with the next node pointed by the current node (with VALUE1).
STEP 3) Free or deallocate the current node.
Traversal of a Circular Linked List
To traverse a circular linked list, starting from a last pointer, check if the last pointer itself is NULL. If this condition is false, check if there is only one element. Otherwise, traverse using a temporary pointer till the last pointer is reached again, or as many times as needed, as shown in the GIF below.
Advantages of Circular Linked List
Some of the advantages of circular linked lists are:
No requirement for a NULL assignment in the code. The circular list never points to a NULL pointer unless fully deallocated. Circular linked lists are advantageous for end operations since beginning and end coincide. Algorithms such as the Round Robin scheduling can neatly eliminate processes which are queued in a circular fashion without encountering dangling or NULL-referential pointers. Circular linked list also performs all regular functions of a singly linked list. In fact, circular doubly linked lists discussed below can even eliminate the need for a full-length traversal to locate an element. That element would at most only be exactly opposite to the start, completing just half the linked list.
Disadvantages of Circular Linked List
The disadvantages in using a circular linked list are below:
Circular lists are complex as compared to singly linked lists. Reverse of circular list is a complex as compared to singly or doubly lists. If not handled carefully, then the code may go in an infinite loop. Harder to find the end of the list and loop control. Inserting at Start, we have to traverse the complete list to find the last node. (Implementation Perspective)
Singly Linked List as a Circular Linked List
You are encouraged to attempt to read and implement the code below. It presents the pointer arithmetic associated with circular linked lists.
#include<stdio.h> #include<stdlib.h>
struct node { int item; struct node *next; };
struct node* addToEmpty(struct node*,int); struct node *insertCurrent(struct node *, int); struct node *insertAfter(struct node *, int, int); struct node *removeAfter(struct node *, int); struct node *removeCurrent(struct node *);
void peek(struct node *);
int main() { …
Explanation of code:
The first two lines of code are the necessary included header files. The next section describes the structure of each self-referential node. It contains a value and a pointer of the same type as the structure. Each structure repeatedly links to structure objects of the same type. There are different function prototypes for:
Adding an element to an empty linked list Inserting at the currently pointed position of a circular linked list. Inserting after a particular indexed value in the linked list. Removing/Deleting after a particular indexed value in the linked list. Removing at the currently pointed position of a circular linked list
The last function prints each element through a circular traversal at any state of the linked list.
int main() { struct node *last = NULL; last = insertCurrent(last,4); last = removeAfter(last, 4); peek(last); return 0; }
struct node* addToEmpty(struct node*last, int data) { struct node *temp = (struct node *)malloc(sizeof( struct node)); temp->item = data; last = temp; last->next = last; return last; }
struct node *insertCurrent(struct node *last, int data)
Explanation of code:
For the addEmpty code, allocate an empty node using the malloc function. For this node, place the data to the temp variable. Assign and link the only variable to the temp variable Return the last element to the main() / application context.
struct node *insertCurrent(struct node *last, int data) { if(last == NULL) { return addToEmpty(last, data); } struct node *temp = (struct node *)malloc(sizeof( struct node)); temp -> item = data; temp->next = last->next; last->next = temp; return last; } struct node *insertAfter(struct node *last, int data, int item) { struct node *temp = last->next, *prev = temp, *newnode =NULL; …
Explanation of code
If there is no element to insert, then you should make sure to add to an empty list and return control. Create a temporary element to place after the current element. Link the pointers as shown. Return the last pointer as in the previous function.
… struct node *insertAfter(struct node *last, int data, int item) { struct node *temp = last->next, *prev = temp, *newnode =NULL; if (last == NULL) { return addToEmpty(last, item); } do { prev = temp; temp = temp->next; } while (temp->next != last && temp->item != data );
if(temp->item != data)
{
printf("Element not found. Please try again");
…
Explanation of code:
If there is no element in the list, ignore the data, add the current item as the last item in the list and return control For every iteration in the do-while loop ensure that there is a previous pointer that holds the last-traversed result. Only then can the next traversal occur. If the data is found, or temp reaches back to the last pointer, the do-while terminates. The next section of code decides what has to be done with the item.
… if(temp->item != data) { printf(“Element not found. Please try again”); return last; } else { newnode = (struct node *)malloc(sizeof(struct node)); newnode->item = item; prev->next = newnode; newnode->next = temp; } return last; }
struct node *removeCurrent(struct node *last) …
Explanation of code:
If the entire list has been traversed, yet the item is not found, display an “item not found” message and then return control to the caller. If there is a node found, and/or the node is not yet the last node, then create a new node. Link the previous node with the new node. Link the current node with temp (the traversal variable). This ensures that the element is placed after a particular node in the circular linked list. Return to the caller.
struct node *removeCurrent(struct node *last) { if(last == NULL) { printf(“Element Not Found”); return NULL; } struct node *temp = last->next; last->next = temp->next; free(temp); return last; }
struct node *removeAfter(struct node *last, int data)
Explanation of code
To remove only the last (current) node, check if this list is empty. If it is, then no element can be removed. The temp variable just traverses one link forward. Link the last pointer to the pointer after the first. Free the temp pointer. It deallocates the un-linked last pointer.
struct node *removeAfter(struct node *last,int data) { struct node *temp = NULL,*prev = NULL; if (last == NULL) { printf(“Linked list empty. Cannot remove any element\n”); return NULL; } temp = last->next; prev = temp; do { prev = temp; temp = temp->next; } while (temp->next != last && temp->item != data );
if(temp->item != data)
{
printf("Element not found");
…
Explanation of code
As with the previous removal function, check if there is no element. If this is true, then no element can be removed. Pointers are assigned specific positions to locate the element to be deleted. The pointers are advanced, one behind the other. (prev behind temp) The process continues until an element is found, or the next element retraces to the last pointer.
if(temp->item != data)
{
printf("Element not found");
return last;
}
else
{
prev->next = temp->next;
free(temp);
}
return last;
}
void peek(struct node * last) { struct node *temp = last; if (last == NULL) { return;
Explanation of program
If the element found after traversing the entire linked list, an error message is displayed saying the item was not found. Otherwise, the element is delinked and freed in steps 3 and 4. The previous pointer is linked to the address pointed as “next” by the element to be deleted (temp). The temp pointer is therefore deallocated and freed.
…
void peek(struct node * last)
{
struct node *temp = last;
if (last == NULL)
{
return;
}
if(last -> next == last)
{
printf("%d-", temp->item);
}
while (temp != last)
{
printf("%d-", temp->item);
temp = temp->next;
}
}
Explanation of code
The peek or traversal is not possible if there are zero needed. The user needs to allocate or insert a node. If there is only one node, there is no need to traverse, the node’s content can be printed, and the while loop does not execute. If there is more than one node, then the temp prints all the item till the last element. Moment the last element is reached, the loop terminates, and the function returns call to the main function.
Applications of the Circular Linked List
Implementing round-robin scheduling in system processes and circular scheduling in high-speed graphics. Token rings scheduling in computer networks. It is used in display units like shop boards that require continuous traversal of data.
