单链表（如何正确 remove/free 一个实体？）

Question

背景

我有以下代码

VOID FD_Remove(FDescs List, PVOID FileDesc) {
    while (List) {
        if (List->Sock == FileDesc) {
            List->Next = (FDescs) LocalAlloc(sizeof(Network::FDesc));
            if (List->Next != ERROR) {
                FDescs Element = List->Next;

                List->Sock = List->Next->Sock;
                List->Host = List->Next->Host;
                List->Path = List->Next->Path;

                List->Next = Element->Next;
                LocalFree(Element);
            }
        } List = List->Next;
    }
}

备注

基本上，当我在链表中创建一个新条目时。我将分配一个给定结构大小的新内存块并将其设置到列表的末尾，找到一个块的方式与我在这个 _Remove 函数中所做的相同。

但是，当我试图删除一个实体时。如上所示，我从列表中释放实体，并将当前实体设置为列表中的下一个条目。问题是， LocalFree 调用似乎并未实际将分配的内存设置回未分配的内存块。当我查看链表时，当前实体只是将其所有条目设置为 NULL (0).

假设我传递给 FD_Remove 的 FileDesc 是列表的最后一个条目。

FD_Remove(FDescList, 0x00000005);

因此我们可以假设具有 0x00000005 实体的内存现在已被释放。

现在我打电话给FD_Add(FDescList, FileDesc, 'whatever');

我只假设这些值会出现在链接列表中先前释放的实体中。

问题

问题是实体设置为 NULL 而不是释放内存，并且该函数将 FileDesc 和 'whatever' 数据添加到 NULL 之后的实体内存块而不是它里面。

问题

我的 FD_Remove 函数有什么问题导致了这个问题，我该如何改进我的函数来解决这个问题？

Answer 1

从链表中删除一个元素只需要更新周围的元素指针指向被删除的元素，然后释放该元素。您不需要分配或复制任何内容。

试试这个：

VOID FD_Remove(FDescs List, PVOID FileDesc) {
    FDescs Previous = NULL;
    while (List) {
        if (List->FDesc == FileDesc) {
            if (Previous)
                Previous->Next = List->Next;
            LocalFree(List);
            return;
        }
        Previous = List;
        List = List->Next;
    }
}

FD_Remove(FDescList, (PVOID)0x00000005);

但是，请注意被删除的元素是否是链表的 head。如果是这样，你也需要更新那个指针，上面的函数不能直接这样做。您将不得不做更多类似的事情：

VOID FD_Remove(FDescs *List, PVOID FileDesc) {
    if (!List) return;
    FDescs Element = *List, Previous = NULL;
    while (Element) {
        if (Element->FDesc == FileDesc) {
            if (*List == Element)
                *List = Element->Next;
            if (Previous)
                Previous->Next = Element->Next;
            LocalFree(Element);
            return;
        }
        Previous = Element;
        Element = Element->Next;
    }
}

FD_Remove(&FDescList, (PVOID)0x00000005);

单链表（如何正确 remove/free 一个实体？）

Singly Linked-List (How to properly remove/free an entity?)

c

winapi

singly-linked-list