//COSC 2437 - Lab 5 - Posted

#ifndef H_doublyLinkedList

#define H_doublyLinkedList

#include

#include

using namespace std;

template

class doublyLinkedList

{

protected:

struct nodeType

{

Type info;

struct nodeType *next;

struct nodeType *back;

};

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.

public:

const doublyLinkedList& operator=

(const doublyLinkedList &);

//Overload the assignment operator.

void initializeList();

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

//Postcondition: first = NULL; last = NULL; 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 = NULL; last = NULL; 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 = NULL; last = NULL; count = 0;

doublyLinkedList(const doublyLinkedList& otherList);

//copy constructor

~doublyLinkedList();

//destructor

//Postcondition: The list object is destroyed.

};

template

doublyLinkedList::doublyLinkedList()

{

first= NULL;

last = NULL;

count = 0;

}

template

bool doublyLinkedList::isEmptyList() const

{

return (first == NULL);

}

template

void doublyLinkedList::destroy()

{

nodeType *temp; //pointer to delete the node

while (first != NULL)

{

temp = first;

first = first->next;

delete temp;

}

last = NULL;

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 != NULL)

{

cout 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 != NULL)

{

cout 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 != NULL && !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 != NULL);

return first->info;

}

template

Type doublyLinkedList::back() const

{

assert(last != NULL);

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 = NULL;

newNode->back = NULL;

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

//the only node

{

first = newNode;

last = newNode;

count++;

}

else

{

found = false;

current = first;

while (current != NULL && !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 != NULL)

{

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 == NULL)

cout

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

//the first node

{

current = first;

first = first->next;

if (first != NULL)

first->back = NULL;

else

last = NULL;

count--;

delete current;

}

else

{

found = false;

current = first;

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

if (current->info >= deleteItem)

found = true;

else

current = current->next;

if (current == NULL)

cout

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

//equality

{

trailCurrent = current->back;

trailCurrent->next = current->next;

if (current->next != NULL)

current->next->back = trailCurrent;

if (current == last)

last = trailCurrent;

count--;

delete current;

}

else

cout

}//end else

}//end deleteNode

template

void doublyLinkedList::copyList(const doublyLinkedList& otherList)

{

nodeType *newNode; //pointer to create a node

nodeType *current; //pointer to traverse the list

if(first != NULL) //if the list is nonempty, make it empty

destroy();

if(otherList.first == NULL) //otherList is empty

{

first = NULL;

last = NULL;

count = 0;

}

else

{

current = otherList.first; //current points to the

//list to be copied.

count = otherList.count;

//copy the first node

first = new nodeType; //create the node

first->info = current->info; //copy the info

first->next = NULL;

first->back = NULL;

last = first;

current = current->next;

//copy the remaining list

while (current != NULL)

{

newNode = new nodeType; //create the node

newNode->info = current->info;

newNode->next = NULL;

newNode->back = last;

last->next = newNode;

last = newNode;

current = current->next;

}//end while

}//end else

}

template

doublyLinkedList::doublyLinkedList(const doublyLinkedList& otherList)

{

//write the fucntion, 2 lines

}

template

const doublyLinkedList& doublyLinkedList::operator=

(const doublyLinkedList &otherList)

{

//write the function - 4 lines

//make sure you avoid self-copy

}

template

doublyLinkedList::~doublyLinkedList()

{

//write the function, one statement

}

#endif

Language: C++

Download the header file doublyLinkedList.h 1. Write a program that tests various operations of the class. Build the list from the user using a loop and a sentinel value (-999 for an integer list for example). Also build a string list. 2. Modify insert function, as discussed in lecture, so that you are not using trailCurrent. 3. Write the missing functions. You will write minimal code in the three functions, copy List is used in two of them. //Copy constructor doublyLinkedList (const doublyLinkedList& otherlist) //assignment operator overloading const doublyLinkedList& operator= (const doublyLinkedList &otherList) //destructor doublyLinkedList::-doublyLinkedList() Enter a list of positive integers ending with -999: -999 List in ascending order: 3 List in descending order: 9 Enter item to be deleted: 8 6 8 8 6 9 3 List after deleting 8: 3 6 Enter item to be searched: 7 9 7 is not in the list. ********Testing copy constructor********** intList: 3 6 9 ********Testing assignment operator******** temp: 369