ListNode.h

#pragma once

#include

using std::cin; using std::cout; using std::endl;

// This class defines a node, which will always be allocated on the heap class ListNode { public: ListNode(int newData = 0); // constructor - "constructs" a ListNode; initializes the object ListNode(const ListNode ©); // copy constructor - implicitly invoked copying a ListNode object during construction of // another ListNode object, or when a ListNode object is passed-by-value; // the compiler generated one would be ok here as well! shallow copy performed!

~ListNode(); // destructor - implicitly invoked when a ListNode object leaves scope; // the compiler generated one would be ok here as well!

// we will not define an explicit overloaded assignment operator (=). We will // rely on the memberwise assignment generated by the compiler.

// getters int getData() const; // used to retrieve a copy of the data in the node ListNode * getNextPtr() const; // used to retrieve a copy of the node's next pointer

// setters void setData(const int newData); // used to modify the data in the node void setNextPtr(ListNode * const pNewNext); // used to modify the node's next pointer

private: int mData; // represents a score ListNode *mpNext; // should be set to NULL in the constructor };

ListNode.cpp

#include "ListNode.h"

// constructor - "constructs" a ListNode; initializes the object ListNode::ListNode(int newData) { mData = newData; mpNext = nullptr; }

// copy constructor - implicitly invoked copying a ListNode object during construction of // another ListNode object, or when a ListNode object is passed-by-value ListNode::ListNode(const ListNode ©) { // shallow copy performed! mData = copy.mData; mpNext = copy.mpNext; }

// destructor - implicitly invoked when a ListNode object leaves scope ListNode::~ListNode() { // Yes, these nodes are dynamically allocated, but delete will be invoked invoked by functions in List. // Hence, don't need to deallocate the heap memory inside of this destructor! cout << "Inside ListNode's destructor!" << endl; }

int ListNode::getData() const // the const indicates "constant" function; can't modify the object's data members with this function { return mData; }

ListNode * ListNode::getNextPtr() const // the const indicates "constant" function; can't modify the object's data members with this function { return mpNext; }

void ListNode::setData(const int newData) // the const in this context ensures newData can't be modified { mData = newData; }

// the const in this context ensures pNewNext can't be modified; // remember read as pNewNext is a constant pointer to a ListNode - the ListNode object is not const though! void ListNode::setNextPtr(ListNode * const pNewNext) { mpNext = pNewNext; }

List.h

#pragma once

#include

#include "ListNode.h"

using std::cin; using std::cout; using std::endl;

// This class defines a container for a list; it's a singly linked list class List { public: List(); // default constructor; will always set mpHead to NULL List(const List ©List); // copy constructor - implicitly invoked copying a List object during construction of // another List object, or when a List object is passed-by-value - must perform a deep copy, // which means create new memory for each node copied! ~List(); // destructor - implicitly invoked when a List object leaves scope

List & operator= (const List &rhs); // overloaded assignment operator - must perform a deep copy, which means // create new memory (from the heap) for each node copied!

// getter ListNode * getHeadPtr() const; // returns a copy of the address stored in mpHead

// setter void setHeadPtr(ListNode * const pNewHead); // modifies mpHead

bool insertAtFront(const int newData); // inserts newData at the beginning or front of the list bool insertInOrder(const int newData); // inserts newData in ascending (smallest to largest) order bool insertAtEnd(const int newData); // inserts newData at the end of the list

bool isEmpty(); // determines if the list is empty

int deleteAtFront(); // deletes the node at the front of the list bool deleteNode(const int searchValue); // deletes the node with data == searchValue int deleteAtEnd(); // deletes the node at the end of the list

void printList(); // visits each node, print the node's data - we could also overload the stream insertion << operator to print the list

private: ListNode *mpHead; // pointer to the start or head of the singly linked list

// yes, we can make member functions private as well ListNode * makeNode(const int newData); // will only call within insert functions void destroyList(); // deletes each node to free memory; will call in the destructor void destroyListHelper(ListNode * const pMem); // we will use recursion to solve this problem! };

List.cpp

#include "List.h"

// default constructor; will always set mpHead to NULL or nullptr List::List() { mpHead = nullptr; }

// copy constructor - implicitly invoked copying a List object during construction of // another List object, or when a List object is passed-by-value - must perform a deep copy, // which means create new memory for each node copied! List::List(const List ©List) { // fill in your code here! }

List::~List() // destructor - implicitly invoked when a List object leaves scope { cout << "Inside List's destructor! Freeing each ListNode in the List!" << endl; destroyList(); }

// this function must allocate new memory for each of the nodes in rhs to construct "this" object List & List::operator= (const List &rhs) // overloaded assignment operator - must perform a deep copy { // you must use a loop, which visits each of the nodes in List rhs, and assign the data to the new nodes // How to use new operator? ListNode *pMem = new ListNode; new is similar to the results of using malloc ()

// fill in your code here!

return (*this); }

// getter ListNode * List::getHeadPtr() const // returns a copy of the address stored in mpHead { return mpHead; }

// setter void List::setHeadPtr(ListNode * const pNewHead) // modifies mpHead { mpHead = pNewHead; }

// This function creates a new ListNode on the heap, and uses the ListNode constructor to initialize the node! bool List::insertAtFront(const int newData) // inserts newData at the beginning or front of the list { ListNode *pMem = makeNode(newData); bool success = false; // C++ has built in bool types - false, true

if (pMem != nullptr) { success = true; // allocated memory successfully // pMem is pointing to a ListNode object, but a List object does not have direct access to it; must use a setter! pMem->setNextPtr(mpHead); mpHead = pMem; }

return success; }

// insert newData in ascending order bool List::insertInOrder(const int newData) { bool success = false;

// fill in your code here!

return success; }

// inserts newData at the end of the list bool List::insertAtEnd(const int newData) { bool success = false;

// fill in your code here!

return success; }

// determines if the list is empty; // returns true if the list is empty; false otherwise bool List::isEmpty() { return (mpHead == nullptr); }

// deletes the node at the front of the list and returns a copy of the data // precondition: list must not be empty int List::deleteAtFront() { int data = 0;

// fill in your code here! use the delete operator!

return data; }

// deletes the node with data == searchValue; // returns true if the value was found; false otherwise // precondition: list must not be empty bool List::deleteNode(const int searchValue) { bool success = false;

// fill in your code here! use the delete operator!

return success; }

// deletes the node at the end of the list and returns a copy of the data // precondition: list must not be empty int List::deleteAtEnd() { int data = 0;

// fill in your code here! use the delete operator!

return data; }

// visits each node, print the node's data void List::printList() { ListNode *pCur = mpHead;

while (pCur != nullptr) { cout << pCur->getData() << endl; pCur = pCur->getNextPtr(); } }

//////////// private member functions! //////////////

// allocates memory for a Listnode; initializes the memory with newData ListNode * List::makeNode(const int newData) // will only call within insert functions { ListNode *pMem = new ListNode(newData); // ListNode constructor is invoked!

return pMem; }

// we created this function so that we could use recursion to delete the nodes! void List::destroyListHelper(ListNode * const pMem) { if (pMem != nullptr) { destroyListHelper(pMem->getNextPtr()); delete pMem; // delete from the back of list to the front! } }

// deletes each node to free memory; will call in the destructor void List::destroyList() { destroyListHelper(mpHead); }

1)

Review the ListNode.h, ListNode.cpp, List.h, and List.cpp files. Start to fill in the code for the functions listed below. Note: the ListNode class declaration (ListNode.h) and ListNode function implementations (ListNode.cpp) have been completed for you!

Write the implementation for the deep copy constructor the List class (found in List.cpp). After you finish writing your copy constructor, uncomment line 25 (List l2 = l1;) in main (). Answer questions 7 and 8.

Write the implementation for the deep copy assignment operator (found in List.cpp). After you finish writing your overloaded assignment operator, uncomment line 37 (l3 = l2;) in main (). Answer questions 9 and 10.

Write the implementation for insertInorder () (found in List.cpp). Test your function by calling it in main () or within a test function.

Write the implementation for insertAtEnd () (found in List.cpp). Test your function by calling it in main () or within a test function.

Write the implementation for deleteAtFront () (found in List.cpp). Test your function by calling it in main () or within a test function.

Write the implementation for deleteNode () (found in List.cpp). Test your function by calling it in main () or within a test function.

Write the implementation for deleteAtEnd () (found in List.cpp). Test your function by calling it in main () or within a test function.

Answer question 11 in main ().