Take the code I have written here and change it into a doubly linked list. You cannot write the doubly linked list without understanding the singly linked list presented. There are tons of good tutorials on singly and doubly linked lists online.

$/*$

Written by Professor Kenneth L Moore

For CIT$245$ Data Structures and Programming C$++$

This code implements a singly linked list

Students must change it to 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.