Please make sure to compile your code before submitting it. Your answer should g
ID: 3809921 • Letter: P
Question
Please make sure to compile your code before submitting it. Your answer should give the exact same output code that the one provided below.
DO NOT submit incomplete code that does not implement the four methods correctly or DOES NOT answer the question.
In this assignment, you will implement the following four methods on an incomplete implementation of a doubly-linked list:
append(const T& value): appends a node containing a specified value to the linked list;
remove(const T& value): removes a node containing a specified value from the linked list;
copy(const List<T> &rhs): copies all values from a specified linked list to the current linked list;
makeEmpty(): deletes all nodes in the linked list.
Below are the starter files for this assignment. Do not alter the class definition or driver code in any way. Programs that crash are subject to a 50% penalty. Please submit the class implementation file only (“List.cpp”). PLEASE NOTE: You may not use any Standard Template Library (STL) classes for this assignment. Use code provided below only.
List.h:
#pragma once
#include "ListNode.h"
#include "ListIterator.h"
#include "ListIterator.cpp"
namespace cs20a
{
template<class T> class ListIterator;
template <class T>
class List
{
public:
typedef ListIterator<T> iterator;
List();
List(const List &rhs);
~List();
List<T> & operator = (const List<T> &rhs);
//*** Implement these methods only. ***
void append(const T &value);
bool remove(const T &value);
//*** *** *** *** *** *** *** *** ***
void clear();
bool contains(const T &value);
bool isEmpty() const;
int getSize() const;
iterator begin()
{ return iterator(head->next); }
iterator end()
{ return iterator(nullptr); }
private:
ListNode<T> *head;
ListNode<T> *tail;
ListNode<T> header;
int size;
void init();
//*** Implement these methods only. ***
void copy(const List<T> &rhs);
void makeEmpty();
//*** *** *** *** *** *** *** *** ***
};
}
List.cpp:
#pragma once
#include <iostream>
#include "List.h"
#include "ListNode.h"
namespace cs20a
{
template<class T>
List<T>::List()
{
init();
}
template<class T>
List<T>::List(const List &rhs)
{
init();
copy(rhs);
}
template<class T>
List<T>::~List()
{
makeEmpty();
}
template<class T>
List<T> & List<T>::operator = (const List<T> &rhs)
{
if (this == &rhs)
return *this;
makeEmpty();
init();
copy(rhs);
return *this;
}
template<class T>
void List<T>::init()
{
head = tail = &header;
header.next = nullptr;
size = 0;
}
template<class T>
bool List<T>::isEmpty() const
{
return size == 0;
}
template<class T>
void List<T>::copy(const List<T> &rhs)
{
//*** Implement this code ***
}
template<class T>
void List<T>::makeEmpty()
{
//*** Implement this code ***
}
template<class T>
void List<T>::append(const T &value)
{
//*** Implement this code ***
}
template<class T>
bool List<T>::remove(const T &value)
{
//*** Implement this code ***
}
template<class T>
void List<T>::clear()
{
makeEmpty();
init();
}
template<class T>
bool List<T>::contains(const T &value)
{
if (head->next == nullptr)
return false;
ListNode<T> *current = head->next;
while (current != nullptr)
{
if (current->value == value)
return true;
current = current->next;
}
return false;
}
template<class T>
int List<T>::getSize() const
{
return size;
}
}
ListIterator.cpp:
#pragma once
#include <iostream>
#include "ListNode.h"
#include "ListIterator.h"
namespace cs20a
{
template<class T>
ListIterator<T>::ListIterator() : m_ptr(nullptr)
{}
template<class T>
ListIterator<T>::ListIterator(ListNode<T>* ptr) : m_ptr(ptr)
{}
template<class T>
ListIterator<T> & ListIterator<T>::operator ++ () // Pre-increment
{
m_ptr = m_ptr->next;
return *this;
}
template<class T>
ListIterator<T> ListIterator<T>::operator ++ (int) // Post-increment
{
ListIterator<T> tmp(*this);
m_ptr = m_ptr->next;
return tmp;
}
template<class T>
T & ListIterator<T>::getValue() const
{
return m_ptr->value;
}
template<class T>
bool ListIterator<T>::operator == (const ListIterator<T>& li) const
{
return m_ptr==li.m_ptr;
}
template<class T>
bool ListIterator<T>::operator != (const ListIterator<T>& li) const
{
return m_ptr!=li.m_ptr;
}
template<class T>
T & ListIterator<T>::operator* () const
{
return m_ptr->value;
}
}
ListIterator.h:
#pragma once
#include "ListNode.h"
namespace cs20a
{
template <class T>
class ListIterator
{
public:
ListIterator();
ListIterator(ListNode<T>* ptr);
ListIterator<T> & operator ++ ( );
ListIterator<T> operator ++ (int);
bool operator == (const ListIterator<T>& li) const;
bool operator != (const ListIterator<T>& li) const;
T & getValue() const;
T & operator * () const;
private:
ListNode<T>* m_ptr;
};
}
ListMenu.cpp:
// Menu.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include "List.h"
#include "List.cpp"
#include "ListIterator.h"
#include "ListIterator.cpp"
using namespace std;
using namespace cs20a;
enum CHOICE { APPEND, REMOVE, CONTAINS, SIZE, MAKEEMPTY, ISEMPTY, QUIT, PRINT, OTHER };
CHOICE menu();
void printList(List<int>& l);
int main(int argc, char* argv[]) {
int value;
List<int> list;
ListIterator<int> iter;
CHOICE choice;
do {
choice = menu();
switch (choice) {
case MAKEEMPTY:
list.clear();
break;
case ISEMPTY:
if (list.isEmpty()) {
cout << "List is empty." << endl;
}
else {
cout << "List is not empty." << endl;
}
break;
case SIZE:
cout << "List has " << list.getSize() << " elements. " << endl;
break;
case REMOVE:
cout << "Please provide int to remove: ";
cin >> value;
list.remove(value);
break;
case APPEND:
cout << "Please provide int to append: ";
cin >> value;
list.append(value);
break;
case CONTAINS:
cout << "Please provide int to find: ";
cin >> value;
if (list.contains(value))
cout << "List contains " << value << "." << endl;
else
cout << "List does not contain " << value << "." << endl;
break;
case PRINT:
printList(list);
break;
case OTHER:
cout << "Not a valid choice." << endl;
}
} while (choice != QUIT);
return(0);
}
CHOICE menu() {
char choice;
CHOICE result;
cout << "(A)ppend (R)emove (C)ontains (M)akeEmpty (S)ize (I)sEmpty (P)rint (Q)uit: " << endl;
cin >> choice;
switch (choice) {
case 'M':
case 'm':
result = MAKEEMPTY;
break;
case 'I':
case 'i':
result = ISEMPTY;
break;
case 'A':
case 'a':
result = APPEND;
break;
case 'R':
case 'r':
result = REMOVE;
break;
case 'C':
case 'c':
result = CONTAINS;
break;
case 'S':
case 's':
result = SIZE;
break;
case 'P':
case 'p':
result = PRINT;
break;
case 'Q':
case 'q':
result = QUIT;
break;
default:
result = OTHER;
break;
}
return(result);
}
void printList(List<int>& l) {
if (l.isEmpty())
cout << "Empty list" << endl;
else {
for (List<int>::iterator it = l.begin(); it != l.end(); it++) {
cout << *it << " -> ";
}
cout << "NULL" << endl;
}
}
ListNode.h:
#pragma once
namespace cs20a
{
template <class T>
struct ListNode
{
ListNode() {};
ListNode(T t) : value(t), next(nullptr), previous(nullptr) {}
T value;
ListNode *next;
ListNode *previous;
};
}
SAMPLE OUTPUT:
Explanation / Answer
Here is the code for List.cpp:
#pragma once
#include <iostream>
#include "List.h"
#include "ListNode.h"
namespace cs20a
{
template<class T>
List<T>::List()
{
init();
}
template<class T>
List<T>::List(const List &rhs)
{
init();
copy(rhs);
}
template<class T>
List<T>::~List()
{
makeEmpty();
}
template<class T>
List<T> & List<T>::operator = (const List<T> &rhs)
{
if (this == &rhs)
return *this;
makeEmpty();
init();
copy(rhs);
return *this;
}
template<class T>
void List<T>::init()
{
head = tail = &header;
header.next = nullptr;
size = 0;
}
template<class T>
bool List<T>::isEmpty() const
{
return size == 0;
}
template<class T>
void List<T>::copy(const List<T> &rhs)
{
//*** Implement this code ***
}
template<class T>
void List<T>::makeEmpty()
{
//*** Implement this code ***
ListNode<T> *temp = head;
size = 0;
while(temp != nullptr)
{
ListNode<T> *next = temp->next;
delete temp;
temp = next;
}
}
template<class T>
void List<T>::append(const T &value)
{
//*** Implement this code ***
ListNode<T> *node = new ListNode<T>(value);
if(tail == nullptr)
tail = head = node;
else
{
node->previous = tail;
tail->next = node;
tail = node;
}
size++;
}
template<class T>
bool List<T>::remove(const T &value)
{
//*** Implement this code ***
ListNode<T> *temp = head;
if(head == nullptr) //If there are no nodes in the list.
return nullptr;
if(head->value == value || tail->value == value) //If the node to be removed is either the head or tail.
{
if(head == tail) //If there is only one node in the list, and is to be removed.
{
temp = head;
head = nullptr;
tail = nullptr;
size--;
return true;
}
else if(head->value == value) //If the first node is to be removed on a multi-node list.
{
temp = head;
head = head->next;
head->previous = nullptr;
size--;
return true;
}
else if(tail->value == value) //If the tail node is to be removed on a multi-node list.
{
temp = tail;
tail = tail->previous;
tail->next = nullptr;
size--;
return true;
}
}
else //If there are multiple nodes, and the node could be found in the middle of the list.
{
while(temp->next != tail)
{
if(temp->value == value)
{
temp->previous->next = temp->next;
temp->next->previous = temp->previous;
size--;
return true;
}
temp = temp->next;
}
}
return false;
}
template<class T>
void List<T>::clear()
{
makeEmpty();
init();
}
template<class T>
bool List<T>::contains(const T &value)
{
if (head->next == nullptr)
return false;
ListNode<T> *current = head->next;
while (current != nullptr)
{
if (current->value == value)
return true;
current = current->next;
}
return false;
}
template<class T>
int List<T>::getSize() const
{
return size;
}
}