#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 { // 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) { // 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; } // end getNodeAt

1. 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:

- Node.h: add member variable Node* prev which points to previous node in linked list (or NULL for the first node in list)

- Node.h: add setPrev(), getPrev() prototypes, these are setter and getter functions for prev pointer

- Node.cpp: all three constructors need to be modified to handle prev

- Node.cpp: add setPrev(), getPrev() implementations

- LinkedList.h: add a new Node* called tailPtr which points to the last item in the list

- 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.

2. 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.