Can a linked list be circular?
If you are not familiar with the LinkedList, I would highly recommend having a look at my blog: Show
In this tutorial, we will learn circular linked list in-depth by dividing topics in the following manner:
Definition of circular linked listIn a circular linked list, elements are stored in random memory locations.
Unlike, singly linked list in which the last node of the contains a pointer to null to represent the termination of a linked list, in circular linked list, last node of linked list will point to the first node of the linked list. Types of Circular Linked List:There are two types of Circular linked list. i.e. we can make a circular linked list by modifying the Singly linked list as well as Doubly linked list. 1. Singly circular linked listThe above diagram is an example of a singly linked list in which the last node(Tail) points to NULL to represent the termination of the linked list. Now, one question which might come into your mind is, how do we get to know termination condition, right? Well, one thing you might do is, keep a track of head node and whenever we encounter it again, we say that we have traversed our whole linked list and Now it is time to terminate. if (temp==head) ===> We have traversed whole linked list. 2. Doubly circular linked listThe above diagram is an example of doubly linked list in which the prev of head points to NULL and last node(Tail) points to NULL to represent the termination of linked list. In this case, keep a track of head node and whenever we encounter it again, we say that we have traversed whole linked list and now it is time to terminate. You could have taken a temp=head->next and start traversing linked list and check for whether our temp is head or not. Operations on Circular linked listA. TraversalTraversal in Circular linked list is similiar to singly or doubly linked list, we just need to take care of termination condition. In this case termination condition would be, If we reach again to our head node. To perform this task do the following: Node *temp=head->next;
while(temp!=head)
{
if(temp->data==ElementToFind) {
cout<<"Element found"< Enter fullscreen mode Exit fullscreen mode B. InsertionInsertion in Circular linked list will be exactly same as in singly linked list except inseting node at front and at last position.
To insert a node at front, We need to know about the last node of linked list. Create a new node and link it with exisiting list as mentioned below: LastNode->next=newNode;
newNode->next=head;
Enter fullscreen mode Exit fullscreen mode After, linking nodes, we need to update the head of linked list as we are inserting at the front and front node represent the head of linked list. head=newNode;
Enter fullscreen mode Exit fullscreen mode
It is similiar to inserting node at front. The only difference is that we don't need to update head in this case. C. Deletion
To delete in between node, find prev and next node of the node which needs to be deleted. curr = head;
while(curr!=nodetoDelete) {
prev = curr;
curr = curr->next;
}
prev->next=curr->next;
delete curr;
Enter fullscreen mode Exit fullscreen mode
To delete a Node from front, We need to know about the last node of linked list. ptr = head;
while(ptr ->next != head) {
ptr = ptr->next;
}
temp = head;
ptr -> next = temp->next;
// update head node
head =head->next;
delete temp;
Enter fullscreen mode Exit fullscreen mode
It is similiar to deleting node at front. The only difference is that we won't be updating head in this case. ptr = head;
while(ptr ->next != head) {
preptr=ptr;
ptr = ptr->next;
}
preptr->next = ptr -> next;
Enter fullscreen mode Exit fullscreen mode D. Advantages of Circular linked list
E. Disadvantage of circular linked list
F. Applications of Circular linked list
G. Implementation#include
Enter fullscreen mode Exit fullscreen mode |