删除双向链表中的链接

发布于 2024-12-10 08:22:52 字数 430 浏览 0 评论 0原文

我正在用 C 编写一个基于双向链表的代码。我错误地认为通过执行 free(head_node) 来删除头节点。我可以看到计算机随着运行的进行而变慢(这显然是由于内存泄漏)。我搜索了 stackoverflow 和其他网站,我通常遇到的用于删除链接列表的代码是这样的:

Node* current = head;
while( current != NULL ) {
Node* next = current->Next;
free( current );
current = next;
}

当我在代码中尝试此操作时,程序只是在 free 语句之后挂起,而没有返回到调用此语句的函数。上面的代码与双向链表相关吗?我的列表成员数据也包含很多指针。当我释放其中一个链接时,它是否会释放成员指向的所有数据?请用代码片段或书籍参考来建议和澄清。 谢谢。

I am writing a doubly linked list based code in C. I had wrongly assumed that deleting the head node by doing free(head_node). And I could see the computer slowing down as the run progressed (which apparently is due to memory leak). I searched stackoverflow and other sites and the code I usually came across for deleting a linked list was this :

Node* current = head;
while( current != NULL ) {
Node* next = current->Next;
free( current );
current = next;
}

When I tried this in my code, the program just hangs right there after the free statement without returning to the function that calls this one. Is the above code relevant for a doubly linked list? My list member data contains a lot of pointers too. When I do free on one of the links, does it free all data the members point to? Please suggest and clarify with code snippets or references to books.
Thank you.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

墨离汐 2024-12-17 08:22:52

当我释放其中一个链接时,它是否会释放成员指向的所有数据?

不会。如果您在垃圾收集语言中删除了对对象的最后一个引用,就会发生这种情况,但 C 不会这样工作。您需要手动释放已分配的每一位内存。

该代码看起来像您通常用于单链表或双链表的代码,假设它的值都不是指针。

我的列表成员数据也包含很多指针。

因为它们是您还需要释放每个current->value(如果它们是指向指针的指针......)。

When I do free on one of the links, does it free all data the members point to?

No. This is what would happen if you deleted the last reference to an object in a garbage-collected language, but C doesn't work like that. You need to manually free each bit of memory that you've allocated.

That code looks like what you'd usually use for a singly- or doubly-linked list, assuming none of its values were pointers.

My list member data contains a lot of pointers too.

Since they are you need to free each current->value as well (and if they're pointers to pointers...).

多情出卖 2024-12-17 08:22:52

您发布的代码应该适用于单链表或双链表,但做了一些假设:

  • 在释放节点之前不需要清理节点;这通常是一个错误的假设。
  • 列表的末尾标记有 NULL 指针(即最后一个节点的 Next 成员是 NULL

关于第一个假设:
由于您在节点中动态分配了数据,并且假设您在其他地方没有另一个指向它的指针供您稍后用来清理它,因此您需要在释放每个节点之前释放该数据。在 C 语言中,这不是为你做的;而是为你做的。一般规则是,如果您必须自己分配它,您也必须自己释放它。处理这个问题的一个明智的方法是编写一个函数来清理和释放节点,然后调用它,而不是仅仅调用 free() ;您的清理函数仍然会释放节点,但它会首先释放节点的数据。

关于第二个假设:
将最后一个节点的 Next 指针设置为 NULL 来标记结束是一种非常常见的做法,因为这样可以轻松判断您何时已经遍历完列表。对于双向链表,first 节点的 Prev 指针也是如此。但是,如果它是循环列表,则最后一个节点只会指向第一个节点 - 这会破坏您发布的代码。在这种情况下,您可以从节点 head->Next 而不是 head 开始,并检查 current 是否不是 head 而不是 NULL。然后在最后处理 head ,因为您最初跳过了它。

还有一件事:
确保释放列表后,不会让 head 指向无效(已释放)节点,然后再次尝试访问该列表...

The code you posted should work for singly or doubly linked lists, but makes some assumptions:

  • That there's no cleanup of the node to do before freeing it; this is often an incorrect assumption.
  • That the end of the list is marked with a NULL pointer (i.e. the last node's Next member is NULL)

Regarding the first assumption:
Since you have dynamically allocated data in your nodes, and presuming you don't have another pointer to it somewhere else that you'll use to clean it up later, you'll need to free that data before you free each node. In C, this is not done for you; the general rule is that if you had to allocate it yourself, you have to free it yourself too. A sensible way to deal with this is to write a function to clean up and free a node, and call that instead of just calling free(); your cleanup function would still free the node, but it would free the node's data first.

Regarding the second assumption:
It's a pretty common practice to set the last node's Next pointer to NULL to mark the end since it makes it easy to tell when you've walked all the way through the list. For a doubly linked list, the same goes for the first node's Prev pointer. However, if it's a circular list, the last node just points back to the first node instead -- and that would break the code you posted. In that situation, you'd start with the node head->Next instead of head, and check whether current is not head rather than not NULL. Then deal with head at the end, since you skipped it initially.

And one more thing:
Make sure after you're done freeing your list, that you don't leave head pointing to an invalid (already freed) node and then try to access the list again...

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文