Implement a singularly linked list class. Complete llist.h, llist.cpp, and client.cpp. The client/main program is a menu based program:

Case 1: 1. check empty and report the result 2. display the list L.displayAll(); 3. add 4 integers L.addRear(1); L.addRear(2); L.addRear(3); L.addRear(4) 4. display the list L.displayAll(); - 1 2 3 4 5. remove from front twice (and display the elements as they are removed) 6. display the list - 3 4 7. check empty again and report the result 8. remove from the rear twice (display the elements removed) 9. check empty again and report the result

Case 2: 1. add to front once (element 5) 2. add to front again (element 4) 3. delete Front -- this removes 4 4. add to rear 3 times (elements 6,8,9) 5. displayAll (4 elements) 5 6 8 9 6. add before the 1st (element 4) 4 5 6 8 9 7. add before the 4th (element 7) 4 5 6 7 8 9 8. add before the 7th (element 10) 4 5 6 7 8 9 10 9. add before the 9th (element 12) error (out of range) 10. add before the 0th (element 0) error (out of range) 11. displayAll 4 5 6 7 8 9 10 12. delete Ith I==1 (indicate the element removed) 5 6 7 8 9 10 13. delete Ith I==6 (indicate the element removed) - 5 6 7 8 9 14. delete Ith I==3 (indicate the element removed) - 5 6 8 9 15. delete Ith I==5 error (out of range) 16. delete Ith I==0 error (out of range) 17. displayAll - 5 6 8 9 18. delete from rear until it is empty (indicate the elements removed) 19. displayAll - [empty]

Case 3: 1. add before the 0th error (out of range) 2. delete front error (underflow) Case 4: 1. delete 2nd error (out of range) 2. delete rear error (underflow)

_________________________________________________________________________________________________________________________________________

list.h

//INSTRUCTION: //Llist class - header file template (by Yoshii) based on Notes-6A //You must complete the ** parts and then complete llist.cpp // Don't forget PURPOSE and PARAMETERS // ======================================================= // HW#: HW3P1 llist // Your name: ** // Compiler: g++ // File type: headher file //=======================================================

//----- Globally setting up the alias and struct ---------------- typedef ** el_t ; // elements will be **

//a list node is defined here as a struct Node // I could have done class Node and add the data members under public // but it would use too much space struct Node { el_t Elem; // elem is the element stored Node *Next; // next is the pointer to the next node }; //---------------------------------------------------------

class llist { private: Node *Front; // pointer to the front node Node *Rear; // pointer to the rear node int Count; // counter for the number of nodes public:

// Exception handling classes class Underflow{}; class OutOfRange{}; // thrown when the specified Node is out of range

llist (); // constructor to create a list object ~llist(); // destructor to destroy all nodes //** bool isEmpty(); //** void displayAll();

//** void addFront(el_t); //** void addRear(el_t);

//** void deleteFront(el_t&); //** void deleteRear(el_t&); //** void deleteIth(int, el_t&);

//** void addbeforeIth(int, el_t); };

_________________________________________________________________________________________________________________________________________-

list.cpp

//INSTRUCTION: //Use the provided text to help create llist.cpp //based on Yoshii CS311 Notes-6A

//- Make sure PURPOSE and PARAMETER comments are given //- Make sure all if-then-else are commented describing which case it is //- Make sure all local variables are described fully with their purposes //EMACS HINT: // control-K cuts and control-Y pastes // Esc X replace-str does string replacements // Esc > goes to the end of the file; Esc < to the beginning // Tab on each line will indent perfectly for C++

// ==================================================== //HW#: HW3P1 llist //Your name: ** //Complier: ** //File type: llist implementation file //=====================================================

using namespace std;

#include #include"llist.h"

Constructor - initialize Front and Rear to be NULL and Count = 0. - This does not create any node. The new list is empty. Destructor - while the list is not empty, call deleteFront repeatedly to delete all nodes. - Please place a cout in this function "calling the llist desctructor."

bool llist::isEmpty() - return true if Front and Rear are both pointing to NULL and Count is 0. - (all 3 conditions must be checked)

void llist::displayAll() - Special case: if the list is empty, display [ empty ] ). - Regular: displays each element of the list horizontally starting from Front in [ ]. void llist::addRear(el_t NewNum) 2 cases: - Special case: if this is going to be the very first node, you must create a new node and make Front and Rear point to it. Place NewNum and Count is updated. - Regular: adds a new node at the rear and puts NewNum in the Elem field of this new node. Count is updated. Regular case: Rear->Next = new Node; Rear = Rear->Next; Rear->Elem = NewNum; Rear->Next = NULL;

void llist::addFront(el_t NewNum) 2 cases: - Special case: if this is going to be the very first node, you must create a new node and make Front and Rear point to it. Place NewNum and Count is updated. - Regular: add a new node to the front of the list and Count is updated. Regular case: Node *x; x = new Node; x->Next = Front; Front = x; Front->Elem = NewNum;

void llist::deleteFront(el_t& OldNum) 3 cases: - Error case: if the List is empty, throw Underflow - Special case: if currently only one Node, give back the front node element through OldNum (pass by reference) and make sure both Front and Rear become NULL. Count is updated. - Regular: give back the front node element through OldNum (pass by reference) and also removes the front node. Count is updated. Regular case: OldNum = Front->Elem; Node *Second; Second = Front->Next; delete Front; Front = Second;

void llist::deleteRear(el_t& OldNum) 3 cases: - Error case: if empty, throw Underflow - Special case: if currently only one node, give back the rear node element through OldNum (pass by reference) and make sure both Front and Rear become NULL. Count is updated. - Regular: give back the rear node element through OldNum (pass by reference) and also remove the rear node. Count is updated. Regular case: OldNum = Rear->Elem; Node *p; Make p go to the one right before rear (using while) delete Rear; Rear = p;

void llist::deleteIth(int I, el_t& OldNum) 4 cases: - Error case: If I is an illegal value (i.e. > Count or < 1) throw OutOfRange. - Special cases: this should simply call deleteFront when I is 1 or deleteRear when I is Count - Regular: delete the Ith node (I starts out at 1). Count is updated.

void llist::addbeforeIth(int I, el_t newNum) 4 cases: - Error case: If I is an illegal value (i.e. > Count+1 or < 1) throw OutOfRange. - Special cases: this should simply call addFront when I is 1 or addRear when I is Count+1 - Regular: add right before the Ith node. Cout if updated.

___________________________________________________________________________________________________________________________________________

client.cpp

//INSTRUCTION //Look for ** to complete all of them //The output should match my assingment sheet

//========================================================= //HW#: HW3P1 llist //Your name: ** //Complier: ** //File type: client program (tester) //===========================================================

using namespace std;

#include #include "llist.h"

void caseOne() { cout << "CASE 1:------------------- " << endl; llist L; // this is my list int x; // to hold a removed element

//1 check empty and report the result cout << 1 << endl; ** //2 display the list cout << 2 << endl; ** //3 add 4 integers 1,2,3,4 cout << 3 << endl; ** //4 display the list cout << 4 << endl; ** //5 remove from front twice (and display the elements removed) cout << 5 << endl; ** //6 display the list cout << 6 << endl; ** //7 check empty and report the result cout << 7 << endl; ** //8 remove from the rear twice (display the element removed) cout << 8 << endl; ** //9 check empty again and report the result cout << 9 << endl; ** }//end of case 1 void caseTwo() { cout << "Case 2: -----------------------" << endl; llist L2; // another list int x; // to hold the removed element int c = 1; // displayed step number

// 1.add to front once (element 5) cout << c << endl; c++; ** // 2.add to front again (element 4) cout << c << endl; c++; ** // 3.delete Front cout << c << endl; c++; ** // 4.add to rear 3 times (elements 6,8,9) cout << c << endl; c++; ** // 5. display all cout << c << endl; c++; ** // 6.add before the 1st (element 4) . 4 5 6 8 9 cout << c << endl; c++; ** // 7.add before the 4th (element 7) . 4 5 6 7 8 9 cout << c << endl; c++; ** // 8.add before the 7th (element 10) . 4 5 6 7 8 9 10 cout << c << endl; c++; ** // 9.add before the 9th (element 12) . error (out of range) cout << c << endl; c++; try{** } catch(**){**} // 10.add before the 0th (element 0) . error (out of range) cout << c << endl; c++; try{** } catch(**){**} // 11.displayAll cout << c << endl; c++; ** // 12.delete Ith I==1 (indicate the element removed) . 5 6 7 8 9 10 cout << c << endl; c++; ** // 13.delete Ith I==6 (indicate the element removed) - 5 6 7 8 9 cout << c << endl; c++; ** // 14.delete Ith I==3 (indicate the element removed) - 5 6 8 9 cout << c << endl; c++; ** // 15.delete Ith I==5 . error (out of range) cout << c << endl; c++; try {** } catch(**){** } // 16.delete Ith I==0 . error (out of range) cout << c << endl; c++; try {**} catch(**){**} // 17.displayAll cout << c << endl; c++; ** // 18.delete from rear until it is empty (indicate the elements removed) cout << c << endl; c++; ** // 19.displayAll cout << c << endl; c++; **

}//end of case 2

void caseThree() { cout << "Case 3:-------------------- " << endl; llist L3; int x; // to hold the removed element

// 1.add before the 0th . error (out of range) cout << 1 << endl;; try {**} catch (**){**} //2.delete front . error (underflow) cout 2 << endl; try {**} catch (**){**} } //end of case 3

void caseFour() { cout << "Case 4:------------------------ " << endl; llist L4; int x; // to hold the removed element

// 1.delete 2nd . error (out of range) cout << 1 << endl; try {** } catch (**){**} // 2.delete rear . error (underflow) cout << 2 << endl; try {** } catch (**){**} } // end of case 4

//PURPOSE of the Program: ** //Algorithm/Design: 4 test cases are divided into 3 functions and ** int main() { int selection; // this will indicate what the user wants to do do { cout << endl << "MENU: These are your options: " << endl << endl; cout << " (1) Case 1 " << endl; cout << " (2) Case 2 " << endl; cout << " (3) Case 3 " << endl; cout << " (4) Case 4 " << endl; cout << " Enter ( 0 ) to quit " << endl; cout << "===>"; cin >> selection; switch(selection) { case 1: caseOne(); break; case 2: caseTwo(); break; case 3: caseThree(); break; case 4: caseFour(); break; } } while(selection !=0);

}// end of main