modify the linked list template.include a member function named rangeSearch. The
ID: 3539564 • Letter: M
Question
modify the linked list template.include a member function named rangeSearch. The function should search the list for a specified range values, defined by two numbers. All value found to be within the range shall be returned a pointer to a list of Nodes in search range. If no value is found, the function should return a Null pointer.
// A class template for holding a linked list.
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream> // For cout and NULL
using namespace std;
template <class T>
class LinkedList
{
private:
// Declare a structure for the list
struct ListNode
{
T value;
struct ListNode *next;
};
ListNode *head; // List head pointer
public:
LinkedList() // Constructor
{ head = NULL; }
~LinkedList(); // Destructor
void appendNode(T);
void insertNode(T);
void deleteNode(T);
void displayList();
int rangesearch(T); // search function
};
template <class T>
void LinkedList<T>::appendNode(T newValue)
{
ListNode *newNode, *nodePtr;
// Allocate a new node & store newValue
newNode = new ListNode;
newNode->value = newValue;
newNode->next = NULL;
// 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;
}
}
template <class T>
void LinkedList<T>::displayList()
{
ListNode *nodePtr;
nodePtr = head;
while (nodePtr)
{
cout << nodePtr->value << endl;
nodePtr = nodePtr->next;
}
}
template <class T>
void LinkedList<T>::insertNode(T newValue)
{
ListNode *newNode, *nodePtr, *previousNode = NULL;
// Allocate a new node & store newValue
newNode = new ListNode;
newNode->value = 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
{
// Initialize nodePtr to head of list and
// previousNode to NULL.
nodePtr = head;
previousNode = NULL;
// Skip all nodes whose value member 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 it after the prev. node.
{
previousNode->next = newNode;
newNode->next = nodePtr;
}
}
}
template <class T>
void LinkedList<T>::deleteNode(T searchValue)
{
ListNode *nodePtr, *previousNode;
// 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 searchValue.
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;
}
}
}
template <class T>
LinkedList<T>::~LinkedList()
{
ListNode *nodePtr, *nextNode;
nodePtr = head;
while (nodePtr != NULL)
{
nextNode = nodePtr->next;
delete nodePtr;
nodePtr = nextNode;
}
}
this is so far i got how can i impleement range searcch
Explanation / Answer
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream> // For cout and NULL
using namespace std;
template <class T>
class LinkedList
{
private:
// Declare a structure for the list
struct ListNode
{
T value;
struct ListNode *next;
};
ListNode *head; // List head pointer
public:
LinkedList() // Constructor
{ head = NULL; }
~LinkedList(); // Destructor
void appendNode(T);
void insertNode(T);
void deleteNode(T);
void displayList();
LinkedList<T> rangesearch(T , T); // search function
};
#endif
template <class T>
void LinkedList<T>::appendNode(T newValue)
{
ListNode *newNode, *nodePtr;
// Allocate a new node & store newValue
newNode = new ListNode;
newNode->value = newValue;
newNode->next = NULL;
// 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;
}
}
template <class T>
void LinkedList<T>::displayList()
{
ListNode *nodePtr;
nodePtr = head;
while (nodePtr)
{
cout << nodePtr->value << endl;
nodePtr = nodePtr->next;
}
}
template <class T>
void LinkedList<T>::insertNode(T newValue)
{
ListNode *newNode, *nodePtr, *previousNode = NULL;
// Allocate a new node & store newValue
newNode = new ListNode;
newNode->value = 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
{
// Initialize nodePtr to head of list and
// previousNode to NULL.
nodePtr = head;
previousNode = NULL;
// Skip all nodes whose value member 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 it after the prev. node.
{
previousNode->next = newNode;
newNode->next = nodePtr;
}
}
}
template <class T>
void LinkedList<T>::deleteNode(T searchValue)
{
ListNode *nodePtr, *previousNode;
// 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 searchValue.
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;
}
}
}
template <class T>
LinkedList<T> LinkedList<T> :: rangesearch(T min, T max)
{
ListNode *nodePtr = NULL;
ListNode *endNodePtr;
ListNode *currNodePtr = head;
//iterate through all the values in the list
while(currNodePtr)
{
//if the value of current node falls in range
if(currNodePtr->value >= min && currNodePtr->value <= max)
{
//insert new node with value equal to current value in the list
ListNode *newNode = new ListNode;
newNode->value = currNodePtr->value;
newNode->next = NULL;
//if list is empty back eaual to front of the list
if(!nodePtr)
{
nodePtr = newNode;
endNodePtr = nodePtr;
}
//otherwise enter at the end of the list
else
{
endNodePtr->next = newNode;
endNodePtr = endNodePtr->next;
}
}
currNodePtr = currNodePtr->next;
}
//return the list
}
template <class T>
LinkedList<T>::~LinkedList()
{
ListNode *nodePtr, *nextNode;
nodePtr = head;
while (nodePtr != NULL)
{
nextNode = nodePtr->next;
delete nodePtr;
nodePtr = nextNode;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.