Home > OS >  How does *node copy *next?
How does *node copy *next?

Time:10-18

I understand how linked lists work but this particular code is tough to grasp for me.

Its this leetcode problem (basically we are given address of a node which is to be deleted) whose solution can be implemented like the code snippet below:

1. class Solution {
2. public:
3.     void deleteNode(ListNode* node) {       
4.         ListNode* next = node->next;
5.         *node = *next;
6.         delete next;
7.     }
8. };

I know that:

  1. &node would mean the address of node variable
  2. node means the value (information) stored at address called node
  3. *node is used to dereference the pointer variable called node.

My doubt:

  1. [IMP] If we need to dereference a node pointer to get its data (like in line 5), then why not do so while accessing its member elements too (in line 4 node->next)?
  2. [Not IMP] Then, how does *node copies *next's data?

CodePudding user response:

node->next is actually equivalent to (*node).next. So there's an implicit dereference there already.

As for the copying, I assume you understand assignment between e.g. plain int variables? As in:

int a = 5;
int b = 10;

a = b;

It's quite natural that the value of b will be copied into a.

Now lets do the same again, but with one pointer to b:

int a = 5;
int b = 10;

int* pb = &b;  // pb is pointing to b

a = *pb;

This is really doing exactly the same as a = b.

And another example with a pointer to a instead:

int a = 5;
int b = 10;

int* pa = &a;  // pa is pointing to a

*pa = b;

Again this is the same as a = b.

Now putting them together:

int a = 5;
int b = 10;

int* pa = &a;  // pa is pointing to a
int* pb = &b;  // pb is pointing to b

*pa = *pb;

It's still the same as a = b.

It doesn't really matter if the pointers are to plain int variables or values, or to structures, it works the same for all pointers.

CodePudding user response:

*node is the entity of the passed-in parameter, including the node value and the next address. *node = *next is a shallow copy. If the ListNode is complex, the shallow copy may cause some problems. Deep copy is recommended. ListNode is here:

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

This way is better to understand:

class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* next = node->next;
        node->val = next->val;
        node->next = next->next;
        delete next;
    }
};
  • Related