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...