//INSTRUCTION

//Look for ** to complete all of them

//----- 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);

};

// end of llist.h

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

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

and make sure you indicate the purposes of these local pointers>

void llist::addbeforeIth(int I, el_t newNum)

4 cases:

- Error case:

If I is an illegal value (i.e. > Count+1 or

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

and make sure you indicate the purposes of these local pointers>

// end of llist.cpp

using namespace std;

#include

#include "llist.h"

void caseOne()

{

cout

llist L; // this is my list

int x; // to hold a removed element

//1 check empty and report the result

cout

**

//2 display the list

cout

**

//3 add 4 integers 1,2,3,4

cout

**

//4 display the list

cout

**

//5 remove from front twice (and display the elements removed)

cout

**

//6 display the list

cout

**

//7 check empty and report the result

cout

**

//8 remove from the rear twice (display the element removed)

cout

**

//9 check empty again and report the result

cout

**

}//end of case 1

void caseTwo()

{

cout

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

**

// 2.add to front again (element 4)

cout

**

// 3.delete Front

cout

**

// 4.add to rear 3 times (elements 6,8,9)

cout

**

// 5. display all

cout

**

// 6.add before the 1st (element 4) . 4 5 6 8 9

cout

**

// 7.add before the 4th (element 7) . 4 5 6 7 8 9

cout

**

// 8.add before the 7th (element 10) . 4 5 6 7 8 9 10

cout

**

// 9.add before the 9th (element 12) . error (out of range)

cout

try{** }

catch(**){**}

// 10.add before the 0th (element 0) . error (out of range)

cout

try{** }

catch(**){**}

// 11.displayAll

cout

**

// 12.delete Ith I==1 (indicate the element removed) . 5 6 7 8 9 10

cout

**

// 13.delete Ith I==6 (indicate the element removed) - 5 6 7 8 9

cout

**

// 14.delete Ith I==3 (indicate the element removed) - 5 6 8 9

cout

**

// 15.delete Ith I==5 . error (out of range)

cout

try {** }

catch(**){** }

// 16.delete Ith I==0 . error (out of range)

cout

try {**}

catch(**){**}

// 17.displayAll

cout

**

// 18.delete from rear until it is empty (indicate the elements removed)

cout

**

// 19.displayAll

cout

**

}//end of case 2

void caseThree()

{

cout

llist L3;

int x; // to hold the removed element

// 1.add before the 0th . error (out of range)

cout

try {**}

catch (**){**}

//2.delete front . error (underflow)

cout 2

try {**}

catch (**){**}

} //end of case 3

void caseFour()

{

cout

llist L4;

int x; // to hold the removed element

// 1.delete 2nd . error (out of range)

cout

try {** }

catch (**){**}

// 2.delete rear . error (underflow)

cout

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

cout

cout

cout

cout

cout

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

1. [30 points] implement a singularly linked list class. Complete llisth, Ilist.cpp, and client.cpp. The client/main ram is a menu based Case 1: 1. check empty and report the result 2. display the list L.displayAllO). 3. add 4 integers L-addRear(1) LaddRear(2). LaddRear(3). LaddReart4) 4. display the list L display All0: -1234 5. remove from front twice (and display the elements as they are removed) 6. display the list 34 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) 5689 -45689 6. add before the 1st (element 4) 7. add before the 4th (element 7) -456789 8. add before the 7th (element 10) 4567 89 10 error (out of range 9. add before the 9th (element 12) 10. add before the 0th (element 0) error (out of range 11. display All 4567 89 10 12. delete ith l 1 (indicate the element removed) 56789 10 13. delete lth l -6 (indicate the element removed) 56789 14. delete lth l FE3 (indicate the element removed) 5689 error (out of range 5. delete lth l >5 16. delete lith l >0 error (out of range 17. display AII 5689 18. delete from rear until it is empty (indicate the elements removed) 19. displayAll