为什么有人想要使用链表而不是数组?
毫无疑问，编码一个链表比使用数组要多一些工作，人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的，但在数组中这是一个主要的任务。与将数据存储在数组中相比，使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复，因为另一个问题是专门问一个特定的Java类，而这个问题是关于一般数据结构的。
当前回答
合并两个链表(特别是两个双链表)比合并两个数组快得多(假设合并是破坏性的)。前者取O(1)，后者取O(n)。
编辑:澄清一下，我在这里指的是无序意义上的“合并”，而不是归并排序。也许"串联"这个词更合适。
其他回答
链表
它更可取的时候，它涉及到插入!基本上它所做的就是处理指针
1 -> 3 -> 4
插入(2)
1... 3... 4 ... 2
最后
1 -> 2 -> 3 -> 4
一个箭头指向3点，另一个箭头指向2点
简单!
但是来自Array
| | 1 | 3 | 4
插入(2) | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |
任何人都可以想象出其中的不同! 对于4个索引，我们执行3个步骤
如果数组长度是一百万呢?数组有效吗? 答案是否定的!：）
删除也是一样! 在链表中，我们可以简单地使用指针并将对象类中的元素和next置空! 但对于数组，我们需要执行shiftLeft()
希望有帮助!：）
链表比数组的维护开销更大，它还需要额外的内存存储，所有这些都是一致的。但是有一些事情是数组做不到的。在很多情况下，假设你想要一个长度为10^9的数组你无法得到它，因为必须有一个连续的内存位置。链表可能是这里的救世主。
假设你想用数据存储多个东西，那么它们可以很容易地扩展到链表中。
STL容器通常在后台有链表实现。
Arrays make sense where the exact number of items will be known, and where searching by index makes sense. For example, if I wanted to store the exact state of my video output at a given moment without compression I would probably use an array of size [1024][768]. This will provide me with exactly what I need, and a list would be much, much slower to get the value of a given pixel. In places where an array does not make sense there are generally better data types than a list to deal with data effectively.
快速插入和删除确实是链表的最佳参数。如果您的结构是动态增长的，并且不需要对任何元素进行固定时间的访问(例如动态堆栈和队列)，链表是一个很好的选择。
合并两个链表(特别是两个双链表)比合并两个数组快得多(假设合并是破坏性的)。前者取O(1)，后者取O(n)。
编辑:澄清一下，我在这里指的是无序意义上的“合并”，而不是归并排序。也许"串联"这个词更合适。
