使用雙指針在鏈接列表中插入節點

Question

我最近看到使用雙指針從單個鏈接列表中刪除節點的實現。除了使代碼更美觀之外，這個實現還是有效的。另外我怎樣才能實現一個類似的方法來插入一個節點到鏈表（不跟蹤以前的節點）。我真的很好奇，如果有任何更好的算法在那裏實現這一

Node* Delete(Node *head, int value) 
{ 
    Node **pp = &head; /* pointer to a pointer */ 
    Node *entry = head; 
    while (entry) 
    { 
     if (entry->value == value) 
     { 
      *pp = entry->next; 
     } 
     pp = &entry->next; 
     entry = entry->next; 
    } 
    return head; 
} 

Answer 1

除了使代碼更漂亮這是否實施 有什麼好處效率明智的。

沒有任何東西可以比較這一點，所以很難說，但這與從鏈表中刪除節點一樣高效。請注意，刪除函數名稱會更準確，因爲它實際上並未清除從列表中刪除的節點。

另外我怎樣才能實現類似的方法來插入一個節點 到鏈接列表（不跟蹤以前的節點）。

一種方法是展望未來。在您的刪除功能的格式之後的示例中最好顯示。

void insert(Node *head, int value) 
{ 
    Node *entry = head; 
    while (entry) 
    { 
     if (entry->next == NULL) 
     { 
      entry->next = new Node(NULL, value); 
      return; 
     } 
     else if (value < entry->next->value) 
     { 
      entry->next = new Node(entry->next, value); 
      return; 
     } 
     entry = entry->next; 
    } 
} 

Answer 2

爲了插入到僅存儲頭部的列表的背面，無尾（這將意味着一個小列表，其中線性時間插入是可接受的），可以通過將額外的指針間接消除做到這一點特殊情況：

簡易版（指向指針的指針到節點）

void List::push_back(int value) 
{ 
    // Point to the node link (pointer to pointer to node), 
    // not to the node. 
    Node** link = &head; 

    // While the link is not null, point to the next link. 
    while (*link) 
     link = &(*link)->next; 

    // Set the link to the new node. 
    *link = new Node(value, nullptr); 
} 

...這可以減少只是：

void List::push_back(int value) 
{ 
    Node** link = &head; 
    for (; *link; link = &(*link)->next) {} 
    *link = new Node(value, nullptr); 
} 

至於反對，說：

複雜的版本（指向節點）

void List::push_back(int value) 
{ 
    if (head) 
    { 
     // If the list is not empty, walk to the back and 
     // insert there. 
     Node* node = head; 
     while (node->next) 
      node = node->next; 
     node->next = new Node(value, nullptr); 
    } 
    else 
    { 
     // If the list is empty, set the head to the new node. 
     head = new Node(value, nullptr); 
    } 
} 

還是要公平，刪除註釋：

void List::push_back(int value) 
{ 
    if (head) 
    { 
     Node* node = head; 
     for (; node->next; node = node->next) {} 
     node->next = new Node(value, nullptr); 
    } 
    else 
     head = new Node(value, nullptr); 
} 

沒有特定的情況簡單版

主要的原因第一個版本沒有特殊情況下，空列表是因爲如果我們想象head爲空：

Node** link = &head; // pointer to pointer to null 
for (; *link; link = &(*link)->next) {} 
*link = new Node(value, nullptr); 

然後for循環條件是立即假的，然後我們分配新節點head。當我們使用指向指針的指針時，我們不必在循環外單獨檢查該情況。

插入排序

如果你想要做一個插入排序，而不是簡單地插入到後面，那麼這樣的：

void List::insert_sorted(int value) 
{ 
    Node** link = &head; 
    for (; *link && (*link)->value < value; link = &(*link)->next) {} 

    // New node will be inserted to the back of the list 
    // or before the first node whose value >= 'value'. 
    *link = new Node(value, *link); 
} 

性能

至於性能，不確保消除額外的分支會有很大的區別，但它確實使代碼更緊密並減少了複雜度。 Linus認爲這種風格是「好品味」的原因是因爲在C語言中，經常需要編寫鏈表列表邏輯，因爲它不是那麼容易，而且一定值得推廣鏈表，因爲我們在那裏沒有類模板，所以它就是方便地支持更小，更優雅，更不容易出錯的方式來編寫這些東西。再加上它表明你很好地理解指針。