如何在不遍历链表的情况下计算链表中节点的数量？

Question

在面试中，我被问及如何在不遍历链表的情况下计算链表中节点的数量？是否有任何方法可以实现这一点？

- Amit Singh Tomar

---

插入时如何处理？ - jmj

理论上（虽然实际上并不是非常相关），假设您在程序中除了这个链表之外没有进行任何分配，那么您可以查询操作系统以获取现在和列表为空时的内存消耗差异。将其除以每个元素的大小将给出列表大小。显然，这并不像跟踪插入一样好。 - davin

我认为，如果您的节点不会改变，可以为每个节点分配一个索引。例如，对于第一个节点，在构造它时，给定int index = 1，当第二个节点构造时，index = 2，...。在此过程中，您可以使用O（1）复杂度执行任何作业（包括搜索、更改其位置等）。当然，当您查看最后一个节点的索引时，您可以知道有多少个节点。 - user478571

我忘了说，当然动态分配是不好的，因为你应该将它们存储在向量中。（我以为你懂C++，我已经回答过了） - user478571

你应该问面试官："我口袋里有多少硬币？" :) - csl

Answer 1

我能想到的唯一方法是添加一个节点数计数器，每次调用add或者insert方法时它就会自增，而在调用delete方法时则自减。由于这是一个链表，你不能假设所有节点都占据同一块内存（实际上，这种情况高度不太可能发生），所以你不能对内存的占用有任何的保证。

- Baltasarq

---

我想了解一件事，堆内存分配是否是非连续的？ - Amit Singh Tomar

你是指连续的吗？（抱歉，当我第一次读到你的评论时感到非常困惑。）关于堆，你甚至没有这个保证。一般来说，如果按顺序请求，大多数堆实现都会给你连续的块。然而，由于重新分配、碎片化、不按顺序请求内存的节点等原因，你不能假设它们在内存中是连续的。 - Baltasarq

抱歉我的错误，应该是contiguous而不是contagious，我明白你的意思了。 - Amit Singh Tomar

Answer 2

如果您使用类似malloc的动态分配方式，则除了每次插入/删除时更新计数器之外，没有其他方法。如果您没有使用动态分配，则可能尚未实现链表。

- Mike Kwan

Answer 3

这些其他人说的完全正确。在查看它们之前，你怎么知道某个东西中有多少项？

你需要维护一个计数，并在插入/删除时进行增量/减量。这是（最|唯一）可靠的方法。

- Lexx Koto

Answer 4

将计数器添加到您的结构体中，并使链表循环而不是单向。不要遍历整个列表，只需遍历初始节点的前一个节点即可。

- stevo

---

如何在仅有新节点链接到的节点引用的情况下，在列表中插入（或删除）一个节点？ - Michael Burr