c - 如何在C中仅释放链表中的单个节点？

Question

如何仅释放链表中的单个节点？下面的代码释放了整个链表，但我只想释放链表中的一个节点。

//Here's my code for delete

while(headPtr!=NULL)
{
    temp = headPtr;
    headPtr = headPtr->next;
    if(strcmp(temp->fname, stdfname) ==0 && 
       strcmp(temp->sname, stdsname) ==0  )
    {
        free(temp);
    }
}

Answer 1

你首先需要知道前一个节点。因此，您需要进行迭代，直到找到要删除的节点。在这个过程中你需要记住前一个节点。然后你需要连接上一个和下一个节点，从而“脱钩”你要删除的节点。

currentNode = headNode;
previousNode = NULL;
while (currentNode != NULL) {
    if (currentNode != nodeToDelete) {
        // Not the node we want to delete yet,
        // go on to next node.
        previousNode = currentNode;
        currentNode = currentNode->next;
        continue;
    }

    // We've now hit the node to delete and know the
    // previous node. Fix the structure.
    if (previousNode) {
        previousNode->next = nodeToDelete->next;
    } else {
        // No previous node means it's the head node.
        headNode = nodeToDelete->next;
    }

    // The node is now delinked from list. Delete it.
    free(nodeToDelete);
    // Stop the loop.
    break;
}

这在性能方面相当糟糕，这就是为什么有双链表。整个操作如下所示:

if (nodeToDelete->previous) {
    nodeToDelete->previous->next = nodeToDelete->next;
}
if (nodeToDelete->next) {
    nodeToDelete->next->previous = nodeToDelete->previous;
}
if (nodeToDelete == headNode) {
    headNode = nodeToDelete->next;
}
free(nodeToDelete);

如您所见，这里不需要迭代，因为每个节点都知道其上一个和下一个节点。

顺便说一句，要解决这些问题(它们非常基本)，它有助于在一张纸上绘制一个简短的链接列表。绘制方框，在每个方框中写入成员名称(如 previous 和 next)，并从这些成员到相应的其他方框绘制线条。然后考虑需要做什么才能删除该节点。它确实可以帮助您了解其工作原理。