從列表中刪除對象

typdef struct sNode 
{ 
    struct sNode* next; 
    myData data; 
} tNode;

我希望實現以下API：

bool removeNode(tNode* node) 
{ 
... // need to fix list and free node 
}

的問題是，我沒有以前的元素進行修改。有沒有解決它的某種魔法？

2011-05-13 user752716

不需要。您必須從列表的開頭遍歷才能找到前一個節點，效率相當低。這是單鏈表的問題。如果您需要快速，請使用雙向鏈表（每個節點具有下一個和以前的指針）。

2011-05-13 16:34:03 luqui

謝謝。但是在這種情況下，我也可以實現循環鏈表。在這種情況下，我不需要改變我的API或結構。然後我可以找到我的節點。我希望會有某種魔力 – user752716 2011-05-13 17:15:23

-1

是（幾乎） - 您可以將node->next的內容複製到node，然後刪除node->next。

僞代碼：

sNode* next = node->next; // see below for an important special case 
node->data = next->data; 
node->next = next->next; 
free(next);

我之所以說「幾乎」是，如果node沒有接班人，這並不工作。在這種情況下，你必須從頭開始遍歷列表。

此外，您必須考慮複製data的額外費用。

如果您經常通過指針刪除節點，您應該考慮一個單鏈表是否是正確的數據結構。例如，一個雙向鏈表沒有這個問題（但是每個節點確實有額外的額外開銷）。

2011-05-13 16:34:06 NPE

我不確定它會在節點是最後一項的情況下工作... – user752716 2011-05-13 16:36:24

@ user752716：它不會。我已經修改了答案。 – NPE 2011-05-13 16:37:10

我喜歡那種C風格的僞代碼：P – BlackBear 2011-05-13 16:52:03

您正在使用單個鏈接列表，如果要從列表中刪除節點，則應該從頭開始遍歷列表。所以，你需要改變你的API爲這樣的：

bool removeNode(tNode * head, tNode* node);

2011-05-13 16:54:42

回答