平原，链接和双链表：何时和为什么？ [英] Plain, linked and double linked lists: When and Why?

问题描述

在什么情况下我应该使用各种列表？每个人的优点是什么？

In what situations should I use each kind of list? What are the advantages of each one?

推荐答案

平原清单：

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

Plain list:

Stores each item sequentially, so random lookup is extremely fast (i.e. I can instantly say "I want the 657415671567th element, and go straight to it, because we know its memory address will be exactly 657415671567 bigger than the first item). This has little or no memory overhead in storage. However, it has no way of automatically resizing - you have to create a new array, copy across all the values, and then delete the old one. Plain lists are useful when you need to lookup data from anywhere in the list, and you know that your list will not be longer than a certain size.

每个项目都有对下一个项目的引用，这意味着有一些开销（存储对下一个项目的引用），而且因为它们没有顺序存储，立即去657415671567元素 - 你h ave从头开始（第一个元素），然后得到它的参考到第二个，然后得到它的参考，得到第三个，然后得到它的参考获得到657415671566th，然后得到它的参考获得657415671567th。以这种方式，对于随机查找是非常低效的。但是，它允许您修改列表的长度。如果您的任务是顺序浏览每个项目，那么它与普通列表大致相同。如果您需要更改列表的长度，它可能比普通列表更好。如果你知道第566个元素，而你正在寻找第567个元素，那么您需要做的就是遵循下一个要素。但是，如果你知道第567号，你正在寻找第566号，找到它的唯一方法是再次从第一个元素开始搜索。双重链接列表可以方便地使用...

Each item has a reference to the next item. This means that there is some overhead (to store the reference to the next item). Also, because they're not stored sequentially, you can't immediately go to the 657415671567th element - you have to start at the head (1st element), and then get its reference to go to the 2nd, and then get its reference, to get to the third, ... and then get its reference to get to the 657415671566th, and then get its reference to get to the 657415671567th. In this way, it is very inefficient for random lookup. However, it allows you to modify the length of the list. If your task is to go through each item sequentially, then it's about the same value as a plain list. If you need to change the length of the list, it could be better than a plain list. If you know the 566th element, and you're looking for the 567th, then all you need to do is follow the reference to the next one. However, if you know the 567th and you're looking for the 566th, the only way to find it is to start searching from the 1st element again. This is where Double Linked Lists come in handy...

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

Double linked lists store a reference to the previous element. This means you can traverse the list backwards as well as forwards. This could be very useful in some situations (such as the example given in the Linked List section). Other than that, they have most of the same advantages and disadvantages as a Linked List.

用作队列：

您必须采取所有这些优点和缺点都考虑在内：您可以放心地说，您的队列将具有最大的大小吗？如果你的队列可以是1到1亿个元素的长度，那么一个简单的列表只会浪费内存（然后甚至可能不够大）。在这种情况下，我会使用链接列表。然而，不是存储前面和后面的索引，你应该实际上存储节点。

For use as a queue:
You'd have to take all of those advantages and disadvantages into account: Can you say with confidence that your queue will have a maximum size? If your queue could be anywhere from 1 to 10000000000 elements long, then a plain list will just waste memory (and then may not even be big enough). In that case, I'd go with a Linked List. However, rather than storing the index of the front and rear, you should actually store the node.

Recap：A linked list由节点组成，每个节点存储项目以及对下一个节点的引用

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

So you should store a reference to the first node, and the last node. Thus, when you enqueue, you stick a new node onto the rear (by linking the old rear one to the new rear one), and remember this new rear node. And, when you dequeue, you remove the front node, and remember the second one as the new "front node". That way, you don't have to worry about any of the middle elements. You can thus ignore the length of the queue (although you can store that too if you really want)

这篇关于平原，链接和双链表：何时和为什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！