I am using pointers for the first time, and am trying to write a function that removes a node and a function that deletes the node. My code recognizes when I insert a key and data (for ex: key = 123, data = 123). However, when I try to delete the key 123, it doesn't recognize that it exists. Here is my LList.cpp, I can include other code if needed:
#include <iostream>
#include "LList.h"
//----------------------------------------------------
// constructor & destructor
//----------------------------------------------------
LList::LList() {
head = NULL;
} // constructor (default)
LList::~LList() {
if (head) delete head;
} // destructor
//----------------------------------------------------
// print
//----------------------------------------------------
// prints each node in the list, or EMPTY when there
// are no nodes to print
//----------------------------------------------------
void LList::print() {
if (head == NULL)
cout << "EMPTY\n\n";
else {
node* p;
p = head;
while (p != NULL) {
p->print();
p = p->next;
}
cout << endl;
}
} // print()
//----------------------------------------------------
// search
//----------------------------------------------------
// Given: key to search for
// Returns: pointer to a node in the list found to have
// the given search key, or NULL for not found
//----------------------------------------------------
node* LList::search(int srchKey) {
if (head == NULL)
return NULL;
node* itr = head;
while (itr != NULL) {
if (itr->key == srchKey)
itr = itr->next;
}
return itr;
} // search()
//----------------------------------------------------
// findNode
//----------------------------------------------------
// Given: a key to search for
// Searches for a node with the given key, and if
// found, invokes the print() method in the found node.
// Otherwise, prints "not found"
//----------------------------------------------------
void LList::findNode(int srchkey) {
if (head == NULL) {
cout << "not found\n";
}
node* itr = head;
while (itr != NULL) {
if (itr->key == srchkey) {
print();
}
itr = itr->next;
}
cout << "not found\n";
} // findNode()
//----------------------------------------------------
// getb4
//----------------------------------------------------
// Given: a pointer to a node in the list
// Returns: a pointer to the node in the list BEFORE
// the one pointed to by r, OR
// NULL when r is the head or not found in
// the list
//----------------------------------------------------
node* LList::getb4(node* r) {
node* tmp = head;
while (tmp->next != NULL) {
if (tmp->next == r)
return tmp;
tmp = tmp->next;
}
return NULL;
} // getb4()
//----------------------------------------------------
// insert
//----------------------------------------------------
// Given: key and data for a new node
// Allocates/populates a new node
// When a node with the same key already exists:
// the current/old node is replaced by the new one
// and the old one is placed on the new one's
// duplicate list.
// Otherwise, the new node is prepended to the head
// of the list.
//----------------------------------------------------
void LList::insert(int k, string d) {
node* newNode = new node();
node* currentNode, *prevNode;
newNode->key = k;
newNode->data = d;
if (head == NULL) {
head = newNode;
}
else {
currentNode = search(k);
if (currentNode == NULL) {
newNode->next = head;
head = newNode;
}
if (currentNode == head) {
newNode->next = head->next;
head->next = NULL;
newNode->dup = head;
head = newNode;
}
prevNode = getb4(currentNode);
if (prevNode == NULL)
return;
prevNode->next = newNode;
//newNode->next = currentNode->next;
currentNode->next = NULL;
newNode->dup = currentNode;
}
} // insert()
//----------------------------------------------------
// remove
//----------------------------------------------------
// Given: a pointer to a node in the list to be removed
// BUT NOT DELETED/DESTROYED
// Returns: TRUE - when the node was successfully removed
// FALSE - when the given node is NULL or the node
// is not actually in the list.
// Simply removes the node from the linked list.
// (including setting the NEXT pointer in the node to NULL)
//----------------------------------------------------
bool LList::remove(node* r) {
if (r == NULL || search(r->key) == NULL) {
return false;
}
if (r == head) {
head = head->next;
}
else {
node* prev = getb4(r);
prev->next = r->next;
}
r->next = NULL;
return true;
} // remove()
//----------------------------------------------------
// drop
//----------------------------------------------------
// Given: key of a node to drop
// Returns: TRUE when a node was found and deleted
// FALSE when a node with the given key not found,
// or the remove() fails.
// Searches for a node in the list with the given key:
// When found, removes and deletes the node
//----------------------------------------------------
bool LList::drop(int k) {
node* currentNode = search(k);
if (currentNode == NULL || !remove(currentNode))
return false;
node* tmp = currentNode;
while (tmp != NULL) {
currentNode = currentNode->dup;
remove(tmp);
tmp = currentNode;
}
return true;
} // drop()
//----------------------------------------------------
// max
//----------------------------------------------------
// Returns: a pointer to the node with the highest key
// or NULL when there list is empty.
node* LList::max() {
if (head == NULL)
return NULL;
node* max = head;
node* tmp = head->next;
while (tmp != NULL) {
if ((tmp->key) > (max->key)) {
max = tmp;
}
tmp = tmp->next;
}
return max;
} // max()
This loop:
while (itr != NULL) {
if (itr->key == srchKey)
itr = itr->next;
}
return itr;
is not correct. You are either iterating if the key is found, or not iterating at all. You need to iterate through the list, and search for the key while doing so:
while (itr != NULL) {
if (itr->key == srchKey)
break;
itr = itr->next;
}
return itr;
Also, your destructor is incorrect; you are only deleting the first node, and leaking the rest. You need to delete all the nodes by iterating through the linked-list:
LList::~LList() {
while (head)
delete std::exchange(head, head->next);
}
Also, prefer to use nullptr, instead of NULL.