Circular Singly Linked List

 Circular Singly Linked List

A circular linked list is a sequence of elements in which every element has a link to its next element in the sequence and the last element has a link to the first element.

We traverse a circular singly linked list until we reach the same node where we started. The circular singly liked list has no beginning and no ending. There is no null value present in the next part of any of the nodes.

When we traverse the DATA and NEXT in this manner, we will finally see that the linked list in above Fig. stores characters that when put together form the word HELLO.

In above fig. Two different linked lists are simultaneously maintained in the memory.

There is no ambiguity in traversing through the list because each list maintains a separate START pointer which gives the address of the first node of the respective linked list. The remaining nodes are reached by looking at the value stored in NEXT.

By looking at the figure, we can conclude that the roll numbers of the students who have opted for Biology are S01, S03, S06, S08, S10, and S11.

Similarly, the roll numbers of the students who chose Computer Science are S02, S04, S05, S07, and S09.

Insertion

Inserting a New Node in a Circular Linked List

In a circular linked list, the insertion operation can be performed in three ways. They are as follows...

1. Inserting At Beginning of the list
2. Inserting At End of the list

1.Inserting a Node at the Beginning of a Circular Linked List

We can use the following steps to insert a new node at beginning of the circular linked list...

• Step 1 - Create a newNode with given value.
• Step 2 - Check whether list is Empty (head == NULL)
• Step 3 - If it is Empty then, set head = newNode and newNode→next = head .
• Step 4 - If it is Not Empty then, define a Node pointer 'temp' and initialize with 'head'.
• Step 5 - Keep moving the 'temp' to its next node until it reaches to the last node (until 'temp → next == head').
• Step 6 - Set 'newNode → next =head', 'head = newNode' and 'temp → next = head'.

In Step 1, we first check whether memory is available for the new node. If the free memory has exhausted, then an OVERFLOW message is printed. Otherwise, if free memory cell is available, then we allocate space for the new node. 

Set its DATA part with the given VAL and the NEXT part is initialized with the address of the first node of the list, which is stored in START. 

Now, since the new node is added as the first node of the list, it will now be known as the START node, that is, the START pointer variable will now hold the address of the NEW_NODE.

While inserting a node in a circular linked list, we have to use a while loop to traverse to the last node of the list. Because the last node contains a pointer to START, its NEXT field is updated so that after insertion it points to the new node which will be now known as START.

ex: Suppose we want to add a new node with data 9 as the first node of the list. Then the following changes will be done in the linked list.

2.Inserting a Node at the End of a Circular Linked List

Suppose we want to add a new node with data 9 as the last node of the list. Then the following changes will be done in the linked list.

In Step 6,we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. 

In the while loop, we traverse through the linked list to reach the last node. Once we reach the last node, in Step 9, we change the NEXT pointer of the last node to store the address of the new node. 

Remember that the NEXT field of the new node contains the address of the first node which is denoted by START.

DELETION:

Here we consider two cases, Rest of the cases of deletion are same as that given for singly linked

lists.

Case 1: Deleting the First Node from a Circular Linked List

Case 2: Deleting the Last Node from a Circular Linked List

1.Deleting the First Node from a Circular Linked List

In Step 1 of the algorithm, we check if the linked list exists or not. If START = NULL, then it signifies that there are no nodes in the list and the control is transferred to the last statement of the algorithm.

However, if there are nodes in the linked list, then we use a pointer variable PTR which will be used to traverse the list to ultimately reach the last node. 

In Step 5, we change the next pointer of the last node to point to the second node of the circular linked list.

In Step 6, the memory occupied by the first node is freed. Finally, in Step 7, the second node now becomes the first node of the list and its address is stored in the pointer variable START.

2.Deleting the Last Node from a Circular Linked List

In Step 2, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. 

In the while loop, we take another pointer variable PREPTR such that PREPTR always points to one node before PTR. 

Once we reach the last node and the second last node, we set the next pointer of the second last node to START, so that it now becomes the (new) last node of the linked list. The memory of the previous last node is freed and returned to the free pool.