为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
当前回答
除了在列表中间进行添加和删除之外,我更喜欢链表,因为它们可以动态地增长和收缩。
其他回答
另一个很好的原因是链表非常适合高效的多线程实现。这样做的原因是,更改往往是局部的——只影响数据结构局部部分的插入和删除的一两个指针。所以,你可以让多个线程在同一个链表上工作。更重要的是,可以使用cas类型的操作创建无锁版本,并完全避免沉重的锁。
使用链表,迭代器还可以在进行修改时遍历列表。在修改没有冲突的乐观情况下,迭代器可以在没有争用的情况下继续。
对于数组,任何修改数组大小的更改都可能需要锁定数组的很大一部分,事实上,这是在整个数组上没有全局锁的情况下完成的,因此修改会停止全局事务。
数组Vs链表:
由于内存碎片,阵列内存分配有时会失败。 在数组中缓存更好,因为所有元素都分配了连续的内存空间。 编码比数组更复杂。 与数组不同,在链表上没有大小限制 在链表中插入/删除更快,在数组中访问更快。 从多线程的角度来看,链表更好。
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)。
编辑:澄清一下,我在这里指的是无序意义上的“合并”,而不是归并排序。也许"串联"这个词更合适。
由于数组本质上是静态的,因此所有的操作 比如内存分配发生在编译的时候 只有。因此处理器必须在运行时投入更少的精力。