Deleting node in linked list causes output of seemingly random nubmers

Question

I am trying to delete a node from a linked list using this function:

void del_node(int del_data)
    {
        node* temp = NULL;
        node* trail = NULL;
        node* del_ptr = NULL;
        temp = head;
        trail = head;

        while (temp != NULL && temp->data != del_data)
        {
            trail = temp;
            temp = temp->next;
        }

        if (temp != NULL) {
            del_ptr = temp;
            temp = temp->next;
            trail->next = temp;
            delete(del_ptr);
        }
    }

It seems like it deletes it fine until i print the linked list using this:


    void print()
    {
        node* temp = NULL;
        temp = head;
        while (temp != NULL)
        {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }

and it starts outputting seemingly random numbers, can anybody help me with this, really confused as this code comes from a tutorial.

Even if you deleted the head node, you forgot to reset the head node to the new head node. What tutorial gave you this erroneous code? Just as an example, try to delete a node from a linked list that has only one element -- then you will see things fall apart. — PaulMcKenzie, Mar 20 '21 at 18:08
One point of advice when creating your own linked lists with pointers is its often good to draw a diagram on what happens with the pointers before and after the operation. Also good to think about what happens to the head and tail nodes — drescherjm, Mar 20 '21 at 18:29
Related thread: [How do I properly delete nodes of a linked list?](https://stackoverflow.com/q/22121257/12149471) — Andreas Wenzel, Mar 20 '21 at 21:32

score 2 · Answer 1 · answered Mar 20 '21 at 18:26

Your algorithm doesn't manage the head pointer correctly whatsoever. Any changes that ultimately should modify the head pointer don't, and that's a huge problem. A pointer to pointer algorithm not only solves this problem, it also delivers a considerably more succinct solution:

void del_node(int del_data)
{
    struct node **pp = &head;
    while (*pp && (*pp)->data != del_data)
        pp = &(*pp)->next;

    if (*pp)
    {
        node *tmp = *pp;
        *pp = tmp->next;
        delete tmp;
    }
}

This will work for any list condition including:

An empty list. i.e. head is null.
A single-node list. If the value matches head->data it will properly delete and reset the node pointer.
A multi-node list. The first matching node will be removed, and it will properly fix up the head node pointer if that was the matching location.
All of the above, in cases where there is no matching node, the list remains unchanged.

Fulfilling all of that in such a short algorithm + implementation is beneficial.

I totally agree that this pointer to pointer solution is the more elegant solution. And [Linus Torvalds does, too](https://grisha.org/blog/2013/04/02/linus-on-understanding-pointers/). :-) — Andreas Wenzel, Mar 20 '21 at 21:42
I do too :) The reason why i accepted the answer above as the solution was due to Joesph using my original code. — Kerch, Mar 21 '21 at 00:56

score 0 · Accepted Answer · answered Mar 20 '21 at 18:23

I'll comment on your code inline:

void del_node(int del_data)
{
    node* temp = NULL;
    node* trail = NULL;
    node* del_ptr = NULL;
    temp = head;
    trail = head;

    // This is fine, but recommend you use nullptr instead of NULL.
    // This will find the first instance of data matches del_data,
    // But if you are trying to delete all instances of del_data,
    // You'll need to do this a little differently.
    while (temp != NULL && temp->data != del_data)
    {
        trail = temp;
        temp = temp->next;
    }

    // This if is fine, but see previous comment about using nullptr
    // instead of NULL.
    if (temp != NULL) {
        del_ptr = temp;
        temp = temp->next;
        // Problematic: What if trail is null?
        trail->next = temp;
        delete(del_ptr);
    }
}

Your code isn't bad. I wouldn't have written exactly like this, but I'm going to replace your if-statement:

if (temp != nullptr) {
    // If trail is nullptr, then we're deleting from the head
    if (trail == nullptr) {
        head = temp->next;
    }
    else {
        trail->next = temp->next;
    }

    delete(temp);
}

There's no need for the temporary. Just point around temp as you see in the if-else block and then delete temp.

Deleting node in linked list causes output of seemingly random nubmers

2 Answers2