data-structures - 纯链表、链表和双链表 : When and Why?

Question

在什么情况下我应该使用每种列表？每一种都有什么优点？

Answer 1

普通 list :
顺序存储每个项目，因此随机查找非常快(即我可以立即说“我想要第 657415671567 个元素，然后直接找到它，因为我们知道它的内存地址将正好比第一个项目大 657415671567)。这几乎没有或者没有内存开销。但是，它无法自动调整大小 - 您必须创建一个新数组，复制所有值，然后删除旧值。当您需要从任何地方查找数据时，普通列表很有用在列表中，并且您知道您的列表不会超过特定大小。
链接列表:
每个项目都有对下一个项目的引用。这意味着有一些开销(存储对下一项的引用)。此外，因为它们不是按顺序存储的，所以您不能立即转到第 657415671567 个元素 - 您必须从头部(第一个元素)开始，然后获取其引用以转到第二个元素，然后获取其引用，到达第三个，...然后获取其引用以获取 657415671566th，然后获取其引用以获取 657415671567th。这样，对于随机查找来说效率很低。但是，它允许您修改列表的长度。如果您的任务是按顺序浏览每个项目，那么它与普通列表的值大致相同。如果您需要更改列表的长度，它可能比普通列表更好。如果您知道第 566 个元素，并且您正在寻找第 567 个元素，那么您需要做的就是遵循对下一个元素的引用。但是，如果您知道第 567 个并且您正在寻找第 566 个，那么找到它的唯一方法是再次从第一个元素开始搜索。这是双链表派上用场的地方......
双链表:
双链表存储对前一个元素的引用。这意味着您可以向后和向前遍历列表。这在某些情况下可能非常有用(例如链接列表部分中给出的示例)。除此之外，它们与链表具有大部分相同的优点和缺点。

来自评论区的回答:
用作队列:
您必须考虑所有这些优点和缺点:您能否自信地说您的队列将具有最大大小？如果您的队列可能有 1 到 10000000000 个元素的长度，那么普通列表只会浪费内存(然后甚至可能不够大)。在这种情况下，我会使用链表。但是，与其存储前后的索引，不如实际存储节点。
回顾:链表由“节点”组成，每个节点存储项以及对下一个节点的引用
所以你应该存储对第一个节点和最后一个节点的引用。因此，当您入队时，您将一个新节点粘贴到后部(通过将旧的后部连接到新的后部)，并记住这个新的后部节点。并且，当您出队时，您会移除前端节点，并记住第二个节点是新的“前端节点”。这样，您就不必担心任何中间元素。因此，您可以忽略队列的长度(尽管您也可以根据需要存储它)