简单,链接和双链表:何时以及为什么？

在什么情况下我应该使用每种列表？每个人有什么好处？

普通清单:

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

链接列表:

每个项目都有对下一个项目的引用.这意味着存在一些开销(将引用存储到下一个项目).另外,因为它们没有按顺序存储,所以你不能立即转到657415671567th元素 - 你必须从头开始(第一个元素),然后得到它的引用转到第二个,然后得到它的引用,到达第三个,...然后得到它的参考到657415671566th,然后得到它的参考到达657415671567th.这样,随机查找效率非常低.但是,它允许您修改列表的长度.如果您的任务是按顺序遍历每个项目,那么它与普通列表的值大致相同.如果您需要更改列表的长度,它可能比普通列表更好.如果您知道第566个元素,并且您正在寻找第567个元素,那么您需要做的就是遵循对下一个元素的引用.但是,如果您知道第567个并且您正在寻找第566个,那么找到它的唯一方法是再次从第1个元素开始搜索.这是Double Linked Lists派上用场的地方......

双链表:

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

评论部分回答:

要用作队列:
您必须考虑所有这些优点和缺点:您能否自信地说您的队列将具有最大大小？如果你的队列长度可以是1到10000000000个元素,那么普通列表只会浪费内存(然后甚至可能不够大).在那种情况下,我会使用链接列表.但是,您应该实际存储节点,而不是存储前后索引.

回顾:链表由"节点"组成,每个节点存储该项以及对下一个节点的引用

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