CODEWITHSUNDEEP
c++linked-listhashtablenodes
user1965283
user1965283

Reputation: 147

Removing a node from a linked-list

I've created a Hash-table and I want to remove a node from the linked-list. The code works for removing the first node but not for removing others.

void intHashTable::remove(int num){
int location = ((unsigned)num) % size;
Node * runner = table[location];
int checker;

if(runner->next == NULL){
    if(num == table[location]->num){
        table[location] = NULL;
    }
}else{
    if(table[location]->num == num){
        table[location] = table[location]->next;
    }else{
        //This part doesn't seem to be working.
        Node *temp = runner->next;
        while(temp != NULL){ 
            if(temp->num == num){
                runner->next = temp->next;
                delete(temp);
                break;
            }
        }
    }
}

}

Upvotes: 2

Views: 588

Answers (2)

Cartroo
Cartroo

Reputation: 4343

You haven't updated temp to point to the next item within the loop:

temp = temp->next;

You also appear to represent an empty row with a NULL pointer in your table, but you don't handle this case properly in your code - if runner is NULL then you'll crash when you try to access runner->next in the first check. Also, you're failing to delete the node in some cases.

To fix these issues, you can update your code to something like this:

void intHashTable::remove(int num)
{
    int location = ((unsigned)num) % size;
    Node * runner = table[location];

    if (runner != NULL) {
        if (runner->num == num) {
            delete runner;
            table[location] = NULL;
        } else {
            while (runner->next != NULL) {
                if (runner->next->num == num) {
                    Node *temp = runner->next;
                    runner->next = runner->next->next;
                    delete temp;
                    break;
                }
                runner = runner->next;
            }
        }
    }
}

Also note that I've removed the brackets from delete, which is a C++ keyword and not a function.

If you use doubly-linked lists (i.e. with a previous pointer as well as a next) then you can simplify this code a little, although for something like a hash table where you only tend to iterate through in one direction it's probably not worth the expense of the extra pointer (an extra 8 bytes per item on a 64-bit system).

Upvotes: 2

Rost
Rost

Reputation: 9089

You didn't updated temp and runner variables inside loop:

    while(temp != NULL)
    { 
        if(temp->num == num)
        {
            runner->next = temp->next;
            delete temp;
            break;
        }
        runner = temp;     // Keep previous element to change its next pointer when num found
        temp = temp->next; // Advance current pointer to next element
    }

Upvotes: 1

Related Questions