Exercise 3: Implementing a Bag Class With a Linked List Create a class Bag that uses a linked list to store the bag items. The item type must be char. The class should have the methods listed below. Create a main() that will store in a bag object a fixed number of characters entered by the program user. After the input is completed, the program should modify the bag content so that it does not contain any duplicate characters, if duplicates were entered. For example, if the user entered 'M' 'I' 'S' 'S' 'I' 'S' 'S' 'I' 'P' 'P' 'I', the characters remaining in the bag after the removal of duplicates would be 'M' 'I' 'S' 'P'. Bag(): default constructor ~Bag(): class destructor bool isEmpty(): determines whether the bag is empty void print(): prints the bag elements int getSize(): returns the number of items in the bag void clear(): removes all of the items from the bag void add(char item): adds an item to the bag void remove(char item): removes an item from the bag; only one occurrence of the item should be removed. int count(char item): counts the number of occurrences of an item in the bag.

You can use the following code for the linked list:

main.cpp

/*******************************

* Week 2 lesson: *

* a simple LinkedList class *

*******************************/

#include

#include "LinkedList.h"

using namespace std;

int main()

{

LinkedList myList;

int x;

//Add 5 random numbers to list

for (int i=0; i < 5; i++)

myList.add(rand()%20);

cout << "1 - Display the list elements" << endl;

cout << "2 - Is it empty?" << endl;

cout << "3 - Add element" << endl;

cout << "4 - Delete element" << endl;

cout << "5 - Exit" << endl;

int option;

//Loop to test the LinkedList class methods

do

{

cout << endl << "Enter your choice: ";

cin >> option;

switch(option)

{

case 1:

cout << "List elements: ";

myList.display();

break;

case 2:

if (myList.isEmpty()) cout << "List is empty"<< endl;

else cout << "List is not empty" << endl;

break;

case 3:

cout << "Enter an element to add at the beginning of the list: ";

cin >> x;

myList.add(x);

break;

case 4:

cout << "Enter an element to delete from the list: ";

cin >> x;

myList.remove(x);

break;

case 5:

cout << "All done!" << endl;

break;

default: cout << "Invalid choice!" << endl;

}

} while (option != 5);

return 0;

}

LinkedList.h

/*******************************

* Week 2 lesson: *

* a simple LinkedList class *

*******************************/

/*

* Linked list node.

*/

struct Node

{

int info; //element stored in this node

Node *next; //link to next node

};

/*

* Class implementing a linked list.

*/

class LinkedList

{

public:

LinkedList();

~LinkedList();

bool isEmpty();

void display();

void add(int);

void remove(int);

private:

Node *first; //pointer to header (dummy) node

};

LinkedList.cpp

/*******************************

* Week 2 lesson: *

* a simple LinkedList class *

*******************************/

#include

#include "LinkedList.h"

using namespace std;

/*

* Initializes the list to empty creating a dummy header node.

*/

LinkedList::LinkedList()

{

first = new Node;

first->next = NULL;

}

/*

* Destructor. Deallocates all the nodes of the linked list,

* including the header node.

*/

LinkedList::~LinkedList()

{

Node *temp;

while (first != NULL)

{

temp=first;

first=first->next;

delete temp;

}

}

/*

* Determines whether the list is empty.

*

* Returns true if the list is empty, false otherwise.

*/

bool LinkedList::isEmpty()

{

return first->next == NULL;

}

/*

* Prints the list elements.

*/

void LinkedList::display()

{

Node * current = first->next;

while(current != NULL)

{

cout << current->info << " ";

current = current->next;

}

cout << endl;

}

/*

* Adds the element x to the beginning of the list.

*

* x: element to be added to the list.

*/

void LinkedList::add(int x)

{

Node *p = new Node;

p->info = x;

p->next = first->next;

first->next = p;

}

/*

* Removes the first occurrence of x from the list. If x is not found,

* the list remains unchanged.

*

* x: element to be removed from the list.

*/

void LinkedList::remove(int x)

{

Node * old = first->next,

* p = first;

//Finding the address of the node before the one to be deleted

bool found = false;

while (old != NULL && !found)

{

if (old->info == x) found = true;

else

{

p = old;

old = p->next;

}

}

//if x is in the list, remove it.

if (found)

{

p->next = old->next;

delete old;

}

}