c - 链表 - 附加节点：循环还是指针？

Question

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

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

Answer 1

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

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

最后，这一切都与您需要执行的操作有关。如果您从不从列表末尾添加或删除或操作，则没有理由这样做。我建议分析您最常见操作的复杂性，并以此为基础做出决定。

Answer 2

取决于您需要多久找到最后一个节点，但一般来说最好有一个tail指针。

保持和更新指针的成本很低tail，但你必须记住更新它！如果您可以保持更新，那么它将使附加操作更快（O(1)而不是O(n)）。因此，如果您通常将元素添加到列表的末尾，那么您绝对应该创建并维护一个tail指针。

如果您有一个双向链表，其中每个元素都包含指向next 和 prev元素的指针，那么tail几乎普遍使用指针。

另一方面，如果这是一个排序列表，那么您将不会追加到末尾，因此tail永远不会使用指针。不过，保留指针是个好主意，以防万一您决定将来需要它。