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

Question

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

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

Answer 1

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

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

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