链表对于类似的指针赋值有不同的行为

Question

我正在编写一个代码，当只给出指向节点的指针而没有给出头节点时，从链表中删除一个节点

/*
struct Node {
  int data;
  struct Node *next;
  Node(int x) {
    data = x;
    next = NULL;
  }
}*head;
*/

// This function should delete node from linked list. The function
// may assume that node exists in linked list and is not last node
// node: reference to the node which is to be deleted
void deleteNode(Node *node)
{
        node=(node->next);
}

不删除列表中的当前指针，但是，

/*
struct Node {
  int data;
  struct Node *next;
  Node(int x) {
    data = x;
    next = NULL;
  }
}*head;
*/

// This function should delete node from linked list. The function
// may assume that node exists in linked list and is not last node
// node: reference to the node which is to be deleted
void deleteNode(Node *node)
{
        *node=*(node->next);
}

从链表中删除节点

为什么？方法之间有什么区别？

Answer 1

给函数的（非引用）参数赋值在该函数之外没有影响。
（学习指针最重要的是指针没有什么特别的。）

和

一样

void f(int x) { x = 1000; }

int main()
{
    int x = 0;
    f(x);
    std::cout << x << std::endl;
}

将打印 0，而不是 1000。

因此，您的第一次尝试没有修改任何内容，也没有明显的效果。

您的第二次尝试也有问题 - 它复制了下一个节点但没有删除它。
如果您的节点是动态分配的（通常是这样），这就是内存泄漏。

你需要这样的东西：

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

虽然通过复制节点来修改列表有点不合常规，因为如果节点的数据很大，效率很低。
通常，您更新列表中的链接，但为此您需要知道前一个节点是什么。

Answer 2

在仅给出指向节点的指针时从链表中删除节点 - 这仅在双向链表或索引列表中才有可能。列表本身的性质表明您必须修改另一个节点才能从现有链中删除一个节点。

在第一种情况下，节点包含指向前一个节点的指针，成本为 O(1)，而对于索引列表，您有索引（键）并可以访问 mapping\indexing 机制，获取前一个节点的成本取决于方法用过的。由于最后一个原因，索引列表有时被实现为双向链接。

Answer 3

让我们举一个更简单的例子，用整数代替节点：

void Modify_1 (int *piVal, int *piNewVal)
 {  
    //piVal has adresse of i passed as argument 

     // similar to  node = (node->next);    
     piVal = piNewVal;  // This change just the VALUE of the pointer passed as argument !  


    //piVal has adresse of j now
 }

void Modify_2 (int *piVal)
{
    // similar to *node=*(node->next);
    *piVal = 0; // This change de content of pointer 
}

int main ()
{
    int i = 3;
    int j = 5;

    Modify_1 (&i, &j);
    cout << i << endl; // This print 3 !

    Modify_2 (&i);
    cout << i << endl; // This print 0

    return 0;
}

piVal 是一个包含 i 地址 VALUE 的 pointer。例子：0x00bcfdb4
如果您想要运行，此地址将作为值 (0x00bcfdb4) 传递。
只要不写 *piVal，就不会更改指向的内容，而只会更改地址的 VALUE。

如果你想改变指针，你需要一个**int（在你的例子中**node）

void Modify_3 (int **piVal, int *piNewVal)
{
   *piVal = piNewVal;   // this change de pointer adresse
}  

int main ()
{
    int x = 5;
    int *pi = &x;
    Modify_3 (&pi, &x);

    cout << *pi << endl; // This print 5  
}

链表对于类似的指针赋值有不同的行为

Linked list has different behaviour for similar pointer assignment

c++

pointers

linked-list

singly-linked-list

c++11