Question
Take the code I have written here and change it into a doubly linked list. #include #include using namespace std; // define a node for
Take the code I have written here and change it into a doubly linked list.
#include
#include
using namespace std;
// define a node for storage and linking
class node{
public:
string name;
node *next;
// node *prev; // to be implemented by students
};
class linkedList{
public:
linkedList():top(NULL){}
bool empty(){return top == NULL;}
node *getTop(){return top;}
void setTop(node *n){top = n;}
void add(string);
int menu();
void remove(string);
~linkedList();
// void reversePrint(); // to be implemented by students
friend ostream& operator << (ostream&, const linkedList&); // default output is in-order print.
private:
node *top;
//node *end; // to be used for reverse print and implemented by students
};
void main(){
linkedList l;
cout << l.empty() << endl;
int option = 0;
string s;
bool go = true;
while(go){
option = l.menu();
switch(option){
case 1: cout << "enter a name: ";cin >> s; l.add(s); break;
case 2: cout << "enter name to be deleted: "; cin >> s; l.remove(s);break;
case 3: cout << l; break;
case 4: cout << "can not be done with a singly linked list"<< endl;
case 5: cout << "exiting" << endl; go = false; break;
}
}
// l goes out of scope and calls ~linkedList()
}
// can not call this method "delete" - "delete" is a reserved keyword.
void linkedList::remove(string s){
bool found = false;
node *curr = getTop(), *prev=NULL;
while(curr != NULL){
// match found, delete
if(curr->name == s){
found = true;
// found at top
if(prev == NULL){
node *temp = getTop();
setTop(curr->next);
delete(temp);
// found in list - not top
}else{
prev->next = curr->next;
delete(curr);
}
}
// not found, advance pointers
if(!found){
prev = curr;
curr = curr->next;
}
// found, exit loop
else curr = NULL;
}
if(found)cout << "Deleted " << s << endl;
else cout << s << " Not Found "<< endl;
}
void linkedList::add(string s){
node *n = new node();
n->name = s;
n->next = NULL;
// take care of empty list case
if(empty()){
top = n;
// take care of node belongs at beginning case
} else if(getTop()->name > s){
n->next = getTop();
setTop(n);
// take care of inorder and end insert
}else{
// insert in order case
node *curr = getTop(), *prev = curr;
while(curr != NULL){
if(curr->name > s)break;
prev = curr;
curr = curr->next;
}
if(curr != NULL){ // search found insert point
n->next = curr;
prev->next = n;
}
// take care of end of list insertion
else if(curr == NULL){// search did not find insert point
prev->next = n;
}
}
}
ostream& operator << (ostream& os, const linkedList& ll){
//linkedList x = ll; // put this in and the code blows up - why?
node *n = ll.top;
if(n == NULL)cout << "List is empty." << endl;
else
while(n != NULL){
os << n->name << endl;
n = n->next;
}
return os;
}
// return memory to heap
linkedList::~linkedList(){
cout << "~linkedList called." << endl;
node *curr = getTop(), *del;
while(curr != NULL){
del = curr;
curr = curr->next;
delete(del);
}
}
int linkedList::menu(){
int choice = 0;
while(choice < 1 || choice > 5){
cout << " Enter your choice" << endl;
cout << " 1. Add a name." << endl;
cout << " 2. Delete a name." << endl;
cout << " 3. Show list." << endl;
cout << " 4. Show reverse list. " << endl; // to be implemented by students
cout << " 5. EXIT " << endl;
cin >> choice;
}
return choice;
}
Example Output:
1
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
1
enter a name: liz
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
1
enter a name: bonnie
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
1
enter a name: al
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
1
enter a name: zeek
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
1
enter a name: willy
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
1
enter a name: wanda
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
3
al
bonnie
liz
wanda
willy
zeek
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
4
zeek
willy
wanda
liz
bonnie
al
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
2
enter name to be deleted: liz
Deleted liz
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
2
enter name to be deleted: al
Deleted al
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
2
enter name to be deleted: zeek
Deleted zeek
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
2
enter name to be deleted: zeek
zeek Not Found
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
3
bonnie
wanda
willy
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
2
enter name to be deleted: bonnie
Deleted bonnie
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
2
enter name to be deleted: willy
Deleted willy
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
2
enter name to be deleted: wanda
Deleted wanda
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
3
List is empty.
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
1
enter a name: tawnya
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
3
tawnya
Enter your choice
1. Add a name.
2. Delete a name.
3. Show list.
4. Show reverse list.
5. EXIT
5
exiting
~linkedList called.
Press any key to continue...
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started