Setting a struct element address to null in C++ (singly linked list)

Question

I have this struct:

struct Node {
    int num;
    Node *next;

    Node(int, Node*);
};

inside class Collection.

When I try to delete the last element of the list, using this function:

void Collection::remove(int num){
   Node *target = find(num);
   if (target == nullptr) return;
   n--;
   Node *temp = target ->next;
   if (temp == nullptr) {
       delete target;  
       target = nullptr;       // This is where the problem occurs
       return;
   } 
   target->num = temp->num;
   target->next = temp->next;
   delete temp;
}

the previous Node's *next still points to the address location that is now empty, how do I set the target memory location to null?

For more info, this is my function find()

Collection::Node* Collection::find(int num) {
    Node *temp = head;
    while (temp != nullptr && temp->num != num) temp = temp->next;
    return temp;
}

Answer 1

You're actually using a slight variation on the normal deletion logic, which works in most cases. That variation is, rather than deleting the current element, you move the data from the following element into it, then delete that following element. This means you never have to back up to the previous element, something that's difficult (without storing extra info or running through the list again) with a singly-linked list.

Unfortunately, the one case where that won't work is when you're deleting the final element in the list. In that case, there is no following element to move the data from and you therefore need to delete the current element and adjust the previous element to become the new end of the list.

And, since you need to do that anyway, you may as well revert to the normal logic for all cases :-)

With that logic, you basically need to have access to the element before the one you want to delete. Then you set its next pointer to bypass the one you're deleting.

You'll need to also handle the special case of deleting the first element in the list. Assuming you have a head member pointing to the first element and curr/prev pointing respectively to the node you want to delete and its predecessor, the pseudo-code would be:

if curr is head:
    set head to curr.next
else
    set prev.next = curr.next
free curr

---

One way to do this easily without involving too many changes is to modify your find method so that you can also use it to get the previous node as well:

Node* Collection::find(
    int num,
    Node **pPrev = nullptr
) {
    // Initially store null as previous item.

    if (pPrev != nullptr) *pPrev = nullptr;

    // Cycle through list until found or not there.

    Node *temp = head;
    while ((temp != nullptr) && (temp->num != num)) {
        // Update previous before advancing.

        if (pPrev != nullptr) *pPrev = temp;
        temp = temp->next;
    }
    return temp;
}

Note that I've just used Node in the code rather than Collection::Node, since your question had both variants and I'm unsure whether you're in a namespace called Collection. Simply adjust as necessary, based on your actual usage.

In any case, defaulting the second parameter to nullptr will allow you to call it exactly as you do currently (with one parameter, it won't bother trying to store the previous node pointer).

But, in the case where you want that previous pointer, you would use something like this to delete:

Node *prev;
Node *curr = find(num, &prev);    // Get previous as well.
if (curr != nullptr) {            // Only delete if actually found.
    if (prev == nullptr)          // Null means current is head.
        head = curr->next;
    else                          // Otherwise adjust previous.
        prev->next = curr->next;
    delete curr;                  // Regardless of head-ness, delete.
}

Answer 2

All this looks like an old-fashion C to me :)

To actually alter memory outside of your Collection::remove function, you should modify your find function to actually return pointer-to-pointer:

Node** find(int num) {
     Node **temp = &head;

     while (*temp != NULL && (*temp)->num != num)
     {
         temp = &((*temp)->next);
     }
     return temp;

}

Having pointer-on-pointer you can then alter your original memory:

int main(int argc, char *argv[])
{
   head = new Node(1, new Node(2, new Node(3, NULL)));

   Node **elem = find(2);


   if (*elem)
    {
        delete *elem;
        *elem = NULL;

        cout << "elem 2 deleted" << endl;
    }


   elem = find(2);
   if (*elem)
   {
      delete *elem;
      *elem = NULL;

       cout << "elem 2 deleted" << endl;
   }



   cout << "Hello World!" << endl;
   return 0;
}

And your Collection::remove will look like:

void Collection::remove(int num){
   Node **target = find(num);
   if (*target == nullptr) return;
   n--;
   Node *temp = (*target)->next;
   if (temp == nullptr) {
       delete *target;
       *target = nullptr;
       //cout << "elem " << num << " deleted " << endl;
       return;
   }
   (*target)->num = temp->num;
   (*target)->next = temp->next;
   delete temp;
}

But it seems your remove function will not work as it suppose to. It will delete only last element of list if the one will be equal to num parameter. To make it work correctly you will probably need to make this list forward and backward iterable to make previous element to point on the next one. Or you can alter find function to return previous element as well.

Answer 3

Setting the pointer to nullptr doesn't necessarily change its value. If you dereference the nullptr you are inciting undefined behaviour (see here). In this case undefined behaviour means that you are still able to reference that memory and interperet it. But next time it might make your program crash. What you are doing here is bad:

if (temp == nullptr) {
       delete target;  
       target = nullptr;       // You delete target
} 
target->num = temp->num;       // Then you immediately dereference it.

You need to set the next before you delete target.

target->next = temp->next;
delete temp;