Node.h

template

class Node

{

private:

ItemType item; // A data item

Node* next; // Pointer to next node

Node* prev;

public:

Node();

Node(const ItemType& anItem);

Node(const ItemType& anItem, Node* nextNodePtr, Node* prevNode$

void setItem(const ItemType& anItem);

void setNext(Node* nextNodePtr);

void setPrev(Node* prevNodePtr);

ItemType getItem() const ;

Node* getNext() const ;

Node* getPrev() const;

}; // end Node

Node.cpp

#include "Node.h"

#include

#include

template

Node::Node() : next(nullptr), prev(nullptr)

{

} // end default constructor

template

Node::Node(const ItemType& anItem) : item(anItem), next(nullptr), prev(null$

{

} // end constructor

template

Node::Node(const ItemType& anItem, Node* nextNodePtr, Node

item(anItem), next(nextNodePtr), prev(prevNodePtr)

{

} // end constructor

template

void Node::setItem(const ItemType& anItem)

{

item = anItem;

} // end setItem

template

void Node::setNext(Node* nextNodePtr)

{

next = nextNodePtr;

} // end setNext

template

ItemType Node::getItem() const

{

return item;

} // end getItem

template

Node* Node::getNext() const

{

return next;

} // end getNext

template

void Node :: setPrev(Node* prevNodePtr)

{

prev = prevNodePtr;

}

template

Node* Node :: getPrev() const

{

return prev;

}

LinkedList.h

#include "ListInterface.h"

#include "Node.h"

#include "PrecondViolatedExcep.h"

template

class LinkedList : public ListInterface

{

private:

Node* headPtr; // Pointer to first node in the chain;

// (contains the first entry in the list)

Node* tailPtr;

int itemCount; // Current count of list items

// Locates a specified node in this linked list.

// @pre position is the number of the desired node;

// position >= 1 and position <= itemCount.

// @post The node is found and a pointer to it is returned.

// @param position The number of the node to locate.

// @return A pointer to the node at the given position.

Node* getNodeAt(int position) const;

public:

LinkedList();

LinkedList(const LinkedList& aList);

virtual ~LinkedList();

bool isEmpty() const;

int getLength() const;

bool insert(int newPosition, const ItemType& newEntry);

bool remove(int position);

void clear();

void setEntry(int position, const ItemType& newEntry)

throw(PrecondViolatedExcep);

void reverse();

}; // end LinkedList 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$

{

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

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

} // 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(PrecondViolatedExce$

{

// 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(Pre$

{

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

template

void LinkedList :: reverse()

{

Node *curr, *prev, *next;

curr = headPtr;

prev = NULL;

while(curr != NULL)

{

next = curr->getNext();

curr->setNext(prev);

curr->setPrev(next);

prev = curr;

curr = next;

}

tailPtr = headPtr;

headPtr = prev;

}

My question is (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. ) thanks!