Modify the LinkedList and Node classes to make a doubly linked list which performs all of the standard list ADT operations. That is, in addition to having a pointer to the next node, each node also has a pointer to the previous node. Make modifications in the below data structures/functions to maintain the integrity of the list state, i.e. after an ADT List operation completes, all next pointers and previous pointers are updated and correct. You will also need to create some new functions in the Node class to set/get the previous pointer. At a minimum, the following will need to be modified:

- LinkedList.cpp: heres the heavy lifting:

- the constructor needs to initialize tailPtr to nullptr

- insert(): modify it to update prev pointers as well as next pointers. Suggestion: handle the special cases first (inserting to empty list, inserting to start of list, inserting to end of list), then handle the generic case (adding to somewhere else in list).

- remove(): modify to update prev pointers as well as next pointers.

/** Implementation file for the class LinkedList. @file LinkedList.cpp */

#include "LinkedList.h" // Header file #include #include #include

template LinkedList::LinkedList() : headPtr(nullptr), itemCount(0) { headPtr = nullptr; itemCount = 0; } // end default constructor

template LinkedList::LinkedList(const LinkedList& aList) : itemCount(aList.itemCount) { Node* origChainPtr = aList.headPtr; // Points to nodes in original chain

if (origChainPtr == nullptr) headPtr = nullptr; // Original list is empty else { // Copy first node headPtr = new Node(); headPtr->setItem(origChainPtr->getItem()); // Copy remaining nodes Node* newChainPtr = headPtr; // Points to last node in new chain origChainPtr = origChainPtr->getNext(); // Advance original-chain pointer while (origChainPtr != nullptr) { // Get next item from original chain ItemType nextItem = origChainPtr->getItem(); // Create a new node containing the next item Node* newNodePtr = new Node(nextItem); // Link new node to end of new chain newChainPtr->setNext(newNodePtr); // Advance pointer to new last node newChainPtr = newChainPtr->getNext(); // Advance original-chain pointer origChainPtr = origChainPtr->getNext(); } // end while newChainPtr->setNext(nullptr); // Flag end of chain } // end if } // end copy constructor

template LinkedList::~LinkedList() { clear(); } // end destructor

template bool LinkedList::isEmpty() const { return itemCount == 0; } // end isEmpty

template int LinkedList::getLength() const { return itemCount; } // end getLength

template bool LinkedList::insert(int newPosition, const ItemType& newEntry) { bool ableToInsert = (newPosition >= 1) && (newPosition <= itemCount + 1); if (ableToInsert) { Node* newNodePtr = new Node(newEntry); if(newPosition == 1) { newNodePtr->setNext(headPtr); headPtr = newNodePtr; } else { Node* temp = headPtr; while(--newPosition>1) temp = temp->getNext(); newNodePtr->setNext(temp->getNext()); temp->setNext(newNodePtr); } itemCount++; } return ableToInsert; }

template bool LinkedList::remove(int position) { bool ableToRemove = (position >= 1) && (position <= itemCount); if (ableToRemove) { Node* curPtr = nullptr; if (position == 1) { // Remove the first node in the chain curPtr = headPtr; // Save pointer to node headPtr = headPtr->getNext(); } else { // Find node that is before the one to delete Node* prevPtr = getNodeAt(position - 1); // Point to node to delete curPtr = prevPtr->getNext(); // Disconnect indicated node from chain by connecting the // prior node with the one after prevPtr->setNext(curPtr->getNext()); } // end if // Return node to system curPtr->setNext(nullptr); delete curPtr; curPtr = nullptr; itemCount--; // Decrease count of entries } // end if return ableToRemove; } // end remove

template void LinkedList::clear() { while (!isEmpty()) remove(1); } // end clear

template ItemType LinkedList::getEntry(int position) const throw(PrecondViolatedExcep) { // Enforce precondition bool ableToGet = (position >= 1) && (position <= itemCount); if (ableToGet) { Node* nodePtr = getNodeAt(position); return nodePtr->getItem(); } else { string message = "getEntry() called with an empty list or "; message = message + "invalid position."; throw(PrecondViolatedExcep(message)); } // end if } // end getEntry

template void LinkedList::setEntry(int position, const ItemType& newEntry) throw(PrecondViolatedExcep) { // Enforce precondition bool ableToSet = (position >= 1) && (position <= itemCount); if (ableToSet) { Node* nodePtr = getNodeAt(position); nodePtr->setItem(newEntry); } else { string message = "setEntry() called with an invalid position."; throw(PrecondViolatedExcep(message)); } // end if } // end setEntry

template Node* LinkedList::getNodeAt(int position) const { // Debugging check of precondition assert( (position >= 1) && (position <= itemCount) ); // Count from the beginning of the chain Node* curPtr = headPtr; for (int skip = 1; skip < position; skip++) curPtr = curPtr->getNext(); return curPtr; }