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

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

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

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


当前回答

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

其他回答

根据你的语言,可以考虑以下一些缺点和优点:

C编程语言:当使用链表(通常是通过结构指针)时,必须特别注意不要泄漏内存。正如前面提到的,链表很容易洗牌,因为我们所做的只是改变指针,但是我们会记得释放所有的东西吗?

Java: Java具有自动垃圾收集功能,因此内存泄漏不会成为问题,但是对于高级程序员来说,隐藏了链表的实现细节。从列表中间删除节点等方法的过程比该语言的一些用户所期望的要复杂得多。

合并两个链表(特别是两个双链表)比合并两个数组快得多(假设合并是破坏性的)。前者取O(1),后者取O(n)。

编辑:澄清一下,我在这里指的是无序意义上的“合并”,而不是归并排序。也许"串联"这个词更合适。

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

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

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

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.