Data structure tutorial 6: Circular Doubly Linked List

 In this chapter we shall learn about below topics:

In the previous chapter we saw how to create a Doubly Linked List. In this chapter we shall learn about circular doubly linked list.

1. Insert Rear

2. Delete element when a key is given

3. Display all the elements

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

#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;
}

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