CIRCULAR LINKED LISTS
In a circular linked list, the last node contains a pointer to the first node of the list. We can have a circular singly linked list as well as a circular doubly linked list. While traversing a circular linked list, we can begin at any node and traverse the list in any direction, forward or backward, until we reach the same node where we started. Thus, a circular linked list has no beginning and no ending.
The only downside of a circular linked list is the complexity of iteration. Note that there are no NULL values in the NEXT part of any of the nodes of list.
Circular linked lists are widely used in operating systems for task maintenance. We will now discuss an example where a circular linked list is used. When we are surfing the Internet, we can use the Back button and the Forward button to move to the previous pages that we have already visited. How is this done? The answer is simple. A circular linked list is used to maintain the sequence of the Web pages visited. Traversing this circular linked list either in forward or backward direction helps to revisit the pages again using Back and Forward buttons. We can traverse the list until we find the NEXT entry that contains the address of the first node of the list. This denotes the end of the linked list, that is, the node that contains the address of the first node is actually the last node of the list.
Inserting a New Node in a Circular Linked List
In this video, we will see how a new node is added into an already existing linked list. We will take two cases and then see how insertion is done in each case:
Case 1: The new node is inserted at the beginning of the circular linked list.
Case 2: The new node is inserted at the end of the circular linked list.
Inserted at the beginning
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 11
(END OF IF)
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = NEXT[AVAIL]
Step 4: SET DATA[NEW_NODE] = VAL
Step 5: SET PTR = START
Step 6: Repeat Step 7 while NEXT[PTR] != START
Step 7: PTR = NEXT[PTR]
[END OF LOOP]
Step 8: SET NEXT[NEW_NODE] = START
Step 9: SET NEXT[PTR] = NEW_NODE
Step 10: SET START = NEW NODE
Step 11: EXIT
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 value 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.
Inserting a Node at the End of a Circular Linked List
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 10
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = NEXT[AVAIL]
Step 4: SET DATA[NEW_NODE] = VAL
Step 5: SET NEXT[NEW_NODE] = START
Step 6: SET PTR = START
Step 7: Repeat Step 8 while NEXT[PTR] != START
Step 8: SET PTR = NEXT[PTR]
[END OF LOOP]
Step 9: SET NEXT[PTR] = NEW_NODE
Step 10: EXIT
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.
Deleting a Node from a Circular Linked List
In this video, we will discuss how a node is deleted from an already existing circular linked list. We will take two cases and then see how deletion is done in each case. Rest of the cases of deletion are same as that given for singly linked lists.
Case 1: The first node is deleted.
Case 2: The last node is deleted.
Deleting the First Node from a Circular Linked List
When we want to delete a node from the beginning of the list, then the following changes will be done in the linked list.
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 while NEXT[PTR] != START
Step 4: SET PTR = NEXT[PTR]
[END OF LOOP]
Step 5: SET NEXT[PTR] = NEXT[START]
Step 6: FREE START
Step 7: SET START = NEXT[PTR]
Step 8: EXIT
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.
Deleting the Last Node from a Circular Linked List
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 NEXT[PTR] != START
Step 4: SET PREPTR = PTR
Step 5: SET PTR = NEXT[PTR]
[END OF LOOP]
Step 6: SET NEXT[PREPTR] = START
Step 7: FREE PTR
Step 8: EXIT
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.
0 Comments