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

template LinkedList::LinkedList() : 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 * newNodePtr = new Node(newEntry);

// Attach new node to chain if (newPosition == 1) { // Insert new node at beginning of chain newNodePtr->setNext(headPtr); headPtr = newNodePtr; } else { // Find node that will be before new node Node* prevPtr = getNodeAt(newPosition - 1);

// Insert new node after node to which prevPtr points newNodePtr->setNext(prevPtr->getNext()); prevPtr->setNext(newNodePtr); } // end if

itemCount++; // Increase count of entries } // end if

return ableToInsert; } // end insert

template bool LinkedList::remove(int position) { bool ableToRemove = (position >= 1) && (position * 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 * nodePtr = getNodeAt(position); return nodePtr->getItem(); } else { std::string message = "getEntry() called with an empty list or "; message = message + "invalid position."; throw(PrecondViolatedExcep(message)); } // end if } // end getEntry

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

template Node* LinkedList::getNodeAt(int position) const { // Debugging check of precondition assert((position >= 1) && (position

// Count from the beginning of the chain Node* curPtr = headPtr; for (int skip = 1; skip getNext();

return curPtr; } // end getNodeAt // End of implementation file.