Add a new public member function to the LinkedList class named reverse() which reverses the items in the list. You must take advantage of the doubly-linked list structure to do this efficiently as discussed in the videos/pdfs, i.e. swap each nodes prev/next pointers, and finally swap headPtr/tailPtr. Demonstrate your function works by creating a sample list of a few entries in main(), printing out the contents of the list, reversing the list, and then printing out the contents of the list again to show that the list has been reversed.
Note: your function must actually reverse the items in the doubly-linked list, not just print them out in reverse order!
Note: we won't use the copy constructor in this assignment, and as such you aren't required to update the copy constructor to work with a doubly-linked list.
/** 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; }
