CODEWITHSUNDEEP
c++algorithmmemory-managementdata-structureslinked-list
Gary Kim
Gary Kim

Reputation: 21

when deleting classical node struct after copying the node, must we worry about possible overwrites?

https://leetcode.com/problems/delete-node-in-a-linked-list/description/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

Problem statement: Given a linked list of at least size 2, you are given a pointer to one of the nodes (guaranteed not to be the tail). Delete the node.

Linked list [1,2,3,4], input: 2, correct output: [1,3,4]

void deleteNode(ListNode* node) {
    ListNode* next = node->next;
    *node = *(node->next);
    delete next;
}

Above is a valid solution. However, I am thinking it shouldn't be correct.

Reason: In the 2nd line of the function, you are copying the value/content of the whole node. So you end up copying the int value, as well as the address of the next node (i.e. the next node pointer).

However, in the 3rd and final line of the function, you end up deleting next (which is equivalent to node->next).

When you do enough allocations in the future, would this not cause overwrite issues? From my understanding, the next pointer now holds the address space of something that was just deleted.

If I am wrong in my understanding, I'd really appreciate someone correcting me.

Upvotes: 0

Views: 85

Answers (2)

HMD
HMD

Reputation: 2226

Let's investigate the function step by step:

ListNode* next = node->next;

Here you copy given node's next into a temporary pointer, so far so good. for example if you had {1, 2, 3, 4} and gave second node to this function now next is 3 and it's third item.

 *node = *(node->next);

Copy content of next of given node into node, as you mentioned this will also copy it's next to it. continuing given example now you have {1, 3, 3, 4} which both 3s (second and third item's next are 4 (forth item)).

delete next;

Delete next. Now, given past example what you are doing here is deleting the second 3 (third item). and your result will be {1, 3, 4}.

This method will not delete the exact given node (I mean it's not deleting given pointer) but it copy it's next into it then delete the next and it's works as intended.

enter image description here

Upvotes: 0

aybassiouny
aybassiouny

Reputation: 578

That's correct, dereferencing the memory location node used to point to is Undefined Behavior. It's worth pointing out that delete does not really zero the memory, because that's extra work and C++ is all about not doing anything it's not explicitly asked to do. 

int* x = new int;
*x = 5;
int* y = x;
delete x;
std::cout << *y << std::endl; // This outputs 5 on my machine (on release config)

What rather happens is that the memory manager in the OS marks those locations as free and they might get occupied later. Maybe not. Until this memory gets overwritten, it would return the correct value. But again, this is UB, and no production code should have it.

Keep in mind that sometimes the c++ runtime can zero the memory after it gets freed, for example when compiling with debug flags.

Upvotes: 0

Related Questions