为什么有人想要使用链表而不是数组?

毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。

我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?

这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。


当前回答

It's easier to store data of different sizes in a linked list. An array assumes every element is exactly the same size. As you mentioned, it's easier for a linked list to grow organically. An array's size needs to be known ahead of time, or re-created when it needs to grow. Shuffling a linked list is just a matter of changing what points to what. Shuffling an array is more complicated and/or takes more memory. As long as your iterations all happen in a "foreach" context, you don't lose any performance in iteration.

其他回答

由于数组本质上是静态的,因此所有的操作 比如内存分配发生在编译的时候 只有。因此处理器必须在运行时投入更少的精力。

除了插入到列表中间更容易之外——从链表中间删除也比从数组中删除容易得多。

但坦率地说,我从未使用过链表。每当我需要快速插入和删除时,我也需要快速查找,所以我使用HashSet或Dictionary。

使用链表的唯一原因是插入元素很容易(删除也很容易)。

缺点可能是指针占用大量空间。

关于编码就更难了: 通常你不需要代码链表(或只需要一次)他们包括在内 STL 如果你还是要做的话,它就不那么复杂了。

这里有一个快速的方法:移除物品更快。

首先,在c++中,使用链表应该不会比使用数组更麻烦。对于链表,可以使用std::list或boost指针列表。链表与数组的关键问题是指针需要额外的空间和糟糕的随机访问。你应该使用链表,如果你

你不需要随机访问数据 您将添加/删除元素,特别是列表中间的元素