Question: Please look at the code. Look at the LinkedList member function insert() in LinkedList.cpp. This is an incorrect implementation that ignores the position desired and
Please look at the code. Look at the LinkedList member function insert() in LinkedList.cpp. This is an incorrect implementation that ignores the position desired and always inserts at the beginning of the list. As a result, note how the test result for the entry at position 4 fails! Your job is to fix this function so it inserts in the correct position in the list. Once you've fixed it you should see the correct output from the tests.
/** 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)
{
// Create a new node containing the new entry
Node* newNodePtr = new Node(newEntry);
// This implementation ignores newPosition, and always put the new
// item at the beginning of the list.
// Your assignment is to correctly insert the item into newPosition
newNodePtr->setNext(headPtr);
headPtr = newNodePtr;
itemCount++; // Increase count of entries
} // 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;
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help