Circular Doubly Linked List

 

Write a Program Example to implement:

 

1. Add a node at the beginning

2. Add a node at the end

3. Remove a node from beginning

4. Remove a node at the end

5. Remove a node at the middle

 

in circular doubly linked list

Write a Program Example to implement:

1. Add a node at the beginning

2. Add a node at the end

3. Remove a node from beginning

4. Remove a node at the end

5. Remove a node at the middle

Step-by-step explanation

HERE YOUR ANSWER:

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

#include <iostream>
#include <string>
#include <iomanip>
using namespace std;

class Node
{
friend class LinkedList;
public:
Node(string&, int);
private:
string itemName;
int itemNo;
Node *next;
};

Node::Node(string &name, int no) : itemName(name), itemNo(no), next(NULL)
{}

class LinkedList
{
public:
LinkedList();
~LinkedList();
int size() const;
void addToStart(Node *);
void addToEnd(Node *);
void printList();
bool removeFromStart();
bool removeFromEnd();
void removeNodeFromList(int);
void removeNodeFromList(string);

private:
Node *myHead;
Node *myTail;
int mySize;
};

LinkedList::LinkedList()
{
myHead = NULL;
myTail = NULL;
mySize = 0;
}

LinkedList::~LinkedList()
{
while(myHead != NULL)
{
Node *temp = myHead;
myHead = myHead->next;
delete(temp);
}

myTail = NULL;
}

int LinkedList:: size() const
{
return mySize;
}

void LinkedList:: addToStart(Node *node)
{
node->next = myHead;
myHead = node;
if(myTail == NULL)
myTail = node;
mySize++;
}

void LinkedList:: addToEnd(Node *node)
{
if(myTail == NULL)
myHead = node;
else
myTail->next = node;
myTail = node;
mySize++;
}

void LinkedList::printList()
{
cout<<"List : "<<endl;
if(myHead == NULL)
cout<<"Empty List"<<endl;
else
{
Node *curr = myHead;
cout<<left<<setw(10)<<"Item No"<<left<<"Item Name"<<endl;
while(curr != NULL)
{
cout<<left<<setw(10)<<curr->itemNo<<left<<curr->itemName<<endl;
curr = curr->next;
}
}
}

bool LinkedList:: removeFromStart()
{
if(myHead != NULL)
{
Node *temp = myHead;
myHead = myHead->next;
if(myHead == NULL)
myTail = NULL;
delete(temp);
mySize--;
return true;
}

return false;
}

bool LinkedList:: removeFromEnd()
{

if(myHead != NULL)
{
if(myHead->next == NULL)
{
Node *temp = myHead;
myHead = NULL;
myTail = NULL;
delete(temp);
mySize--;
return true;
}

Node *curr= myHead;
while(curr->next != myTail)
curr = curr->next;

curr->next = NULL;
delete(myTail);
myTail = curr;

mySize--;
return true;
}

return false;
}

void LinkedList:: removeNodeFromList(int no)
{
if(myHead != NULL)
{
Node *curr = myHead;
Node *prev = NULL;

while(curr != NULL)
{
if(curr->itemNo == no)
{
if(prev == NULL)
myHead = curr->next;
else
prev->next = curr->next;

if(myHead == NULL)
myTail = NULL;
else if(curr == myTail)
myTail = prev;

mySize--;
return;
}

prev = curr;
curr = curr->next;
}
cout<<"Item not found"<<endl;
}else
cout<<"Item not found"<<endl;
}

void LinkedList:: removeNodeFromList(string name)
{
if(myHead != NULL)
{
Node *curr = myHead;
Node *prev = NULL;

while(curr != NULL)
{
if(curr->itemName == name)
{
if(prev == NULL)
myHead = curr->next;
else
prev->next = curr->next;

if(myHead == NULL)
myTail = NULL;
else if(curr == myTail)
myTail = prev;

mySize--;
return;
}

prev = curr;
curr = curr->next;
}

cout<<"Item not found"<<endl;
}else
cout<<"Item not found"<<endl;
}

int main() {

int choice;
LinkedList list;
int itemNo;
string itemName;
cout<<"Welcome to the shopping list program"<<endl;
// loop that continues till the user exits
do
{
cout<<"Please choose an option:"<<endl;
cout<<"1. Add a new node at the beginning"<<endl;
cout<<"2. Add a new node at the end"<<endl;
cout<<"3. Remove the beginning node"<<endl;
cout<<"4. Remove the end node"<<endl;
cout<<"5. Remove a node from the list by entering an item number"<<endl;
cout<<"6. Remove a node from the list by entering an item name"<<endl;
cout<<"7. Print out the list"<<endl;
cout<<"8. Quit the program"<<endl;
cin>>choice;

if(choice == 1)
{
cout<<"Please enter the product number to insert at beginning: ";
cin>>itemNo;
cout<<"Please enter the name of the product : ";
cin>>itemName;
list.addToStart(new Node(itemName,itemNo));
list.printList();
}
else if(choice == 2)
{
cout<<"Please enter the product number to insert at end: ";
cin>>itemNo;
cout<<"Please enter the name of the product : ";
cin>>itemName;
list.addToEnd(new Node(itemName,itemNo));
list.printList();
}
else if(choice == 3)
{
if(!list.removeFromStart())
cout<<"List is empty"<<endl;
list.printList();
}
else if(choice == 4)
{
if(!list.removeFromEnd())
cout<<"List is empty"<<endl;
list.printList();
}
else if(choice == 5)
{
cout<<"Please enter the product number to remove: ";
cin>>itemNo;
list.removeNodeFromList(itemNo);
list.printList();
}
else if(choice == 6)
{
cout<<"Please enter the name of the product : ";
cin>>itemName;
list.removeNodeFromList(itemName);
list.printList();
}
else if(choice == 7)
{
list.printList();
}
else if(choice != 8)
{
cout<<"Invalid choice"<<endl;
}

}while(choice != 8);

return 0;
}

OUTPUT:

Welcome to the shopping list program Please choose an option: Add a new node at the beginning 2 . Add a new node at the end 3. Remove the beginning node Remove the end node Remove a node from the list by entering an item number 6. Remove a node from the list by entering an item name Print out the list B. Quit the program Please enter the product number to insert at beginning: 1 Please enter the name of the product : PIZZA List : Item No Item Name PIZZA Please choose an option: Add a new node at the beginning Add a new node at the end 3. Remove the beginning node Remove the end node Remove a node from the list by entering an item number 6. Remove a node from the list by entering an item name Print out the list B. Quit the program 2 Please enter the product number to insert at end: 2 Please enter the name of the product : JUICE List : Item No Item Name PIZZA JUICE