Question: // A class template for holding a linked list. // The node type is also a class template. #ifndef LINKEDLIST_H #define LINKEDLIST_H //********************************************* // The
// 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
// Constructor
ListNode (T nodeValue)
{ value = nodeValue;
next = NULL;}
};
//*********************************************
// LinkedList class *
//*********************************************
template
class LinkedList
{
private:
ListNode
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
{
ListNode
ListNode
// Allocate a new node and store newValue there.
newNode = new ListNode
// 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
{
ListNode
// 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
{
ListNode
ListNode
ListNode
// Allocate a new node and store newValue there.
newNode = new ListNode
// 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
{
ListNode
ListNode
// 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
{
ListNode
ListNode
// 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
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help