This is an incorrect implementation that ignores the position desired and always inserts at the beginning of the list. How to fix the insert function to make it inserts in the correct position in the list.

#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) { // Create a new node containing the new entry Node* newNodePtr = new Node(newEntry);

if (newPosition == 1) { newNodePtr->setNext(headPtr); headPtr = newNodePtr; } else { Node* prevPtr = getNodeAt(newPosition-1); newNodePtr->setNext(prevPtr->getNext()); prevPtr->setNext(newNodePtr); } itemCount++; return ableToInsert; } // end if return ableToInsert; } // end insert

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; }