data-structures - 普通链表、链表和双链表：何时以及为什么？

Question

在什么情况下我应该使用每种列表？各有什么优势？

Answer 1

普通清单：

按顺序存储每个项目，因此随机查找非常快（即我可以立即说“我想要第 657415671567 个元素，然后直接去找它，因为我们知道它的内存地址将比第一个项目大 657415671567）。这几乎没有或者没有存储内存开销。但是，它无法自动调整大小 - 您必须创建一个新数组，复制所有值，然后删除旧数组。当您需要从任何地方查找数据时，普通列表很有用在列表中，并且您知道您的列表不会超过特定大小。

链表：

每个项目都有对下一个项目的引用。这意味着有一些开销（存储对下一项的引用）。此外，由于它们不是按顺序存储的，因此您不能立即转到第 657415671567 个元素 - 您必须从头部（第一个元素）开始，然后获取它的引用以转到第二个元素，然后获取它的引用，到第三个，...然后得到它的参考到第 657415671566th，然后得到它的参考到第 657415671567th。这样，对于随机查找来说，效率非常低。但是，它允许您修改列表的长度。如果您的任务是按顺序遍历每个项目，那么它与普通列表的值大致相同。如果您需要更改列表的长度，它可能比普通列表更好。如果你知道第 566 个元素，并且你 重新寻找第 567 个，那么您需要做的就是按照对下一个的参考。但是，如果您知道第 567 个并且正在寻找第 566 个，则找到它的唯一方法是再次从第一个元素开始搜索。这就是双链表派上用场的地方......

双链表：

双链表存储对前一个元素的引用。这意味着您可以前后遍历列表。这在某些情况下可能非常有用（例如链接列表部分中给出的示例）。除此之外，它们与链接列表具有大部分相同的优点和缺点。

评论区的回答：

用作队列：
您必须考虑所有这些优点和缺点：您可以自信地说您的队列将具有最大大小吗？如果您的队列长度可能在 1 到 10000000000 个元素之间，那么普通列表只会浪费内存（甚至可能不够大）。在这种情况下，我会使用链接列表。但是，与其存储前后的索引，不如实际存储节点。

回顾：链表由“节点”组成，每个节点存储项目以及对下一个节点的引用

因此，您应该存储对第一个节点和最后一个节点的引用。因此，当您入队时，您将一个新节点粘贴到后端（通过将旧后端连接到新后端），并记住这个新后端节点。而且，当你出队时，你删除了前节点，并记住第二个作为新的“前节点”。这样，您就不必担心任何中间元素。因此，您可以忽略队列的长度（尽管如果您真的想要也可以存储它）

Answer 2

没有人提到我最喜欢的链表：带有指向最后一个元素的指针的循环链表。您可以在任一端获得恒定时间的插入和删除，以及恒定时间的破坏性追加。唯一的代价是空列表有点棘手。这是一个甜蜜的数据结构：列表、队列和堆栈合二为一。

Answer 3

使用单链表，您只能向前遍历。使用双向链表，您可以向后和向前遍历列表。一般来说，如果你要使用链表，真的没有充分的理由不使用双向链表。我在学校只使用过单链接。

Answer 4

双向链表的一个优点是删除指定指针的节点是 O(1)。