Requirements: The LinkedList class given below is to be used to implement a stac

Question

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 <iostream>
#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 <iostream>
#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

Explanation / Answer

Given below is the modified files as per the question.
Please do rate the answer if it was helpful. Thank you

list.h
-------
/*********************************************************************

* 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(const LinkedList &other); //copy constructor
LinkedList & operator = (const LinkedList &other); //assignment operator
~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

list.cpp
---------
/*********************************************************************

* list.cpp - Implementation of LinkedList class.


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

#include <iostream>
#include <cstdlib>
#include "list.h"
using namespace std;

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

//copy constructor
LinkedList::LinkedList(const LinkedList &other)
{
Head = NULL;
*this = other;
}

//assignment operator
LinkedList & LinkedList:: operator = (const LinkedList &other)
{
if(this != &other) //avoid self assignment
{
//deallocate existing memory
NodePtr temp;

while(Head != NULL)
{
temp = Head->Next;
delete Head;
Head = temp;
}
}

if(other.Head != NULL)
{

Head = new Node;

NodePtr n1 = Head;
NodePtr n2 = other.Head;

n1->Item = n2->Item;

n2 = n2->Next;
while(n2 != NULL)
{
n1->Next = new Node;
n1 = n1->Next;
n1->Item = n2->Item;
n2 = n2->Next;
}

n1->Next = NULL;

}
return *this;
}

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

while(Head != NULL)
{
temp = Head->Next;
delete Head;
Head = temp;
}
}

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

NodePtr n = new Node;
n->Item = Item;
n->Next = Head;
Head = n;
}

// 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
*/

if(IsEmpty())
{
cout << "Stack is empty. Can't Remove!" << endl;
exit(1);
}

int Item = Head->Item;
NodePtr temp = Head;
Head = Head->Next;
delete temp;
return Item;
}

// Returns true if list is empty
bool LinkedList::IsEmpty()
{
/*
return Head==NULL
*/
return Head == NULL;
}

// 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
*/

if(IsEmpty())
{
cout << "empty" << endl;
return;
}

NodePtr crnt = Head;
while(crnt != NULL)
{
cout << crnt->Item << " ";
crnt = crnt->Next;
}

cout << endl;
}

main.cpp
--------
/*********************************************************************

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

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

#include <iostream>
#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;
}

output
======
===== Testing Step-1 =====
Testing default construstor...
empty

Testing AddHead()...
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

Testing IsEmpty() and RemoveHead()...9 8 7 6 5 4 3 2 1 0
empty

===== End of Tests =====
amoeba-2:linkedstack raji$ g++ list.cpp main.cpp
amoeba-2:linkedstack raji$ ./a.out
===== Testing Step-1 =====
Testing default construstor...
empty

Testing AddHead()...
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

Testing IsEmpty() and RemoveHead()...9 8 7 6 5 4 3 2 1 0
empty

===== Testing Step-2 =====

Testing copy constructor...
9 8 7 6 5 4 3 2 1 0
9 8 7 6 5 4 3 2 1 0

===== Testing Step-3 =====
Testing assignment operator...
10 11 12 13 14 15 16 17 18 19
19 18 17 16 15 14 13 12 11 10
19 18 17 16 15 14 13 12 11 10
19 18 17 16 15 14 13 12 11 10

===== End of Tests =====

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.