Function to delete item from hashtable not deleting

[rlake]

Hello,

I have a hashtable that has chaining using a linked list. I am trying to write a function that will delete an item from the hashtable, but when it runs, it doesn't delete the item. Here is the function:

void MyChain::deleteItem(int val)
{
int location = (val % arraySize); //hash function
nodeType *link = hashtable[location]; //pointer to location in array of hashtable

while (link->next != NULL && link->info != val)
{
if (link->info == val) //if the item to be deleted is found
{
next = link; //set the pointer traversing the list to that node
link = link->next; //set the pointer to the node to be deleted to the next node
delete next; //delete the node with the value to be removed
}
else
{
next = link->next; //set the pointer traversing the list to the next node
}
}
}

If someone can give me some tips on why it is not deleting the item, I would appreciate it.

Thank you.

Regards

Ragan

[Bdanielz]

I think we would need to see more of your code to answer this question.


Looking at your code, I think my approach would be different.

If you intend to delete an item from a list that is inside of hash table,
then I would suggest writing a delete function for your list, with respect to an item in a list.

This way, from your hash table you can look up the list by key, then once you have the list pass in what item/data you need to, to perform the delete to the list itself. I think it makes more sense from a OOD point of view.

[rlake]

Thanks.

That's what I tried to do - write a delete function that allows you to enter a value, it searches through the list to find the item to delete.

I'll be happy to post more of my code. What would you like to see? I have a class to create the hashtable, a constructor, an insert function, the delete function (posted) and a print function.

Thanks,

Ragan

[Bdanielz]

post a runnable program, that reproduces the issue.

[rlake]

Here is the code:


#include<iostream>;

using namespace std;

struct nodeType
{
int info;
nodeType *link;
nodeType *next;
};

class MyChain
{
public:
void print() const; //Print the values of the hashtable
void push(int val); //Insert value into hashtable
void deleteItem(int val); //Remove value from hashtable
MyChain(); //Constructor
nodeType *next;

private:
int arraySize;
nodeType *hashtable[100];
};

MyChain::MyChain()
{
arraySize = 100;
for (int i = 0; i < arraySize; i++)
{
hashtable[i] = nullptr;
}
}

void MyChain::deleteItem(int val)
{
int location = (val % arraySize);
nodeType *entry = hashtable[location];
nodeType *prev = NULL;
if (entry == NULL || entry->info != val)
{
cout << "No element found at key" << val << endl;
return;
}
while (entry->next != NULL)
{
prev = entry;
entry = entry->next;
}
if (prev != NULL)
{
prev->next = entry->next;
}
delete entry;
cout << "Element deleted" << endl;
}

void MyChain::push(int val)
{
int location = val % arraySize;
nodeType *toInsert = new nodeType;
toInsert->link = NULL;
toInsert->info = val;
if (hashtable[location] == NULL)
{
hashtable[location] = toInsert;
}
else
{
nodeType *entry = hashtable[location];
while (entry->link != NULL)
{
entry = entry->link;
}
entry->link= toInsert;
toInsert->info = val;
}
}

void MyChain::print() const
{
nodeType *current;
for (int i = 0; i < arraySize; i++)
{
current = hashtable[i];
int pointerCounter = 0;
while (current != NULL)
{
cout << "Position [" << i << "]";
cout << "[" << pointerCounter << "]";
cout << current->info << " " <<endl;
current = current->link;
pointerCounter++;
}
}
}

int main()
{
MyChain newChain;
newChain.push(5);
newChain.push(11);
newChain.push(24);
newChain.push(51);
newChain.push(106);
newChain.push(5);
newChain.push(9);
newChain.print();
newChain.deleteItem(51);
newChain.print();
}


Thank you.

Regards,

Ragan

[cire]

In MyChain::deleteItem,
if (entry == NULL || entry->info != val) is wrong.
while (entry->next != NULL) is wrong.
And the fact that under no condition is any element of hashTable updated is wrong.

[Bdanielz]

What cire said it true. If you step through your delete function can see that all it does is creates a local copy of the node then bails.

I also think you are trying to do too much in one class. I wold try and take a more ODD approach.
Take a look at this article. http://pumpkinprogrammer.com/2014/06/21/c-tutorial-intro-to-hash-tables/
That is a solid approach to take IMO.

[rlake]

Thanks for the input. I'm trying to understand it.

if (entry == NULL || entry->info != val) - is this wrong because you only need to test if entry->info !=val?

Regarding while (entry->next != NULL), the idea behind this is to run the loop while the list is not empty to search for the item to be deleted. Why would one not test for this?

For updating the hashtable, since the hashtable is essentially an array with a chain of linked lists, my understanding is to delete an item from the hashtable, you change the pointer to the node to be deleted to the next node (like in a linked list) then you delete the node. Is that not correct?

Thank you.

Regards,

Ragan

[cire]

if (entry == NULL || entry->info != val) - is this wrong because you only need to test if entry->info !=val?

It is wrong because if entry->info is not equal to val, that doesn't mean val is not present.

Regarding while (entry->next != NULL), the idea behind this is to run the loop while the list is not empty to search for the item to be deleted. Why would one not test for this?

You are not looking for the item to be deleted, you are only iterating through the list.

For updating the hashtable, since the hashtable is essentially an array with a chain of linked lists, my understanding is to delete an item from the hashtable, you change the pointer to the node to be deleted to the next node (like in a linked list) then you delete the node. Is that not correct?

It is correct. In a subset of possible situations. What happens when the list contains only one item? In your current code, you delete the entry and continue on. That entry still contains the (now invalid) address of the deleted memory, and using it results in undefined behavior.

[rlake]

Thanks for the information.

I have tried implementing your suggestions, but I am still getting a read access violation when it tries to print the list after I run the delete function. (It does not generate a read access violation when the delete function is being run.) Thus, I'm not sure if the problem is with the delete function or the print function.

Here is the delete function:

void MyChain::deleteItem(int val)
{
int location = (val % arraySize); //hash function
nodeType *link;
nodeType *trailCurrent; //pointer just before current
nodeType *current;
nodeType *first= hashtable[location]; //pointer to traverse the list

//If list is empty
if (first == NULL)
cout << "Cannot delete from an empty list." << endl;
else
{

//If the first item in the list is the item to be deleted
if (first->info == val)
{
current = first;
first = first ->link;

if (first == NULL)
last = NULL;
delete current;
}
else
{
trailCurrent = first;
current = first->link;

//Search while the list isn't empty and the item to be deleted is not found.
while (current != NULL && current->info != val)
{
if (current->info != val)
{
trailCurrent = current;
current = current->link;
}
}

//If the item is found
if (current->info == val)
{
trailCurrent->link = current->link;
if (last == current)
last = trailCurrent;
delete current;
}
else
cout << "The item to be deleted is not in the list." << endl;
}
}
}

Here is the print function:

void MyChain::print() const
{
nodeType *current;

for (int i = 0; i < arraySize; i++)
{
current = hashtable[i];
int pointerCounter = 0;
while (current != NULL)
{
cout << "Position [" << i << "]";
cout << "[" << pointerCounter << "]";
cout << current->info << " " <<endl;
current = current->link;
pointerCounter++;
}
}
}

Again, any input you can provide is appreciated because I just can't seem to pinpoint the problem.

Thanks,

Ragan

[cire]

I have tried implementing your suggestions, but I am still getting a read access violation when it tries to print the list after I run the delete function.

You still fail to update the hashtable elements in the delete function.

If I were to write that function it might look something like this:

void MyChain::deleteItem(int val)
{
    auto bucket = val % arraySize;

    if ( auto entry = hashtable[bucket] ) {
        auto prev = static_cast<nodeType*>(nullptr);

        // look for node to delete
        while (entry->next && entry->info != val) {
            prev = entry;
            entry = entry->next;
        }

        if (entry->info == val) { // found val?
            if (prev)
                prev->next = entry->next;
            else
                hashtable[bucket] = nullptr;      // hashtable element updated

            delete entry;      
        }
    }
}

[rlake]

I see now what I was missing. Thank you very much!