gpt4 book ai didi

c - 链表 - 追加节点 : loop or pointer?

转载 作者:行者123 更新时间:2023-12-02 21:49:55 24 4
gpt4 key购买 nike

我正在写一个链表数据类型,因此我目前有一个标准的头指针,它引用第一个项目,然后每个元素的下一个指针指向下一个元素,这样最后一个元素的 next = NULL。

我只是好奇跟踪最后一个节点的优点/缺点或最佳实践是什么。我可以有一个“尾”指针,它始终指向最后一个节点,以便于追加,或者我可以从头指针开始遍历列表以在我想追加时找到最后一个节点。哪种方法更好?

最佳答案

存储尾部通常是个好主意。如果我们考虑在末尾添加项目的复杂性(如果这是您经常执行的操作),则搜索尾部的时间将是 O(n),如果存储它,则时间为 O(1)。

您可以考虑的另一个选择是使您的列表双向链接。这样当你想删除列表的末尾时,通过存储尾部你可以在 O(1) 时间内删除节点。但这会导致为列表的每个元素存储一个额外的指针(并不昂贵,但它加起来,对于内存受限的系统应该是一个考虑因素)。

说到底,都是你需要做的操作。如果您从不在列表末尾添加、删除或操作,则没有理由这样做。我建议分析最常见操作的复杂性,并据此做出决定。

关于c - 链表 - 追加节点 : loop or pointer?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18855432/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com