Requirements: The LinkedList class given below is to be used to implement a stack. Meaning, items are to be added and removed from the head only. Complete the implementation of the given LinkedList stack class by following the steps below. After completing each step, test that your LinkedList class works and behaves like a stack by uncomenting the appropriate code in main.cpp and checking the output. Each step is worth 1 mark each. Step 1 Implement all the public member functions of the LinkedList class declared below in files list.h and list.cpp. Test your code by uncomenting the Step-1 code in main.cpp. struct Node { int Item; Node *Next; }; class LinkedList { public: LinkedList(); ~ LinkedList(); void AddHead(int Item); // adds item to head of linked list int RemoveHead(); // removes item from head of list bool IsEmpty(); // returns true if list is empty void Print(); // prints list. eg 12 34 21 26 private: Node *Head; }; Step 2 Implement a copy constructor that makes a deep copy of the LinkedList argument. Uncomment the code in main() to test that the copy constructor works on both on empty and non-empty lists. Make sure the contents of the lists (stacks) are printed as expected and there are no memory leaks. Step 3 Implement an assignment operator in your LinkedList class. The assignment operator should ensure that multiple assignments are possible. E.g.: A = B = C; // assign (copy) stack C to A and B Test the assignment operator by uncomenting the Step-3 code in main.cpp.

/********************************************************************* * list.cpp - Implementation of LinkedList class. *********************************************************************/

#include #include "list.h" using namespace std;

// Default constructor LinkedList::LinkedList() { // set Head to NULL }

// Destructor LinkedList::~LinkedList() { /* while head is not null set temp ptr to head set head to head->next delete head */ }

// Adds item to head of list void LinkedList::AddHead(int Item) { /* Create a new node put the item in it set Next to Head */ }

// Removes head node and returns item int LinkedList::RemoveHead() { /* if list is empty print error and exit set Item to Head item set temp ptr to head set head to head-> next delete temp */ return 0; //remove this line, for compilation only }

// Returns true if list is empty bool LinkedList::IsEmpty() { /* return Head==NULL */ return true; //remove this line, for compilation only }

// Prints contents of linked list void LinkedList::Print() { /* if list is empty print "empty " and return set crnt ptr to head while crnt is not null print crnt->Item print endl */ }

/********************************************************************* * main.cpp - main() driver for testing LinkedList class. *********************************************************************/

#include #include "list.h" using namespace std;

int main() { cout << "===== Testing Step-1 ===== "; cout << "Testing default construstor... " LinkedList L1; L1.Print(); // should be empty cout<<" Testing AddHead()... " for(int i=0; i<10; i++){ cout << i << ' '; L1.AddHead(i); } cout << endl; L1.Print(); cout << " Testing IsEmpty() and RemoveHead()..." while(!L1.IsEmpty()) cout << L1.RemoveHead()<< ' '; // should be printed in reverse cout << endl; L1.Print(); // should be empty

/* cout<<" ===== Testing Step-2 ===== "; for(int i=0; i<10; i++) L1.AddHead(i); cout << " Testing copy constructor... " LinkedList L2(L1); L1.Print(); L2.Print(); cout << endl;

cout << " ===== Testing Step-3 ===== "; cout << "Testing assignment operator... " LinkedList L3; for(int i=10; i<20; i++){ cout << i << ' '; L3.AddHead(i); } cout << endl; L1 = L2 = L3; L1.Print(); L2.Print(); L3.Print(); cout << endl; */ cout << " ===== End of Tests ===== ";

return 0; }

/********************************************************************* * list.h - Declaration of LinkedList class *********************************************************************/

#ifndef LIST_H #define LIST_H

struct Node;

typedef Node *NodePtr;

struct Node { int Item; NodePtr Next; };

class LinkedList { public: LinkedList(); // default constructor ~LinkedList(); // destructor void AddHead(int); // adds item to head int RemoveHead(); // removes item from head bool IsEmpty(); // returns true if list is empty void Print(); // prints list

private: NodePtr Head; };

#endif