A circular linked list is identical to a single linked list with the exception that the end node in the list refers to the initial node. This means that a circular linked list is a collection of elements in which each element has a connection to the next element in the sequence, and the last element has a link to the first element in the collection. We can start at any node in a circular linked list and traverse it in any direction, forward or backward, until we reach the same node from where we started. As a result, a circular linked list has no beginning and no endpoint. There is no end to a circular linked list. As a result, the FIRST and LAST nodes in a linked list must be determined. In operating systems, circular linked lists are commonly used for task maintenance. As the circular linked list has a dynamic size, memory may be allocated only when it is needed.
Representation of a Circular Linked List
Each node contains two parts, just like in a singly linked list. The first section provides data, while the second section directs you to the next node. In the real memory, it holds the address of the next node.
The structure of a doubly linked list in C is as follows:
struct node
{
int num;
struct node*next ;
};
typedef struct Node node ;
node * start = NULL ;
node * last = NULL ;
Basic Operations on Circular Linked List
The following procedures are performed on a circular linked list:
- Insertion
- Deletion
Insertion
In this part, we’ll look at how to add a new node to an existing linked list. We’ll look at three different scenarios and see how each one is handled:
- Insertion in the beginning.
- Insertion at the end.
- Insertion at Specific Point
Insertion in the Beginning
The instructions below can be used to add a new node to the circular linked list’s beginning:
Step 1: Check for Overflow
if ptr = Null then
print overflow
Exit
else
ptr = (node *) malloc (size of (node));
End if
Step 2: if start = Null then
set ptr -> num = item
set ptr -> next = ptr
start = ptr
last = ptr
End if
Step 3: set ptr -> num = item
Step 4: set ptr -> next = start
Step 5: set start = ptr
Step 6: set last -> next = ptr
Step 7: EXIT
Insertion at the End
The instructions below can be used to add a new node to the circular linked list’s end:
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE -> NEXT = START
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR -> NEXT != START
Step 8: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 9: SET PTR -> NEXT = NEW_NODE
Step 10: SET NEW_NODE -> PREV = PTR
Step 11: SET START -> PREV = NEW_NODE
Step 12: EXIT
Insertion at Specific Point
These methods are used to put data into a circular linked list at a specified point.
- Terminate the function if the circular linked list is empty.
- If not, create two node pointers.
- Create a new node to store the data. Now, navigate to the desired location and place this new node there.
- Connect the pointer of this new node to the node that was previously existing at this location.
- To observe the outcome, print the new circular linked list.
Deletion
In this part, we’ll look at how to remove a node from a circular linked list that already exists. We’ll look at three scenarios and see how each one is handled.
- Deletion of the first node.
- Deletion of the last node.
- Deletion from Specific Point.
Deletion of the First Node
The instructions below can be used to remove a node from the circular linked list’s beginning:
Step 1: Check for Overflow
if start = Null then
print list is empty
Exit
End if
Step 2: set ptr = start
Step 3: set start = start -> next
Step 4: print Element deleted is , ptr -> info
Step 5: set last -> next = start
Step 6: free ptr
Step 7: EXIT
Deletion of the Last Node
The instructions below can be used to remove a node from the circular linked list’s end:
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR NEXT != START
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR NEXT [END OF LOOP]
Step 6: SET PREPTR NEXT = START
Step 7: FREE PTR
Step 8: EXIT
START is used to initialize the pointer variable PTR, i.e., PTR now points to the linked list’s first node. We use another pointer variable PREPTR in the while loop so that PREPTR always refers to one node before PTR. We set the next pointer of the second last node to START after we reach the last node and the second last node, making it the (new) final node of the linked list.
Deletion from Specific Point
Deletion from the nth place in a circular linked list is one of the deletion operations that we commonly execute on this type of list. We utilize pointers to traverse the circular linked list and conduct deletion from a specified position. These instructions are used to delete a specified place in a circular linked list:
- Initialize the p and q node pointers.
- Create a variable called k that will serve as a counter variable.
- Set the value of del to pos-1.
- Repeat step 5 until k does not equal del.
- Make q=p and p=p->next in this loop.
- After each successful repetition, increase the value of k by one.
- Make the next of q equal to the next of p.
- Delete the node referred to by the node pointer p.