You are going to implement a Doubly Linked List. Your class will be called DoublyLinkedList. Using the LinkedList provided below, make the appropriate adjustments for it to become a doubly linked list:

Keep all the existing methods (suitably modified) Add a tail pointer to the implementation Add a Copy Constructor that does a deep copy. Add another new constructor that takes a (singly) Linked List as an argument and creates the Doubly Linked List from it: DoublyLinkedList(const LinkedList& linkedList). You will create new Nodes for the doubly linked list you will not modify the list passed in rather, you will copy from it. Add a method void reverse() which reverses the list. This method should not make a copy of the list, nor should it allocate any new nodes, nor should it swap data between nodes it must reverse the list simply by modifying pointers. Add the a method vector toVector(bool reverse) that returns a vector populated with the items in the list, in forward order, unless reverse is true, in which case the vector should be populated with the list items in reverse order (the list itself does not change). Remember you can easily go through a doubly linked list in either order, and you have a tail pointer so you now where the last node is.

Your main program should do the following: 1. Declare a singly linked called slist: LinkedList slist; Populate the list using the insert method to make it be the following:

2. Using the new Doubly Linked List constructor, pass this list as an argument to create a DoublyLinkedList object call dlist: DoublyLinkedList dlist(slist);

3. Use the toVector() method of dlist to create a vector of the data in forward order, and then loop through this vector to print the data.

4. Use the toVector() method of dlist to create a vector of the data in reverse order, and then loop through this vector to print the data. 5. Call the reverse method of dlist to reverse the list. 6. Use the toVector() method of dlist to create a vector of the data in forward order, and then loop through this vector to print the data. 7. Create a new Doubly Linked List called dlist2 that is a copy of dlist by using the copy constructor:: DoublyLinkedList dlist2(dlist); 8. Use the toVector() method of dlist2 to create a vector of the data in forward order, and then loop through this vector to print the data. 9. Call the reverse method of dlist2 to reverse the list. 10. Use the toVector() method of dlist2 to create a vector of the data in forward order, and then loop through this vector to print the data. 11. Use the toVector() method of dlist to create a vector of the data in forward order, and then loop through this vector to print the data.

The output should be as follows:

Step 3 dlist: aa bb cc dd Step 4 dlist: dd cc bb aa Step 6 dlist: dd cc bb aa Step 8 dlist2: dd cc bb aa Step 10 dlist2: aa bb cc dd Step 11 dlist: dd cc bb aa

Node.cpp

#include "Node.h"

Node::Node() : next(nullptr) { } // end default constructor

Node::Node(const ItemType& anItem) : item(anItem), next(nullptr) { } // end constructor

Node::Node(const ItemType& anItem, Node* nextNodePtr) : item(anItem), next(nextNodePtr) { } // end constructor

void Node::setItem(const ItemType& anItem) { item = anItem; } // end setItem

void Node::setNext(Node* nextNodePtr) { next = nextNodePtr; } // end setNext

ItemType Node::getItem() const { return item; } // end getItem

Node* Node::getNext() const { return next; } // end getNext

Node.h

#ifndef NODE_ #define NODE_

#include using namespace std;

typedef int ItemType;

class Node { private: ItemType item; // A data item Node* next; // Pointer to next node public: Node(); Node(const ItemType& anItem); Node(const ItemType& anItem, Node* nextNodePtr); void setItem(const ItemType& anItem); void setNext(Node* nextNodePtr); ItemType getItem() const ; Node* getNext() const ; }; // end Node

#endif

LinkedList.h

#ifndef LINKED_LIST_

#define LINKED_LIST_

#include "Node.h"

#include

using namespace std;

typedef int ItemType;

class LinkedList

{

private:

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

int itemCount; // Current count of list items

// Locates a specified node in this linked list.

Node* getNodeAt(int position) const;

public:

LinkedList();

// Copy constructor and destructor are supplied by compiler

bool isEmpty() const;

int getLength() const;

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

bool remove(int position);

void clear();

ItemType getEntry(int position) const;

ItemType replace(int position, const ItemType& newEntry);

virtual ~LinkedList();

}; // end ArrayList

#endif

LinkedList.cpp

#include "LinkedList.h" #include

LinkedList::LinkedList() : headPtr(nullptr), itemCount(0) { } // end default constructor

void LinkedList::clear() { while (!isEmpty()) remove(1); } // end clear

int LinkedList::getLength() const { return itemCount; } // end getLength

bool LinkedList::isEmpty() const { return itemCount == 0; } // end isEmpty

ItemType LinkedList::getEntry(int position) const { bool ableToGet = (position >= 1) && (position <= itemCount); if (ableToGet) { Node* nodePtr = getNodeAt(position); return nodePtr->getItem(); } else { std::string message = "getEntry() called with an empty list or "; message = message + "invalid position."; throw(message); } } // end getEntry

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); // Attach new node to chain if (newPosition == 1) { // Insert new node at beginning of chain newNodePtr->setNext(headPtr); headPtr = newNodePtr; } else { // Find node that will be before new node Node* prevPtr = getNodeAt(newPosition - 1); // Insert new node after node to which prevPtr points newNodePtr->setNext(prevPtr->getNext()); prevPtr->setNext(newNodePtr); } itemCount++; // Increase count of entries } return ableToInsert; } // end insert

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 remove Node* prevPtr = getNodeAt(position - 1); // Point to node to remove curPtr = prevPtr->getNext(); // Disconnect indicated node from chain by connecting the // prior node with the one after prevPtr->setNext(curPtr->getNext()); } // Return node to system curPtr->setNext(nullptr); delete curPtr; curPtr = nullptr; itemCount--; // Decrease count of entries } return ableToRemove; } // end remove

ItemType LinkedList::replace(int position, const ItemType& newEntry) { bool ableToReplace = (position >= 1) && (position <= itemCount); if (ableToReplace) { Node* entryPtr = getNodeAt(position); ItemType oldEntry = entryPtr->getItem(); entryPtr->setItem(newEntry); return oldEntry; } else { std::string message = "replace() called with an empty list or "; message = message + "invalid position."; throw(message); } } // end replace

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

LinkedList::~LinkedList() { clear(); } // end destructor

Greatly appreciate the help,