爲鏈表添加​​元素時爲什麼不使用指針指針？

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語句在這裏和那裏出現。