删除双向链表中的链接
我正在用 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技术交流群](/public/img/jiaqun_03.jpg)
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
不会。如果您在垃圾收集语言中删除了对对象的最后一个引用,就会发生这种情况,但 C 不会这样工作。您需要手动释放已分配的每一位内存。
该代码看起来像您通常用于单链表或双链表的代码,假设它的值都不是指针。
因为它们是您还需要释放每个
current->value
(如果它们是指向指针的指针......)。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.
Since they are you need to free each
current->value
as well (and if they're pointers to pointers...).您发布的代码应该适用于单链表或双链表,但做了一些假设:
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:
Next
member isNULL
)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 toNULL
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'sPrev
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 nodehead->Next
instead ofhead
, and check whethercurrent
is nothead
rather than notNULL
. Then deal withhead
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...