为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
为什么有人想要使用链表而不是数组?
毫无疑问,编码一个链表比使用数组要多一些工作,人们可能会想知道如何才能证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的,但在数组中这是一个主要的任务。与将数据存储在数组中相比,使用链表存储一组数据还有其他优点吗?
这个问题不是这个问题的重复,因为另一个问题是专门问一个特定的Java类,而这个问题是关于一般数据结构的。
当前回答
除了插入和删除方便之外,链表的内存表示方式也不同于数组。对于链表中的元素数量没有限制,而在数组中,您必须指定元素的总数。 看看这篇文章。
其他回答
另一个很好的原因是链表非常适合高效的多线程实现。这样做的原因是,更改往往是局部的——只影响数据结构局部部分的插入和删除的一两个指针。所以,你可以让多个线程在同一个链表上工作。更重要的是,可以使用cas类型的操作创建无锁版本,并完全避免沉重的锁。
使用链表,迭代器还可以在进行修改时遍历列表。在修改没有冲突的乐观情况下,迭代器可以在没有争用的情况下继续。
对于数组,任何修改数组大小的更改都可能需要锁定数组的很大一部分,事实上,这是在整个数组上没有全局锁的情况下完成的,因此修改会停止全局事务。
除了插入到列表中间更容易之外——从链表中间删除也比从数组中删除容易得多。
但坦率地说,我从未使用过链表。每当我需要快速插入和删除时,我也需要快速查找,所以我使用HashSet或Dictionary。
A widely unappreciated argument for ArrayList and against LinkedList is that LinkedLists are uncomfortable while debugging. The time spent by maintenance developers to understand the program, e.g. to find bugs, increases and IMHO does sometimes not justify the nanoseconds in performance improvements or bytes in memory consumption in enterprise applicatons. Sometimes (well, of course it depends on the type of applications), it's better to waste a few bytes but have an application which is more maintainable or easier to understand.
例如,在Java环境中,使用Eclipse调试器,调试ArrayList将显示一个非常容易理解的结构:
arrayList ArrayList<String>
elementData Object[]
[0] Object "Foo"
[1] Object "Foo"
[2] Object "Foo"
[3] Object "Foo"
[4] Object "Foo"
...
另一方面,查看LinkedList的内容并找到特定的对象变成了一个展开树的噩梦,更不用说过滤LinkedList内部信息所需的认知开销:
linkedList LinkedList<String>
header LinkedList$Entry<E>
element E
next LinkedList$Entry<E>
element E "Foo"
next LinkedList$Entry<E>
element E "Foo"
next LinkedList$Entry<E>
element E "Foo"
next LinkedList$Entry<E>
previous LinkedList$Entry<E>
...
previous LinkedList$Entry<E>
previous LinkedList$Entry<E>
previous LinkedList$Entry<E>
Eric Lippert最近发表了一篇关于数组应该保守使用的原因之一的文章。
在数组中,您有权限在O(1)时间内访问任何元素。所以它适用于二进制搜索、快速排序等操作。链表则适合于插入删除,因为它在O(1)时间内。两者都有优点和缺点,选择一种而不是另一种归结为您想要实现什么。
—更大的问题是,我们能有一个两者的混合体吗?类似于python和perl实现的列表。