Chapter 3, Problem 18E

Program Plan Intro

Implementation of circular doubly linked list:

Program plan:

• Create a class IntCircularDLList for circular list using doubly linked list.
• Create a structure IntCircularDLLNode for list node.
• Define a function “createNode()” to create a circular doubly linked list node.
• Define a function named “displayList()” for printing the list.
• Define a function named “addToHead()” to add node at head.
• Define a function named “addToTail()” to add node at tail.
• Define a function named “isInList()” for checking the availability of the node in the list.
• Define a function named “deleteNode()” to delete a node at a specific position in the list.
• Define a function named “deleteFromHead()” to delete a node at head.
• Define a function named “deleteFromTail()” to delete a node at a tail.
• Define a function named “isEmpty()” for checking the availability of nodes in the list.

Program Description Answer

/***********************************************************

* This program shows the implementation of Circular Doubly *

* Linked List using class                                  *

***********************************************************/

Explanation of Solution

Program:

// Include the necessary header files.

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;

Define a structure “IntCircularDLLNode” for circular doubly linked list node.

// Declaration of node.

struct IntCircularDLLNode

{

// Declaration of node element.

int element;

// Declaration of node next pointer.

struct IntCircularDLLNode *nextPtr;

// Declaration of node previous pointer.

struct IntCircularDLLNode *prevPtr;

}

// Declaration of start and last pointers.

*startPtr, *lastPtr;

// Declare and initialize the counter value.

int counter = 0;

Define a class “IntCircularDLList” for circular doubly linked list.

// Declaration of list class.

class IntCircularDLList

{

// Access specifier.

public:

// Function declaration to create list.

IntCircularDLLNode *createNode(int);

// Function declaration to insert node at head.

void addToHead(int);

// Function declaration to insert node at tail.

void addToTail(int);

// Function declaration to delete a node at head.

int deleteFromHead();

// Function declaration to delete a node at tail.

int deleteFromTail();

/* Function declaration to delete a node at given index.*/

void deleteNode(int);

/* Function declaration to check whether an element is in the list or not. */

bool isInList(int);

// Function declaration to print the list.

void displayList();

/* Function declaration to check whether the list empty or not */

int isEmpty();

Define a constructor “IntCircularDLList()” with no arguments.

// Definition for constructor.

IntCircularDLList()

{

// Assign NULL to start pointer.

startPtr = NULL;

// Assign NULL to end pointer.

lastPtr = NULL;

}

Define a destructor “~IntCircularDLList()” for freeing the memory.

// Definition for destructor.

~IntCircularDLList(){}

};

Define a “main()” to create, insert, delete, search and traverse a circular doubly linked list by calling the respective functions defined.

// Function main().

int main()

{

// Declaration of variable for user selection.

int userChoice;

// Creation of object for the list.

IntCircularDLList cdll;

Execute “while” loop to iterate through the operations to be applied on the circular doubly linked list.

// While loop to iterate through the operations.

while (1)

{

// Output Menu Display.

cout<<endl<<"---------------------------"<<endl;

cout<<"Doubly Circular linked list";

cout<<endl<<"---------------------------"<<endl;

cout<<"1.Insert to Head"<<endl;

cout<<"2.Insert to Tail"<<endl;

cout<<"3.Delete from Head"<<endl;

cout<<"4.Delete from Tail"<<endl;

cout<<"5.Delete Node"<<endl;

cout<<"6.Search Node"<<endl;

cout<<"7.Display List"<<endl;

cout<<"8.Is List Empty?"<<endl;

cout<<"9.Exit"<<endl;

// Prompt for the user selection.

cout<<"Enter your selection : ";

// Get the user selection of choice.

cin>>userChoice;

Use “switch” condition to execute the code block based on user input.

/* Execute switch case based on the user selection. */

switch(userChoice)

{

Execute “case 1” to insert a node to head when the user enters 1.

// Case 1 for inserting values at the head.

case 1:

/* Declaration of variable for insertion. */

int nodeElement1;

// Prompt for element to insert.

cout<<endl<<"Enter the element to be inserted: ";

// Gets the element from the user.

cin>>nodeElement1;

// Function call to addToHead().

cdll.addToHead(nodeElement1);

break;

Execute “case 2” to insert a node to tail when the user enters 2.

// Case 2 for inserting values at the tail.

case 2:

/* Declaration of variable for insertion. */

int nodeElement2;

// Prompt for element to insert.

cout<<endl<<"Enter the element to be inserted: ";

// Gets the element from the user.

cin>>nodeElement2;

// Function call to addToTail().

cdll.addToTail(nodeElement2);

break;

Execute “case 3” to delete a node from the head when the user enters 3.

// Case 3 for deleting values at the head.

case 3:

// Function call to deleteFromHead().

cdll.deleteFromHead();

break;

Execute “case 4” to delete a node from the tail when the user enters 4.

// Case 4 for deleting values at the tail.

case 4:

// Function call to deleteFromTail().

cdll.deleteFromTail();

break;

Execute “case 5” to delete a node based on the index when the user enters 5.

/* Case 5 for deleting values at the specific index. */

case 5:

/* Declaration of variable for node's position. */

int indexOfNode;

// Prompt for node index to remove.

cout<<endl<<"Enter the index of the element to be removed: ";

// Gets the node index.

cin>>indexOfNode;

// Function call to deleteNode

cdll.deleteNode(indexOfNode);

break;

Execute “case 6” to search a node based on the index when the user enters 6.

/* Case 6 for searching the given node element. */

case 6:

/* Declaration of variable for search node element. */

int searchNode;

/* Prompt the user for search node element. */

cout<<endl<<"Enter the value to be searched: ";

// Gets the search node element.

cin>>searchNode;

// Function call to isInList().

cdll.isInList(searchNode);

break;

Execute “case 7” to print the circular doubly linked list when user enters 7.

// Case 7 for displaying the list.

case 7:

// Function call to displayList().

cdll.displayList();

break;

Execute “case 8” to check whether the list emptiness when user enters 8.

/* Case 8 for checking whether the list is empty or not. */

case 8:

// Function call to isEmpty().

cdll.isEmpty();

break;

Execute “case 9” to exit the menu operations when user enters 9.

// Case 9 for exiting the operations.

case 9:

// Exiting.

exit(1);

Execute “default” case when user enters values other than the range 0 to 9.

// Default case.

default:

// Display a warning message.

cout<<"Wrong selection"<<endl;

}

}

return 0;

}

Define a function “createNode()” to create a node for circular doubly linked list by allocating memory for it dynamically.

/* Function definition createNode() to allocate memory for the node dynamically. */

IntCircularDLLNode* IntCircularDLList::createNode(int value)

{

// Increment the counter value.

counter++;

// Declare a temp node pointer.

struct IntCircularDLLNode *tempPtr;

// Allocate memory for the node.

tempPtr = new(struct IntCircularDLLNode);

// Add a element to the node.

tempPtr->element = value;

// Update the next node pointer to NULL.

tempPtr->nextPtr = NULL;

// Update the previous node pointer to NULL.

tempPtr->prevPtr = NULL;

// Return the node.

return tempPtr;

}

Define a function “isEmpty()” to check whether the circular doubly linked list is empty or not.

/* Function definition isEmpty() to check the list emptiness. */

int IntCircularDLList::isEmpty()

{

Use “if” condition to check whether the first node is equal to last node or not and first node is NULL or not.

/* If the start node is last node and start node value is null, then list is empty. */

if (startPtr == lastPtr && startPtr == NULL)

{

// Display the list as empty.

cout<<"List is empty"<<endl;

// Return the empty list.

return 0;

}

Use “else” block when the “if” condition fails.

// Else, show the list.

else

// Display the list.

cout<<"Circular doubly linked list: ";

/* Function call to displayList() to print the list. */

displayList();

}

Define a function “addToHead()” to insert a node to the head position of the circular doubly linked list.

/* Function definition addToHead() to add a node at start of the list. */

void IntCircularDLList::addToHead(int value)

{

// Declare a temp node pointer.

struct IntCircularDLLNode *tempPtr;

/* Function call to createNode() to create a temporary node. */

tempPtr = createNode(value);

Use “if” condition to check whether the first node is equal to last node or not and the first node is NULL or not.

/* If the start node is last node and start node value is null, then add a node. */

if (startPtr == lastPtr && startPtr == NULL)

{

// Display the message.

cout<<"Element inserted in empty list"<<endl;

// Update temp node as start and last node.

startPtr = lastPtr = tempPtr;

/* Update start node next and end node next as NULL. */

startPtr->nextPtr = lastPtr->nextPtr = NULL;

/* Update start node previous and end node previous as NULL. */

startPtr->prevPtr = lastPtr->prevPtr = NULL;

}

Use “else” block when the “if” condition fails.

// Else block if the list already has nodes.

else

{

// New node next points to the start node.

tempPtr->nextPtr = startPtr;

// Start node previous points to new node.

startPtr->prevPtr = tempPtr;

// Make new node as Start node.

startPtr = tempPtr;

// Update start node previous points to last.

startPtr->prevPtr = lastPtr;

// Update last node next points to start node.

lastPtr->nextPtr = startPtr;

// Display the message.

cout<<"Element inserted"<<endl;

}

}

Define a function “addToTail()” to insert a node to the tail position of the circular doubly linked list.

/* Function definition addToTail() to add a node at end of the list. */

void IntCircularDLList::addToTail(int value)

{

// Declare a temp node pointer.

struct IntCircularDLLNode *tempPtr;

/* Function call to createNode() to create a temporary node. */

tempPtr = createNode(value);

Use “if” condition to check whether the first node is equal to last node or not and the first node is NULL or not.

/* If the start node is last node and start node value is null, then add a node. */

if (startPtr == lastPtr && startPtr == NULL)

{

// Display the message.

cout<<"Element inserted in empty list"<<endl;

// Update temp node as start and last node.

startPtr = lastPtr = tempPtr;

/* Update start node next and end node next as NULL. */

startPtr->nextPtr = lastPtr->nextPtr = NULL;

/* Update start node previous and end node previous as NULL. */

startPtr->prevPtr = lastPtr->prevPtr = NULL;

}

Use “else” block when the “if” condition fails.

// Else block if the list already has nodes.

else

{

// Last node next points to the new node.

lastPtr->nextPtr = tempPtr;

// New node previous points to last node.

tempPtr->prevPtr = lastPtr;

// Make new node as last node.

lastPtr = tempPtr;

// Update start node previous points to last.

startPtr->prevPtr = lastPtr;

// Update last node next points to start node.

lastPtr->nextPtr = startPtr;

}

}

Define a function “deleteFromHead()” to delete a node from the head position of the circular doubly linked list.

/* Function definition deleteFromHead() to delete a node at start of the list. */

int IntCircularDLList::deleteFromHead()

{

// Declare a temp node pointer.

IntCircularDLLNode *temp;

Use “if” condition to check whether the first node is equal to last node or not and the first node is NULL or not.

/* If the start node is last node and start node value is null, then list is empty. */

if (startPtr == lastPtr && startPtr == NULL)

{

// Display the list as empty.

cout<<"List is empty"<<endl;

// Return the empty list.

return 0;

}

// Make the temp node as start node.

temp = startPtr;

// Decrement the counter.

counter--;

// Update the last node next as temp node next.

lastPtr->nextPtr = temp->nextPtr;

// Update temp node next and previous as last node.

temp->nextPtr->prevPtr = lastPtr;

// Make start node as new node next.

startPtr = temp->nextPtr;

// Delete the temp node.

free(temp);

// Display the message.

cout<<"Element Deleted"<<endl;

// Return the list.

return 1;

}

Define a function “deleteFromTail()” to delete a node from the tail position of the circular doubly linked list.

/* Function definition deleteFromTail() to delete a node at end of the list. */

int IntCircularDLList::deleteFromTail()

{

// Declare and initialize the position as counter.

int index=counter;

/* Declare a temp node pointer and element node pointer. */

IntCircularDLLNode *ptr, *temp;

Use “if” condition to check whether the first node is equal to last node or not and the first node is NULL or not.

/* If the start node is last node and start node value is null, then list is empty. */

if (startPtr == lastPtr && startPtr == NULL)

{

// Display the list as empty.

cout<<"List is empty"<<endl;

// Return the empty list.

return 0;

}

// Make the temp node as start node.

temp = lastPtr;

// Update the element node as temp node previous.

ptr = temp->prevPtr;

// Update the element node next as temp node next.

ptr->nextPtr = temp->nextPtr;

// Update temp node next and previous as element node.

temp->nextPtr->prevPtr = ptr;

Use “if” condition to check whether the index value is the counter value (last node) or not.

// If the index is equal to the counter

if (index == counter)

{

// Assign element node to Last node.

lastPtr = ptr;

}

// Decrement the counter.

counter--;

// Delete the temp node.

free(temp);

// Display the message.

cout<<"Element Deleted"<<endl;

}

Define a function “deleteNode()” to delete a node at a given index of the circular doubly linked list.

/* Function definition deleteNode() to delete a node at a specific index of the list. */

void IntCircularDLList::deleteNode(int index)

{

/* Declare a temp node pointer and element node pointer. */

IntCircularDLLNode *ptr, *temp;

Use “if” condition to check whether the first node is equal to last node or not and the first node is NULL or not.

/* If the start node is last node and start node value is null, then list is empty. */

if (startPtr == lastPtr && startPtr == NULL)

{

// Display the list as empty.

cout<<"List is empty"<<endl;

// Return the empty list.

return;

}

Use “if” condition to check whether the counter value (last node) is lesser than the given index or not.

// If the counter is lesser than the index, then.

if (counter < index)

{

// Index entered is out of range.

cout<<"Index out of range"<<endl;

// Return the value.

return;

}

// Make the node as the start.

temp = startPtr;

Use “if” condition to check whether the given index is equal to 1 (first node) or not.

// If the index points to the start, then.

if(index == 1)

{

// Decrement the counter.

counter--;

/* Update the last node next to the element node next. */

lastPtr->nextPtr = temp->nextPtr;

/* Update the temp node next and previous to last pointer. */

temp->nextPtr->prevPtr = lastPtr;

// Assign temp next to start.

startPtr = temp->nextPtr;

// Delete the element node.

free(temp);

// Display the message.

cout<<"Element Deleted"<<endl;

// Return the list.

return;

}

Execute “for” loop to iterate through the circular doubly linked list to find the node to be deleted.

/* For loop to iterate the list to find index and delete the node. */

for (int i = 0;i < index - 1;i++ )

{

// Assign temp node next to temp node.

temp = temp->nextPtr;

// Assign temp previous to element.

ptr = temp->prevPtr;

}

// Update element next as temp node next.

ptr->nextPtr = temp->nextPtr;

//  Update temp next and previous as element.

temp->nextPtr->prevPtr = ptr;

Use “if” condition to check whether the given index is equal to counter (last node) or not.

// If the index is the last node.

if (index == counter)

{

// Make the element as last node.

lastPtr = ptr;

}

// Decrement the counter.

counter--;

// Delete the temp node.

free(temp);

// Display the message.

cout<<"Element Deleted"<<endl;

}

Define a function “isInList()” to search a node in the circular doubly linked list or not.

/* Function definition isInList() to search a node in the list. */

bool IntCircularDLList::isInList(int value)

{

// Declare and assign the index as 0.

int index = 0;

// Declare and assign boolean variable as false.

bool myflag = false;

// Declare a temp node pointer.

struct IntCircularDLLNode *temp;

Use “if” condition to check whether the first node is equal to last node or not and the first node is NULL or not.

/* If the start node is last node and start node value is null, then list is empty. */

if (startPtr == lastPtr && startPtr == NULL)

{

// Display the list as empty.

cout<<"The List is empty"<<endl;

// Return the empty list.

return 0;

}

// Make temp node as start node.

temp = startPtr;

Execute “for” loop to iterate through the circular doubly linked list till the last element to find the node to be searched.

// For loop to iterate till the last find the node.

for (int i = 0;i < counter; i++)

{

// Increment the index value.

index++;

Use “if” condition to check whether the list node is equal to user search node or not.

/* If the node element is the user seeking node element, then. */

if (temp->element == value)

{

// Display the element's index.

cout<<"Element "<<value<<" found at index: "<<index<<endl;

// Update flag as true.

myflag = true;

}

// Update the node as node next.

temp = temp->nextPtr;

}

Use “if” condition to check whether the flag value is not false or not.

// If not flag value.

if (!myflag)

// Display the message.

cout<<"Element not found in the list"<<endl;

}

Define a function “displayList()” to display the circular doubly linked list.

// Function definition displayList() to print the list.

void IntCircularDLList::displayList()

{

// Declare a temp node pointer.

struct IntCircularDLLNode *temp;

Use “if” condition to check whether the first node is equal to last node or not and the first node is NULL or not.

/* If the start node is last node and start node value is null, then list is empty. */

if (startPtr == lastPtr && startPtr == NULL)

{

// Display the list as empty.

cout<<"The List is empty"<<endl;

// Return the empty list.

return;

}

// Make the temp node as start.

temp = startPtr;

Execute “for” loop to iterate through the circular doubly linked list till the last element to display the circular doubly linked list.

/* For loop to iterate till the last to display the list. */

for (int i = 0;i < counter-1;i++)

{

// Print the node elements as list.

cout<<temp->element<<"<->";

// Update the node as node next.

temp = temp->nextPtr;

}

// Print the node element.

cout<<temp->element<<endl;

}

Sample Output

Output:

---------------------------

Doubly Circular linked list

---------------------------

1. Insert to Head

2. Insert to Tail

3. Delete from Head

4. Delete from Tail

5. Delete Node

6. Search Node

7. Display List

8. Is List Empty?

9. Exit

Enter your selection : 1

Enter the element to be inserted: 15

Element inserted in empty list

---------------------------

Doubly Circular linked list

---------------------------

1. Insert to Head

2. Insert to Tail

3. Delete from Head

4. Delete from Tail

5. Delete Node

6. Search Node

7. Display List

8. Is List Empty?

9. Exit

Enter your selection : 2

Enter the element to be inserted: 14

---------------------------

Doubly Circular linked list

---------------------------

1. Insert to Head

2. Insert to Tail

3. Delete from Head

4. Delete from Tail

5. Delete Node

6. Search Node

7. Display List

8. Is List Empty?

9. Exit

Enter your selection : 1

Enter the element to be inserted: 16

Element inserted

---------------------------

Doubly Circular linked list

---------------------------

1. Insert to Head

2. Insert to Tail

3. Delete from Head

4. Delete from Tail

5. Delete Node

6. Search Node

7. Display List

8. Is List Empty?

9. Exit

Enter your selection : 2

Enter the element to be inserted: 13

---------------------------

Doubly Circular linked list

---------------------------

1. Insert to Head

2. Insert to Tail

3. Delete from Head

4. Delete from Tail

5. Delete Node

6. Search Node

7. Display List

8. Is List Empty?

9. Exit

Enter your selection : 7

16<->15<->14<->13

---------------------------

Doubly Circular linked list

---------------------------

1. Insert to Head

2. Insert to Tail

3. Delete from Head

4. Delete from Tail

5. Delete Node

6. Search Node

7. Display List

8. Is List Empty?

9. Exit

Enter your selection : 3

Element Deleted

---------------------------

Doubly Circular linked list

---------------------------

1. Insert to Head

2. Insert to Tail

3. Delete from Head

4. Delete from Tail

5. Delete Node

6. Search Node

7. Display List

8. Is List Empty?

9. Exit

Enter your selection : 4

Element Deleted

---------------------------

Doubly Circular linked list

---------------------------

1. Insert to Head

2. Insert to Tail

3. Delete from Head

4. Delete from Tail

5. Delete Node

6. Search Node

7. Display List

8. Is List Empty?

9. Exit

Enter your selection : 7

15<->14

---------------------------

Doubly Circular linked list

---------------------------

1. Insert to Head

2. Insert to Tail

3. Delete from Head

4. Delete from Tail

5. Delete Node

6. Search Node

7. Display List

8. Is List Empty?

9. Exit

Enter your selection : 6

Enter the value to be searched: 15

Element 15 found at index: 1

---------------------------

Doubly Circular linked list

---------------------------

1. Insert to Head

2. Insert to Tail

3. Delete from Head

4. Delete from Tail

5. Delete Node

6. Search Node

7. Display List

8. Is List Empty?

9. Exit

Enter your selection : 5

Enter the index of the element to be removed: 1

Element Deleted

---------------------------

Doubly Circular linked list

---------------------------

1. Insert to Head

2. Insert to Tail

3. Delete from Head

4. Delete from Tail

5. Delete Node

6. Search Node

7. Display List

8. Is List Empty?

9. Exit

Enter your selection : 7

14

---------------------------

Doubly Circular linked list

---------------------------

1. Insert to Head

2. Insert to Tail

3. Delete from Head

4. Delete from Tail

5. Delete Node

6. Search Node

7. Display List

8. Is List Empty?

9. Exit

Enter your selection : 8

Circular doubly linked list: 14

---------------------------

Doubly Circular linked list

---------------------------

1. Insert to Head

2. Insert to Tail

3. Delete from Head

4. Delete from Tail

5. Delete Node

6. Search Node

7. Display List

8. Is List Empty?

9. Exit

Enter your selection : 9