In the second chapter we say how to create a Doubly Linked List. In this chapter we shall learn about circular doubly linked list.
Below is the representation of Circular Double Linked List:
Operations performed on Circular Doubly Linked List that we are going to learn in this tutorial.
- Insert Rear
- Delete element when a key is given
- Display all the elements
- Insert Rear
If there is only 1 node, then make prev pointer of new node to itself. Then assign the head pointer to the new node. Then assign the next pointer of the new node to head node.
else
If there are other elements, then traverse till the last element. Then point the prev pointer of the new node to the last node, then point the next pointer of the new node to the head node.
Working of Delete and Display is as shown in the code:
Implementation of Circular Doubly Liked List in C++
#include<iostream> using namespace std; struct Node { int val; Node *prev; Node *next; }; Node *head; void insert_rear(int value) { // create a new node to save the value Node *newNode = new Node; //update the value newNode->val = value; if(head == NULL) { //if the head is null //assign the prev to newNode newNode->prev = newNode; //assign newNode as head node head = newNode; //assign next to head node newNode->next=head; } else { //if the head is not null // take a temp node to go to last node Node* temp = head->prev; //assign the newNode as last node head->prev = newNode; //assign the newNode to temp node newNode->prev = temp; //assign the next of newNode to head node making it as last node newNode->next = head; //assign next node of temp node to new node. temp->next = newNode; } } void remove(int x) { if(head == NULL) { printf("\nList is Empty.\n"); return; } else { if(head->val == x) { //if the head value is equal to element to be deleted if(head->next == head) { //if there is only 1 element head=NULL; } else { Node* temp = head->prev; head = head->next; head->prev = temp; temp->next = head; } return; } Node* temp = head->next; while(temp != head && temp->val != x) { temp = temp->next; } if(temp == head) { printf("Value not found in list\n"); } else { temp->prev->next = temp->next; temp->next->prev = temp->prev; } } } void search(int x) { Node *temp = head; int found = 0; do { if(temp->val == x) { cout<<"\nFound"; found = 1; break; } temp = temp->next; }while(temp != head); if(found == 0) { cout<<"\nNot Found"; } } void display() { Node *temp = head; do { cout<< temp->val<<"\t"; temp = temp->next; }while(temp != head); } int main() { int choice, x; do { cout<<"\n1. Insert"; cout<<"\n2. Delete"; cout<<"\n3. Search"; cout<<"\n4. Display"; cout<<"\n5. Exit"; cout<<"\n\nEnter you choice : "; cin>>choice; switch (choice) { case 1 : cout<<"\nEnter the element to be inserted at rear : "; cin>>x;; insert_rear(x); break; case 2 : cout<<"\nEnter the element to be removed : "; cin>>x; remove(x); break; case 3 : cout<<"\nEnter the element to be searched : "; cin>>x; search(x); break; case 4 : display(); break; } } while(choice != 5); return 0; }
Output:
1. Insert 2. Delete 3. Search 4. Display 5. Exit Enter you choice : 1 Enter the element to be inserted at rear : 1 1. Insert 2. Delete 3. Search 4. Display 5. Exit Enter you choice : 1 Enter the element to be inserted at rear : 2 1. Insert 2. Delete 3. Search 4. Display 5. Exit Enter you choice : 1 Enter the element to be inserted at rear : 3 1. Insert 2. Delete 3. Search 4. Display 5. Exit Enter you choice : 1 Enter the element to be inserted at rear : 4 1. Insert 2. Delete 3. Search 4. Display 5. Exit Enter you choice : 1 Enter the element to be inserted at rear : 5 1. Insert 2. Delete 3. Search 4. Display 5. Exit Enter you choice : 4 1 2 3 4 5 1. Insert 2. Delete 3. Search 4. Display 5. Exit Enter you choice : 2 Enter the element to be removed : 4 1. Insert 2. Delete 3. Search 4. Display 5. Exit Enter you choice : 4 1 2 3 5 1. Insert 2. Delete 3. Search 4. Display 5. Exit Enter you choice : 5
Further Reading: