C++ Rewrite Lab 10 using the doublyLinkedList instead of an array (Note: You dont have to limit the size to 100)

#ifndef H_doublyLinkedList

#define H_doublyLinkedList

#include

#include

using namespace std;

//Definition of the node

template

struct nodeType

{

Type info;

nodeType *next;

nodeType *back;

};

template

class doublyLinkedList

{

public:

const doublyLinkedList& operator=

(const doublyLinkedList &);

//Overload the assignment operator.

void initializeList();

//Function to initialize the list to an empty state.

//Postcondition: first = nullptr; last = nullptr; count = 0;

bool isEmptyList() const;

//Function to determine whether the list is empty.

//Postcondition: Returns true if the list is empty,

// otherwise returns false.

void destroy();

//Function to delete all the nodes from the list.

//Postcondition: first = nullptr; last = nullptr; count = 0;

void print() const;

//Function to output the info contained in each node.

void reversePrint() const;

//Function to output the info contained in each node

//in reverse order.

int length() const;

//Function to return the number of nodes in the list.

//Postcondition: The value of count is returned.

Type front() const;

//Function to return the first element of the list.

//Precondition: The list must exist and must not be empty.

//Postcondition: If the list is empty, the program

// terminates; otherwise, the first

// element of the list is returned.

Type back() const;

//Function to return the last element of the list.

//Precondition: The list must exist and must not be empty.

//Postcondition: If the list is empty, the program

// terminates; otherwise, the last

// element of the list is returned.

bool search(const Type& searchItem) const;

//Function to determine whether searchItem is in the list.

//Postcondition: Returns true if searchItem is found in

// the list, otherwise returns false.

void insert(const Type& insertItem);

//Function to insert insertItem in the list.

//Precondition: If the list is nonempty, it must be in

// order.

//Postcondition: insertItem is inserted at the proper place

// in the list, first points to the first

// node, last points to the last node of the

// new list, and count is incremented by 1.

void deleteNode(const Type& deleteItem);

//Function to delete deleteItem from the list.

//Postcondition: If found, the node containing deleteItem

// is deleted from the list; first points

// to the first node of the new list, last

// points to the last node of the new list,

// and count is decremented by 1; otherwise,

// an appropriate message is printed.

doublyLinkedList();

//default constructor

//Initializes the list to an empty state.

//Postcondition: first = nullptr; last = nullptr; count = 0;

doublyLinkedList(const doublyLinkedList& otherList);

//copy constructor

~doublyLinkedList();

//destructor

//Postcondition: The list object is destroyed.

protected:

int count;

nodeType *first; //pointer to the first node

nodeType *last; //pointer to the last node

private:

void copyList(const doublyLinkedList& otherList);

//Function to make a copy of otherList.

//Postcondition: A copy of otherList is created and

// assigned to this list.

};

template

doublyLinkedList::doublyLinkedList()

{

first= nullptr;

last = nullptr;

count = 0;

}

template

bool doublyLinkedList::isEmptyList() const

{

return (first == nullptr);

}

template

void doublyLinkedList::destroy()

{

nodeType *temp; //pointer to delete the node

while (first != nullptr)

{

temp = first;

first = first->next;

delete temp;

}

last = nullptr;

count = 0;

}

template

void doublyLinkedList::initializeList()

{

destroy();

}

template

int doublyLinkedList::length() const

{

return count;

}

template

void doublyLinkedList::print() const

{

nodeType *current; //pointer to traverse the list

current = first; //set current to point to the first node

while (current != nullptr)

{

cout << current->info << " "; //output info

current = current->next;

}//end while

}//end print

template

void doublyLinkedList::reversePrint() const

{

nodeType *current; //pointer to traverse

//the list

current = last; //set current to point to the

//last node

while (current != nullptr)

{

cout << current->info << " ";

current = current->back;

}//end while

}//end reversePrint

template

bool doublyLinkedList::

search(const Type& searchItem) const

{

bool found = false;

nodeType *current; //pointer to traverse the list

current = first;

while (current != nullptr && !found)

if (current->info >= searchItem)

found = true;

else

current = current->next;

if (found)

found = (current->info == searchItem); //test for

//equality

return found;

}//end search

template

Type doublyLinkedList::front() const

{

assert(first != nullptr);

return first->info;

}

template

Type doublyLinkedList::back() const

{

assert(last != nullptr);

return last->info;

}

template

void doublyLinkedList::insert(const Type& insertItem)

{

nodeType *current; //pointer to traverse the list

nodeType *trailCurrent; //pointer just before current

nodeType *newNode; //pointer to create a node

bool found;

newNode = new nodeType; //create the node

newNode->info = insertItem; //store the new item in the node

newNode->next = nullptr;

newNode->back = nullptr;

if(first == nullptr) //if the list is empty, newNode is

//the only node

{

first = newNode;

last = newNode;

count++;

}

else

{

found = false;

current = first;

while (current != nullptr && !found) //search the list

if (current->info >= insertItem)

found = true;

else

{

trailCurrent = current;

current = current->next;

}

if (current == first) //insert newNode before first

{

first->back = newNode;

newNode->next = first;

first = newNode;

count++;

}

else

{

//insert newNode between trailCurrent and current

if (current != nullptr)

{

trailCurrent->next = newNode;

newNode->back = trailCurrent;

newNode->next = current;

current->back = newNode;

}

else

{

trailCurrent->next = newNode;

newNode->back = trailCurrent;

last = newNode;

}

count++;

}//end else

}//end else

}//end insert

template

void doublyLinkedList::deleteNode(const Type& deleteItem)

{

nodeType *current; //pointer to traverse the list

nodeType *trailCurrent; //pointer just before current

bool found;

if (first == nullptr)

cout << "Cannot delete from an empty list." << endl;

else if (first->info == deleteItem) //node to be deleted is

//the first node

{

current = first;

first = first->next;

if (first != nullptr)

first->back = nullptr;

else

last = nullptr;

count--;

delete current;

}

else

{

found = false;

current = first;

while (current != nullptr && !found) //search the list

if (current->info >= deleteItem)

found = true;

else

current = current->next;

if (current == nullptr)

cout << "The item to be deleted is not in "

<< "the list." << endl;

else if (current->info == deleteItem) //check for

//equality

{

trailCurrent = current->back;

trailCurrent->next = current->next;

if (current->next != nullptr)

current->next->back = trailCurrent;

if (current == last)

last = trailCurrent;

count--;

delete current;

}

else

cout << "The item to be deleted is not in list."

<< endl;

}//end else

}//end deleteNode

template

void doublyLinkedList::copyList(const doublyLinkedList& otherList)

{

//ENTER CODE HERE (20%)

}//end copyList

template

doublyLinkedList::doublyLinkedList(const doublyLinkedList& otherList)

{

//ENTER CODE HERE (20%)

}

template

const doublyLinkedList& doublyLinkedList::operator=

(const doublyLinkedList& otherList)

{

//ENTER CODE HERE (20%)

}

template

doublyLinkedList::~doublyLinkedList()

{

cout << "Definition of the destructor is left as an exercise." << endl;

cout << "See Programming Execrise 9." << endl;

}

#endif