// A class template for holding a linked list. // The node type is also a class
ID: 3731039 • Letter: #
Question
// 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 T>
class ListNode
{
public:
T value; // Node value
ListNode<T> *next; // Pointer to the next node
// Constructor
ListNode (T nodeValue)
{ value = nodeValue;
next = NULL;}
};
//*********************************************
// LinkedList class *
//*********************************************
template <class T>
class LinkedList
{
private:
ListNode<T> *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 <class T>
void LinkedList<T>::appendNode(T newValue)
{
ListNode<T> *newNode; // To point to a new node
ListNode<T> *nodePtr; // To move through the list
// Allocate a new node and store newValue there.
newNode = new ListNode<T>(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 <class T>
void LinkedList<T>::displayList() const
{
ListNode<T> *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 << nodePtr->value << endl;
// Move to the next node.
nodePtr = nodePtr->next;
}
}
//**************************************************
// The insertNode function inserts a node with *
// newValue copied to its value member. *
//**************************************************
template <class T>
void LinkedList<T>::insertNode(T newValue)
{
ListNode<T> *newNode; // A new node
ListNode<T> *nodePtr; // To traverse the list
ListNode<T> *previousNode = NULL; // The previous node
// Allocate a new node and store newValue there.
newNode = new ListNode<T>(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 < newValue)
{
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 <class T>
void LinkedList<T>::deleteNode(T searchValue)
{
ListNode<T> *nodePtr; // To traverse the list
ListNode<T> *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 <class T>
LinkedList<T>::~LinkedList()
{
ListNode<T> *nodePtr; // To traverse the list
ListNode<T> *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 oExplanation / Answer
// 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 T>
class ListNode
{
public:
T value; // Node value
ListNode<T> *next; // Pointer to the next node
// Constructor
ListNode (T nodeValue)
{ value = nodeValue;
next = NULL;}
};
//*********************************************
// LinkedList class *
//*********************************************
template <class T>
class LinkedList
{
private:
ListNode<T> *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;
LinkedList(const LinkedList&);
int search(T) const;
T operator[](int pos);
void reversedLinkedList();
};
//**************************************************
// appendNode appends a node containing the value *
// pased into newValue, to the end of the list. *
//**************************************************
template <class T>
void LinkedList<T>::appendNode(T newValue)
{
ListNode<T> *newNode; // To point to a new node
ListNode<T> *nodePtr; // To move through the list
// Allocate a new node and store newValue there.
newNode = new ListNode<T>(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 <class T>
void LinkedList<T>::displayList() const
{
ListNode<T> *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 << nodePtr->value << endl;
// Move to the next node.
nodePtr = nodePtr->next;
}
}
//**************************************************
// The insertNode function inserts a node with *
// newValue copied to its value member. *
//**************************************************
template <class T>
void LinkedList<T>::insertNode(T newValue)
{
ListNode<T> *newNode; // A new node
ListNode<T> *nodePtr; // To traverse the list
ListNode<T> *previousNode = NULL; // The previous node
// Allocate a new node and store newValue there.
newNode = new ListNode<T>(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 < newValue)
{
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 <class T>
void LinkedList<T>::deleteNode(T searchValue)
{
ListNode<T> *nodePtr; // To traverse the list
ListNode<T> *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;
}
}
}
//******************************************************************************
//Copy Constructor
//This function performs deep copy of each node in the list
//to another linked list
//******************************************************************************
template <class T>
LinkedList<T>::LinkedList(const LinkedList &aList)
{
//Intialize the head to NULL
head= NULL;
//make a temporary variable point to head of the list to be copied
ListNode<T> *current = aList.head;
for (current = head; current != NULL; current = current->next)
appendNode(current->value); // add the current node to the new linked list to which deep copy has to be done
}
//****************************************************************
//This function searches for a data in a linked list.
// If the data is found, return the position of that
// data in linked list, if not found return -1 value
//******************************************************************
template<class T>
int LinkedList<T>::search(const T data) const
{
int count=0; // variable to keep track on the position of the data in linked list
ListNode<T> *current ;
// if list is empty return -1
if (head == NULL)
return -1;
for (current = head; current != NULL; current = current->next)
if (current ->value == data) // if current node's value is equal to the search data return the count value that holds the position
return count;
else
count++; // if it is not equal move to next position in list and continue the search till end of list
return -1; //if the search reaches the end of the list and the data is not found, return -1
}
//*****************************************************************************
//This function overloads the operator[] to fetch the node value
//based on its position in the list
//****************************************************************************
template< class T >
T LinkedList<T>::operator[](int pos) {
ListNode<T> *current;
int i = 0;
for(current = head;current != NULL;current = current->next) {
if(i == pos) // if the position of current node is equal to given position return that node value
return current->value;
else
i++; // if it is not equal move to next position in list and continue till the given position is reached
}
if( pos >= i)
{
const char * error = "Error: invalid subscript";
throw error;
}
}
//**********************************************************
//This function reverses the linked list
//********************************************************
template< class T >
void LinkedList<T>::reversedLinkedList()
{
if(head == NULL) return;
ListNode<T> *prev = NULL, *current = NULL, *next = NULL;
current = head;
while(current != NULL){
next = current->next;
current->next = prev;
prev = current;
current = next;
}
// now let the head point at the last node (prev)
head = prev;
}
//**************************************************
// Destructor *
// This function deletes every node in the list. *
//**************************************************
template <class T>
LinkedList<T>::~LinkedList()
{
ListNode<T> *nodePtr; // To traverse the list
ListNode<T> *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
int main()
{
LinkedList<int> *myIntList = new LinkedList<int>();
int num = 0;
int positionInList,valueInPosition;
for(int i = 0;i < 10;i++) {
num = rand()%10 + 1;
myIntList->appendNode(num);
}
myIntList->displayList();
LinkedList<int> *copyList(myIntList);
copyList->displayList();
positionInList=myIntList->search(6);
cout<<"position of value 6 is: "<<positionInList<<" ";
try{
valueInPosition=(*myIntList)[5];
cout<<"value in position 5 is:"<<valueInPosition<<" ";
} catch (const char * err) {
cout << err << " ";
}
myIntList->reversedLinkedList();
myIntList->displayList();
LinkedList<double> *myDoubleList = new LinkedList<double>();
myDoubleList->appendNode(2.5);
myDoubleList->appendNode(12.25);
myDoubleList->appendNode(6.0);
myDoubleList->appendNode(40.725);
myDoubleList->displayList();
LinkedList<double> *copyDList(myDoubleList);
copyDList->displayList();
positionInList=myDoubleList ->search(40.725);
cout<<"position of value 40.725 is: "<<positionInList<<" ";
try{
valueInPosition=(*myDoubleList)[5];
cout<<"value in position 5 is:"<<valueInPosition<<" ";
} catch (const char * err) {
cout << err << " ";
}
myDoubleList->reversedLinkedList();
myDoubleList->displayList();
}
Output :
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.