CODEWITHSUNDEEP
c++pointersdereference
Adrian
Adrian

Reputation: 9590

Pointer to pointer assignment and dereference in C++

Let's say I have a linked list node like the following:

struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};

The goal is to write a function to delete a node in a singly-linked list. One efficient way to do it in constant time is something like this:

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

This works, but why do we need to dereference the pointers?

If node is a pointer and tmp is a pointer, why does it need to dereferenced? Why can't I do node = tmp?

Upvotes: 1

Views: 637

Answers (8)

eerorika
eerorika

Reputation: 238311

but why do we need to dereference the pointers?

Let's explore what happens if we don't indirect through the pointers:

auto *tmp = node->next;
node = tmp;
delete tmp;

This would be equivalent to just

delete node->next;

// resulting structure
previous    node             next (deleted)     next next (leaked)
1---------->2----dangling--->_                  4

// desired structure that we get from the correct code
previous    node             next (deleted)     next next
                             _
1-----------3---------------------------------->4

So, we end up with wrong node being deleted, and with a dangling pointer in the node that was supposed to be deleted.

Note that even the correct inirecting version is broken when attempting to delete the last node.

Upvotes: -1

Devolus
Devolus

Reputation: 22074

What your function really does, is that it doesn't delete the node from the parameter, but the next node, overwriting the current node with the follower.

The dereferencing of the pointer acts like a memcpy() and moves the data from the next node to the current. You are not copying the pointers but the data it points to.

This way you can repeatedly call the function with the same node pointer, and it will move down the chain. However, since you are not checking the pointer, the last node probably has a NULL pointer and will crash on derefencing.

So you need to do

 if (tmp)
     *node = *tmp;

Example:

typedef struct list
{
    struct list *next;
    int value;
} List;

void deleteNext(List* node)
{
    auto *tmp = node->next;

    if(tmp)
        *node = *tmp;

    delete tmp;
}
int main(int argc, char *argv[])
{
    List *l0 = new List;
    List *l1 = new List;
    l0->value = 0;
    l0->next = l1;
    l1->value = 1;
    l1->next = NULL;

    deleteNext(l0);
    deleteNext(l0); // Without the 'if' it will crash here.

    return 0;
}

Upvotes: 0

Hanjoung Lee
Hanjoung Lee

Reputation: 2152

  1. As others pointed out, node = tmp just changes the argument(local variable)
  2. *node = *tmp is to copy the content of ListNode which is equivalent to node.val = tmp.val; node.next = tmp.next
  3. This function actually removes the next element - it works, but it invalidates the next pointer(if there was something that refers node->next as a pointer, it is now a dangling pointer)

Upvotes: 0

Adrian Mole
Adrian Mole

Reputation: 51825

Let's break down the three lines of your deleteNode function:

    auto *tmp = node->next;

This creates a local variable, tmp which will be a copy of the next field of the passed node parameter. This is a pointer to the next structure in the list and, once we've made a copy of it, we can erase or overwrite that member.

    *node = *tmp;

This copies the actual data of the structure pointed to by tmp (that is, the next node in the list) to the current node, overwriting the next field as it does so. We need to dereference both pointers in order to copy the values of the structures pointed to.

    delete tmp;

This deletes the 'next' node in the given list. However, we have already copied all its data (including its next member) into our current node, so our modified list now starts with (effectively) the second one in the original list (the passed parameter); notably, the next field of *node will now be the address originally stored in node->next->next – thus, we have 'skipped' an entry (the second) in the list and deleted it.

Upvotes: 1

Nikolay Karashtranov
Nikolay Karashtranov

Reputation: 91

If you do node = tmp and after that delete tmp you will be deleting the ListNode, which node points to.

Upvotes: 0

prog-fh
prog-fh

Reputation: 16805

When performing *node=*tmp you copy all the bytes of *tmp into *node thus node->val now holds tmp->val and node->next now holds tmp->next.

The old content of node has been forgotten (it's normal since you want to get rid of this node) but you saved the content of the next node at this same place. Then if you delete the next node (known through tmp) you don't lose its content (it has been saved in the previous node).

Upvotes: 1

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122133

Why can't I do node = tmp ?

You can do that, but it won't do anything useful. node is a local variable in deleteNode. As it is a pointer you can use that local pointer to modify what it points to, but modfying the pointer itself has no effect outside of the function.

Actually pointers are not different with respect to that. You also cannot observe any effect from outside when you have

void foo(int x) {
    x = 42;
}

Passing a reference is different:

void bar(int& x) {
    x = 42;
}
int a = 0;
bar(a);    // now a == 42

Same with pointers:

void bar_ptr(int*& x) {
      x = nullptr;
}
int* b = &a;
bar_ptr(b);   // now b == nullptr

Upvotes: 0

OhadShwartzman
OhadShwartzman

Reputation: 41

The reason you can't just write node = tmp is because that wouldn't change anything outside of your function.

Given this linked list

node0 -> node1 -> node2 -> node3

If you want to delete node1, the desired outcome would be

node0 -> node2 -> node3

If you don't want to actively modify the pointer value (that is, the address next) in node0, you have to move the value inside node2 to where node1 was.

Upvotes: 0

Related Questions