为链表添加​​元素时为什么不使用指针指针？

Question

我已经看到了这个问题：

它使用下面的代码添加元素OA列表：C linked list inserting node at the end

int addNodeBottom(int val, node *head){ 

    //create new node 
    node *newNode = (node*)malloc(sizeof(node)); 

    if(newNode == NULL){ 
     fprintf(stderr, "Unable to allocate memory for new node\n"); 
     exit(-1); 
    } 

    newNode->value = val; 
    newNode->next = NULL; // Change 1 

    //check for first insertion 
    if(head->next == NULL){ 
     head->next = newNode; 
     printf("added at beginning\n"); 
    } 

    else 
    { 
     //else loop through the list and find the last 
     //node, insert next to it 
     node *current = head; 
     while (true) { // Change 2 
      if(current->next == NULL) 
      { 
       current->next = newNode; 
       printf("added later\n"); 
       break; // Change 3 
      } 
      current = current->next; 
     }; 
    } 
    return 0; 
} 

为什么头为节点*head，而不是node **head如果我们要内改变它传递我们希望这些变化在函数之外传播？我在这里错过了什么？

Answer 1

head永远不会在此函数中直接修改。只有head->next被分配给另一个值。因此你不需要使用指向指针的指针。

Answer 2

基本上，没有理由为什么它不能。事实上，这是Linus Torvalds指出的对指针掌控的事情之一。相关问题：Using pointers to remove item from singly-linked list

Answer 3

你可以使用指针的指针，像这样可能使代码有点更优雅：

int addNodeBottom(int val, node **link){ 
    node *newNode = ...; 
    ... 
    if(*link == NULL){ 
     printf("added at beginning\n"); 
    } 
    else 
    { 
     while (*link) 
      link = &(*link)->next; 
     printf("added later\n"); 
    } 
    *link = newNode; 
    return 0; 
} 

... 
addNodeBottom(some_val, &head->next); 

...一些这种效果。虽然不是最大的区别，但可能会更好一点。如果列表没有为头部使用虚拟节点，并且当它添加到列表的开头与结束时不需要打印出来，则会更简单。在这种情况下，我们可以简单地做：

void addNodeBottom(int val, node **link){ 
    node *newNode = ...; 
    ... 
    while (*link) 
     link = &(*link)->next; 
    *link = newNode; 
} 
... 
addNodeBottom(some_val, &head); 

...它开始看起来相当漂亮，没有特殊情况来处理。如果绝对需要使用这种虚拟头并输出插入是否在列表的前面，也许它会帮助返回一个指向新节点的指针（例如，失败时为null），比如所以：

node* addNodeBottom(int val, node **link){ 
    node *newNode = ...; 
    ... 
    while (*link) 
     link = &(*link)->next; 
    *link = newNode; 
    return newNode; 
} 
... 
if (addNodeToBottom(some_val, &head->next) == head->next) 
    printf("added at beginning\n"); 
else 
    printf("added later\n"); 

为什么头为节点传递*头，而不是节点**头，如果我们 要内改变它，我们希望改变传播 之外的功能？

正如其他人所指出的，这是一种不同寻常的链表，其中head是某种虚拟节点或什么的。它在该功能中永远不会被修改，只有head->next，因此对head的更改会传播并导致外部副作用。

我从来没有理解这些类型的链接列表实现存储在像C和C++语言的虚拟节点的点，因为它们不减少特殊情况。他们只是浪费记忆，没有理由。对于不允许超过一种间接级别的语言来说，它们可能是有意义的，但在有指针的语言中是没有意义的。也许实现这个链表的人最初来自没有指针的语言背景，比如Java或Python等等。这种类型的虚拟节点链表可能不像那些不常见的解决方案，以避免语言不允许指向指针（或引用引用）的指针以避免某些if语句在这里和那里出现。