如何删除 C++ 链表中的节点？

Question

到目前为止，我已将我的工作粘贴到此处： http://codepad.org/WhJuujRm

链表的概念让我感到困惑，所以我想我应该练习一下。我知道如何添加节点和编辑节点，但我不知道如何在我的特定场景中删除节点。

我的伪代码：

previous == now - 1;
if(stdid == now->getID());
previous->setNext(now->getNext);
delete now;
return;

我该如何实现？

Answer 1

我没有用你的符号，但我想你能明白这一点。

prev = NULL;
current = top;
while (current != NULL && !isfound(current)){
    prev = current;
    current = current->next;
}
// current point to the element you want to delete (if not NULL)
if(current != NULL) {
    if(previous != NULL) {
        previous->next = current->next;
    }
    else {
        top = current->next;
    }
    delete current;
}

Answer 2

这应该可以，但我还没有测试过。

有一种特殊情况，当第一个节点被删除时。第一次迭代时 previous 设置为 NULL，在这种情况下必须调整 top。

我没有使用 bottom，因为我不会这样做。如果你使用 bottom，还有第二种特殊情况，当你删除最后一个学生时。我会用 next 指针设置为 NULL 来标记列表的末尾，因为这消除了这种特殊情况。

bool deleteStudent(int id)
{
    student* now = top;
    student* prev = NULL;
    while(now != NULL) {
        student* next = now->getNext();
        if(id == now->getID()) {
            delete now;
            if(prev) prev->setNext(next);
            else top = next;
            return true;
        }
        prev = now;
        now = next;
    }
    return false;
}

Answer 3

从链表中删除元素的技巧在于更新最初将您带到该元素的指针。在您的列表案例中，它可能是 top（and/or 可能是 bottom），它可能是某个节点的 next。当您使用 cur 指针遍历列表搜索时，请保留一个 prev 指针，您在枚举时将其向前推进一步。假设你找到了受害者节点（如果你没有找到，就没什么可做的，哇！），prev 将处于两种状态之一：

它将是 NULL，在这种情况下 top 是指向您的受害者节点的指针，并且 top 必须更新，或者...
它将是一些指向节点的指针，在这种情况下，该节点的 next 成员需要更新以反映受害者节点的 next 成员值。

在两个案例中bottom可能也需要更新。在第一种情况下，如果列表只有一个节点并且您要删除它，则 bottom 将需要更改。即完成后你将有一个空列表。很容易判断，因为在分离 cur 并将 top 设置为 cur->next 之后 top 将为 NULL。对您来说更容易，因为您在列表容器中保留了一个 size 成员；如果它是 1，你知道 head 和 bottom

第二种情况，last节点可能是受害者节点。在这种情况下，必须更新 bottom 以反映列表的新结尾（巧合的是 prev，并且可能是 NULL，如果列表再次只有一个元素。如何判断受害者是否是列表中的最后一个节点？如果它的 next 成员为 NULL，则它必须是最后一个节点，并且 bottom 必须待更新。

像这样，基于ID搜索的删除功能

void deleteStudent(int id)
{
    student *cur = top, *prev = nullptr;
    while (cur && cur->getID() != id)
    {
        prev = cur;
        cur = cur->getNext();
    }

    // found a node?
    if (cur)
    {
        student *pNext = cur->getNext();

        // set new next pointer for prev, or new top
        if (prev)
            prev->setNext(pNext);
        else
            top = pNext;

        // update bottom if needed
        if (!pNext)
            bottom = prev;

        delete cur;
        --scnt;
    }
}

我留给你的其他删除选项和标准。

祝你好运。

如何删除 C++ 链表中的节点？

How can I delete a node in my linked list in C++?

c++

pointers

linked-list

nodes

delete-operator