![\"Singly](\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/06\/Circular-linked-list-normal-image1.jpg\")
<\/a><\/p>\n2. Doubly Circular Linked List<\/h4>\n
A doubly linked list points to not only the next node but to the previous node as well. A circular doubly linked list contains 2 NULL pointers. The \u2018Next\u2019 of the last node points to the first node in a doubly-linked list.\u00a0The \u2018Prev\u2019 of the first node points to the last node.<\/p>\n
A doubly circular linked list looks as follows:<\/p>\n
Memory representation defines how a linked list is stored in the main memory.<\/p>\n A singly circular list consists of only one addition pointer named \u2018Next\u2019. The \u2018Next\u2019 of each node, except the last node will contain the address of the upcoming node.\u00a0The last node\u2019s \u2018Next\u2019 will store the address of the first node.<\/p>\n For a singly linked list, the memory will be represented as follows:<\/p>\n In a doubly-linked list, there are two additional pointers: \u2018Next\u2019 and \u2018Prev\u2019.\u00a0The \u2018Next\u2019 of each node links to the address of the upcoming node\u2019s \u2018Prev\u2019. The \u2018Next\u2019 of the last node links to the first node.\u00a0The \u2018prev\u2019 of each node has the address of the previous node. The \u2018Prev\u2019 of the first node links to the last node.<\/p>\n The memory representation diagram for the doubly linked list is:<\/p>\n A circular linked list has some real-life applications such as:<\/p>\n 1. In multi-player games, all the players are kept\/arranged in a circular linked list form. This gives a fixed turn number to every player.<\/p>\n 2. Circular linked lists are implied in our computer\u2019s operating system for scheduling various processes. In many cases, a lot of processes are aligned and they need to use the same resource. In such cases, they are put into a circular linked list and given a fixed time slot for execution.<\/p>\n 3. We can also implement a circular queue using a circular linked list. This will help to reduce the number of pointers from 2 to 1 because a circular linked list will require only one pointer.<\/p>\n The traversal operation includes traveling through all the nodes of the linked list and displaying their values if needed.<\/p>\n The function for traversal operation in a circular linked list is as follows:<\/p>\n Display operation is used to print the value of all the nodes. To display a list, we need to traverse all its nodes and print their values.<\/p>\n The following function depicts the display operation in a circular linked list.<\/p>\n Insertion operation is used to insert nodes in a linked list. Let us see two different cases for insertion:<\/p>\n Since a circular list could be both a singly circular list and a doubly circular linked list, let us check the insertion operation for both of them.<\/p>\n i. Singly circular linked list:<\/strong><\/p>\n We will insert a node at the front of the list in the following way:<\/p>\n The above diagram shows that initially, the list was A\u2192B\u2192C\u2192D.<\/p>\n After inserting a new node, the final list is E\u2192A\u2192B\u2192C\u2192D.<\/p>\n The function for performing this operation is as follows:<\/p>\n ii. Doubly circular linked list:<\/strong><\/p>\n 1. Insertion operation will lead to the shifting of various pointers in the list.<\/p>\n 2. We insert a node at the beginning such that the next pointer points to the node which was at first before.<\/p>\n 3. Let us take an example: Let us try inerting M into the list as shown:<\/p>\n Thus, the new list will be M\u2192A\u2192B\u2192C\u2192D.<\/p>\n The function for the above operation is:<\/p>\n This operation will add a node at the end of the circular linked list.<\/p>\n i. Singly linked list:<\/strong><\/p>\n a. To insert a node at the end of the list, we first need to traverse the whole list.<\/p>\n <\/p>\n b. The function for insertion at the end is:<\/p>\n ii. Doubly linked list:<\/strong><\/p>\n a. If the list is empty, we will insert a node after the Head.<\/p>\n b. If the list is not empty, we first need to traverse the whole list to insert a node at the end of the list.<\/p>\n Suppose we wish to insert the node \u2018M\u2019 at the end of the list, the list then will be A\u2192B\u2192C\u2192D\u2192M as shown:<\/p>\n The function will be:<\/p>\n a. It involves deleting the first node from the linked list.<\/p>\n b. Suppose we have a list A\u2192B\u2192C\u2192D and we wish to delete D from it, we will do it as follows:<\/p>\n The function for the deletion operation will be:<\/p>\n While writing its function, we take into consideration three different cases:<\/p>\n 1. When the list is empty<\/p>\n 2. When the list has only one node<\/p>\n 3. When the list has two or more nodes<\/p>\n 1. If we wish to delete the first node from a doubly-linked list, we need to make the Head point to the second node.<\/p>\n 2. Suppose we have a doubly-linked list: A\u2192B\u2192C\u2192D.<\/p>\n 3. On deleting the first node, we will get B\u2192C\u2192D.<\/p>\n 4. The pointer adjustments are shown below:<\/p>\n The pseudo-code for deleting operation will be:<\/p>\n 1. It involves deleting the last node of the circular linked list.<\/p>\n 2. But, a circular linked list has all the nodes inter-connected to each other, so technically there is no last node.<\/p>\n 3. If we want to delete the last node, we will check out which node\u2019s \u2018Next\u2019 points to the first node and we will delete that node.<\/p>\n i. Singly-linked list<\/strong><\/p>\n While deleting the last node, we take into consideration three cases:<\/p>\n a. When the list is empty<\/p>\n b. When the list contains a single node<\/p>\n c. When the list contains two or more nodes<\/p>\n Suppose we have a list A\u2192B\u2192C\u2192D. On deleting the last node, we get A\u2192B\u2192C as shown below:<\/p>\n<\/a><\/p>\nMemory Representation of Circular Linked List<\/h3>\n
1. Singly Circular Linked List<\/h4>\n
<\/a><\/p>\n2. Doubly Circular Linked List<\/h4>\n
<\/a><\/p>\nApplications of Circular Linked List<\/h3>\n
Basic operations on a Circular Linked List:<\/h3>\n
1. Traversal Operation:<\/h4>\n
Traversal()\n{\n if (Head == NULL)\n return;\n else\n {\n Ptr = Head;\n while(Ptr->Next != Head)\n {\n Ptr = Ptr->Next;\n print(data);\n }\n }\n}\n<\/pre>\n2. Display Operation:<\/h4>\n
Display_listl()\n{\n if (Head == NULL)\n return;\n else\n {\n Ptr = Head;\n while(Ptr->Next != Head)\n {\n Ptr = Ptr->Next;\n display(data);\n }\n }\n}\n<\/pre>\n3. Insertion Operation:<\/h4>\n
a. Insertion at the beginning:<\/h5>\n
<\/a><\/p>\nInsert_at_beginning_Singly(struct Node* Head, int key)\n{\n Ptr = (struct Node *) malloc(sizeof(struct Node)); \/\/Allocating memory for new Node\n if(Head == NULL) \/\/When the list is empty\n { \n Head = Ptr; \n Ptr->Next = Head; \n } \n temp = Head; \n while(temp->next != head) \n temp = temp->next; \n temp->Next = Ptr; \/\/Making the last node point to the first node \n Ptr->Next = Head;\n Head = Ptr; \n}\n<\/pre>\n
\nInitially, let the list be A\u2192B\u2192C\u2192D.<\/p>\n<\/a><\/p>\nInsert_at_beginning_Doubly(struct Node* Head, int key)\n{\n Ptr = (struct Node *) malloc(sizeof(struct Node)); \/\/Allocating memory for new Node\n if(Head == NULL) \/\/When the list is empty\n { \n Head = Ptr; \n Ptr->Next = Head; \n Ptr->Prev = Head; \n } \n temp = Head; \n while(temp->Next != Head) \n temp = temp->Next; \n temp->Next = Ptr; \n Ptr->Prev = temp; \n Head -> Prev = Ptr; \n Ptr->Next = Head; \n Head = Ptr; \n}\n<\/pre>\nb. Insertion at the end:<\/h5>\n
<\/a><\/p>\nInsert_at_end_singly(struct Node* Head, int key)\n{\n Ptr = (struct Node *) malloc(sizeof(struct Node)); \/\/Allocating memory for new Node\n if(Head == NULL) \/\/When the list is empty\n { \n Head = Ptr; \n Ptr->Next = Head; \n } \n temp = Head; \n while(temp->Next != Head) \n temp = temp->Next; \n temp->Next = Ptr; \n Ptr->Next = Head; \n}\n<\/pre>\n<\/a><\/p>\nInsert_at_end_doubly(struct Node* Head, int key)\n{\n Ptr = (struct Node *) malloc(sizeof(struct Node)); \/\/Allocating memory for new Node\n if(Head == NULL) \/\/When the list is empty\n { \n Head = Ptr; \n Ptr->Next = Head; \n Ptr->Prev = Head;\n } \n Head->Prev = Ptr; \n Ptr->Next = Head; \n temp->Next = Ptr; \n Ptr->Prev = temp; \n}\n<\/pre>\n4. Deletion from the beginning:<\/h4>\n
a. Singly linked list:<\/h5>\n
<\/a><\/p>\nDelete_from_brginning_sngly(struct Node* Head)\n{\n Ptr = (struct Node *) malloc(sizeof(struct Node)); \/\/Allocating memory for new Node\n if(Head == NULL) \/\/When the list is empty\n return;\n if(Head->Next == Head) \/\/When the list contains a single node\n { \n Head = NULL; \n free(Head); \n } \n Ptr = Head; \n while(Ptr->Next != Head) \n Ptr = Ptr->Next; \n Ptr->Next = Head->Next;\n free(Head);\n}\n<\/pre>\nb. Doubly linked list:<\/h5>\n
<\/a><\/p>\nDeletion_from_beginning_doubly(int key){\n \n if (Head == NULL) \/\/If the list is empty\n {\n free(Head);\n return;\n }\n temp = head; \n while(temp->Next != head) \n temp = temp->Next; \n temp->Next = Head->Next; \/\/Make temp point to the last node of the list\n Head->Next->Prev = temp; \/\/the new Head must also point to the last node\n free(Head); \n Head = temp->Next; \/\/Make the pointer next to Head as the new Head\n}\n<\/pre>\na. Deletion at the End<\/h5>\n