the constructor needs to initialize tailPtr to nullptr - insert(): modify it to update prev pointers as well as next pointers. - remove(): modify to update prev pointers as well as next pointers. Add a new public member function to the LinkedList class named reverse() which reverses the items in the list. swap each node’s 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 constructor needs to initialize tailPtr to nullptr
- insert(): modify it to update prev pointers as well as next pointers.
- remove(): modify to update prev pointers as well as next pointers.
Add a new public member function to the LinkedList class named reverse() which reverses the items in the list. swap each node’s 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! 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.
@file LinkedList.cpp */
#include "LinkedList.h" // Header file
#include <cassert>
#include <string>
#include <cstdlib>
template<class ItemType>
LinkedList<ItemType>::LinkedList() : headPtr(nullptr), itemCount(0)
{
headPtr = nullptr;
itemCount = 0;
}
template<class ItemType>
LinkedList<ItemType>::LinkedList(const LinkedList<ItemType>& aList) : itemCount(aList.itemCount)
{
Node<ItemType>* origChainPtr = aList.headPtr;
if (origChainPtr == nullptr)
headPtr = nullptr;
else {
headPtr = new Node<ItemType>();
headPtr->setItem(origChainPtr->getItem());
Node<ItemType>* newChainPtr = headPtr;
origChainPtr = origChainPtr->getNext();
while (origChainPtr != nullptr) {
ItemType nextItem = origChainPtr->getItem();
Node<ItemType>* newNodePtr = new Node<ItemType>(nextItem);
newChainPtr->setNext(newNodePtr);
newChainPtr = newChainPtr->getNext();
origChainPtr = origChainPtr->getNext();
}
newChainPtr->setNext(nullptr); // Flag end of chain
} // end if
} // end copy constructor
template<class ItemType>
LinkedList<ItemType>::~LinkedList()
{
clear();
} // end destructor
template<class ItemType>
bool LinkedList<ItemType>::isEmpty() const
{
return itemCount == 0;
} // end isEmpty
template<class ItemType>
int LinkedList<ItemType>::getLength() const
{
return itemCount;
} // end getLength
template<class ItemType>
bool LinkedList<ItemType>::insert(int newPosition, const ItemType& newEntry)
{
bool ableToInsert = (newPosition >= 1) && (newPosition <= itemCount + 1);
if (ableToInsert)
{
Node<ItemType>* newNodePtr = new Node<ItemType>(newEntry);
if(newPosition == 1){
newNodePtr->setNext(headPtr);
headPtr = newNodePtr;
} else {
Node<ItemType>* temp = headPtr;
while(--newPosition>1)
temp = temp->getNext();
newNodePtr->setNext(temp->getNext());
temp->setNext(newNodePtr);
}
itemCount++;
}
return ableToInsert;
}
template<class ItemType>
bool LinkedList<ItemType>::remove(int position)
{
bool ableToRemove = (position >= 1) && (position <= itemCount);
if (ableToRemove)
{
Node<ItemType>* curPtr = nullptr;
if (position == 1) {
curPtr = headPtr;
headPtr = headPtr->getNext();
}
else {
Node<ItemType>* prevPtr = getNodeAt(position - 1);
curPtr = prevPtr->getNext();
prevPtr->setNext(curPtr->getNext());
}
curPtr->setNext(nullptr);
delete curPtr;
curPtr = nullptr;
itemCount--;
}
return ableToRemove;
}
template<class ItemType>
void LinkedList<ItemType>::clear() {
while (!isEmpty())
remove(1);
}
template<class ItemType>
ItemType LinkedList<ItemType>::getEntry(int position) const {
bool ableToGet = (position >= 1) && (position <= itemCount);
if (ableToGet) {
Node<ItemType>* nodePtr = getNodeAt(position);
return nodePtr->getItem();
}
else {
string message = "getEntry() called with an empty list or ";
message = message + "invalid position.";
throw(PrecondViolatedExcep(message));
}
}
template<class ItemType>
void LinkedList<ItemType>::setEntry(int position, const ItemType& newEntry) {
bool ableToSet = (position >= 1) && (position <= itemCount);
if (ableToSet) {
Node<ItemType>* nodePtr = getNodeAt(position);
nodePtr->setItem(newEntry);
}
else {
string message = "setEntry() called with an invalid position.";
throw(PrecondViolatedExcep(message));
}
}
template<class ItemType>
Node<ItemType>* LinkedList<ItemType>::getNodeAt(int position) const
{
assert( (position >= 1) && (position <= itemCount) );
Node<ItemType>* curPtr = headPtr;
for (int skip = 1; skip < position; skip++)
curPtr = curPtr->getNext();
return curPtr;
}
// add definitions of template types we will use (int or string now,
// add more types if necessary)
template class LinkedList<int>;
template class LinkedList<std::string>;
#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)
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
