// A class template for holding a linked list.

// The node type is also a class template.

#ifndef LINKEDLIST_H

#define LINKEDLIST_H

//*********************************************

// The ListNode class creates a type used to *

// store a node of the linked list. *

//*********************************************

template

class ListNode

{

public:

T value; // Node value

ListNode *next; // Pointer to the next node

// Constructor

ListNode (T nodeValue)

{ value = nodeValue;

next = NULL;}

};

//*********************************************

// LinkedList class *

//*********************************************

template

class LinkedList

{

private:

ListNode *head; // List head pointer

public:

// Constructor

LinkedList()

{ head = NULL; }

// Destructor

~LinkedList();

// Linked list operations

void appendNode(T);

void insertNode(T);

void deleteNode(T);

void displayList() const;

};

//**************************************************

// appendNode appends a node containing the value *

// pased into newValue, to the end of the list. *

//**************************************************

template

void LinkedList::appendNode(T newValue)

{

ListNode *newNode; // To point to a new node

ListNode *nodePtr; // To move through the list

// Allocate a new node and store newValue there.

newNode = new ListNode(newValue);

// If there are no nodes in the list

// make newNode the first node.

if (!head)

head = newNode;

else // Otherwise, insert newNode at end.

{

// Initialize nodePtr to head of list.

nodePtr = head;

// Find the last node in the list.

while (nodePtr->next)

nodePtr = nodePtr->next;

// Insert newNode as the last node.

nodePtr->next = newNode;

}

}

//**************************************************

// displayList shows the value stored in each node *

// of the linked list pointed to by head. *

//**************************************************

template

void LinkedList::displayList() const

{

ListNode *nodePtr; // To move through the list

// Position nodePtr at the head of the list.

nodePtr = head;

// While nodePtr points to a node, traverse

// the list.

while (nodePtr)

{

// Display the value in this node.

cout value

// Move to the next node.

nodePtr = nodePtr->next;

}

}

//**************************************************

// The insertNode function inserts a node with *

// newValue copied to its value member. *

//**************************************************

template

void LinkedList::insertNode(T newValue)

{

ListNode *newNode; // A new node

ListNode *nodePtr; // To traverse the list

ListNode *previousNode = NULL; // The previous node

// Allocate a new node and store newValue there.

newNode = new ListNode(newValue);

// If there are no nodes in the list

// make newNode the first node

if (!head)

{

head = newNode;

newNode->next = NULL;

}

else // Otherwise, insert newNode

{

// Position nodePtr at the head of list.

nodePtr = head;

// Initialize previousNode to NULL.

previousNode = NULL;

// Skip all nodes whose value is less than newValue.

while (nodePtr != NULL && nodePtr->value

{

previousNode = nodePtr;

nodePtr = nodePtr->next;

}

// If the new node is to be the 1st in the list,

// insert it before all other nodes.

if (previousNode == NULL)

{

head = newNode;

newNode->next = nodePtr;

}

else // Otherwise insert after the previous node.

{

previousNode->next = newNode;

newNode->next = nodePtr;

}

}

}

//*****************************************************

// The deleteNode function searches for a node *

// with searchValue as its value. The node, if found, *

// is deleted from the list and from memory. *

//*****************************************************

template

void LinkedList::deleteNode(T searchValue)

{

ListNode *nodePtr; // To traverse the list

ListNode *previousNode; // To point to the previous node

// If the list is empty, do nothing.

if (!head)

return;

// Determine if the first node is the one.

if (head->value == searchValue)

{

nodePtr = head->next;

delete head;

head = nodePtr;

}

else

{

// Initialize nodePtr to head of list

nodePtr = head;

// Skip all nodes whose value member is

// not equal to num.

while (nodePtr != NULL && nodePtr->value != searchValue)

{

previousNode = nodePtr;

nodePtr = nodePtr->next;

}

// If nodePtr is not at the end of the list,

// link the previous node to the node after

// nodePtr, then delete nodePtr.

if (nodePtr)

{

previousNode->next = nodePtr->next;

delete nodePtr;

}

}

}

//**************************************************

// Destructor *

// This function deletes every node in the list. *

//**************************************************

template

LinkedList::~LinkedList()

{

ListNode *nodePtr; // To traverse the list

ListNode *nextNode; // To point to the next node

// Position nodePtr at the head of the list.

nodePtr = head;

// While nodePtr is not at the end of the list...

while (nodePtr != NULL)

{

// Save a pointer to the next node.

nextNode = nodePtr->next;

// Delete the current node.

delete nodePtr;

// Position nodePtr at the next node.

nodePtr = nextNode;

}

}

#endif

Modify/Expand LinkedList Template Class Assignment Use the LinkedList template class (definedin LinkedList.hversion 2), add following template member functions: 1 Linkedlist copy constructor 2. LinkedList search function The search function returns the position of a specificvalue inthe linked list. The first node in the listis at position 0, the second node is at positon 1, and so on. Ifvalue is not found on the LinkedList, the search should return-1. 3. Overloaded [loperator: Adding an overloaded operator function. This will give the linked list the ability to access nodes using a subscript, like an array. The subscript 0 will reference the first node in the list, the subscript 1 will reference the second node in the list, and so forth. If an invalid subscript isused, the function should throw an exception. 4LinkedUst reverse function The reverse function will put the linked list in reverseorder. Forexample: if the list is 1-2->3-4 after calling the reverse)function, the linked list should be: Test these functions using an appropriate driver program. Submission LinkedList.h Driver program testeach addedmember functions test using different class type T, int, double, and/or stringdata type. o o