数组与链表

Question

为什么有人想在阵列上使用链表？

毫无疑问,对链接列表进行编码比使用数组要多一些工作,人们可能想知道什么是合理的额外工作.

我认为在链表中插入新元素是微不足道的,但它是数组中的一项重要工作.使用链表存储一组数据与将其存储在数组中是否还有其他优点？

这个问题不是一个重复这个问题,因为其他的问题是关于一个特定的Java类专门询问,而这个问题的关注与一般的数据结构.

Answer 1

另一个很好的理由是链表很适合高效的多线程实现.这样做的原因是更改往往是本地的 - 只影响一个或两个指针,以便在数据结构的本地化部分插入和删除.因此,您可以让许多线程在同一个链表上工作.更重要的是,可以使用CAS类型的操作创建无锁版本,并完全避免重量级锁定.

使用链表,迭代器也可以在发生修改时遍历列表.在乐观的情况下,修改不会发生冲突,迭代器可以继续而不会发生争用.

使用数组,任何修改数组大小的更改都可能需要锁定数组的大部分内容,事实上,如果没有跨整个数组的全局锁定就很少这样做,因此修改就会阻止这个世界事务.

Answer 2

• 在链表中存储不同大小的数据更容易.数组假定每个元素的大小完全相同.
• 正如您所提到的,链表更容易有机增长.数组的大小需要提前知道,或者在需要增长时重新创建.
• 改组链表只是改变指向什么的问题.混乱阵列更复杂和/或占用更多内存.
• 只要您的迭代都发生在"foreach"上下文中,您就不会在迭代中失去任何性能.

Answer 3

维基百科有很好的部分关于差异.

链接列表与数组相比有几个优点.元素可以无限期地插入到链表中,而数组最终会填满或需要调整大小,这是一项昂贵的操作,如果内存碎片化,甚至可能无法实现.类似地,从中移除许多元素的阵列可能变得浪费空或者需要变小.

另一方面,数组允许随机访问,而链表仅允许对元素进行顺序访问.事实上,单链表只能在一个方向上进行.这使链接列表不适合于快速查找元素的应用程序,例如heapsort.由于引用和数据高速缓存的位置,对阵列的顺序访问也比许多机器上的链接列表更快.链接列表几乎没有从缓存中获益.

链表的另一个缺点是引用所需的额外存储空间,这通常使得它们对于诸如字符或布尔值的小数据项列表而言是不实际的.它也可能很慢,并且对于每个新元素分别为每个新元素分配内存而浪费一个天真的分配器,通常使用内存池解决问题.

http://en.wikipedia.org/wiki/Linked_list

Answer 4

我将添加另一个 - 列表可以充当纯粹的功能数据结构.

例如,您可以拥有完全不同的列表,共享相同的结尾部分

a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)

即:

b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next  

无需将指向的数据复制a到b和中c.

这就是为什么它们在功能语言中如此受欢迎,它使用不可变变量 - prepend并且tail操作可以自由发生而不必复制原始数据 - 当您将数据视为不可变时非常重要的功能.

Answer 5

除了在列表中间插入更容易之外 - 从链表中间删除比从数组中删除更容易.

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

Answer 6

合并两个链表(尤其是两个双链表)比合并两个数组要快得多(假设合并具有破坏性).前者取O(1),后者取O(n).

编辑:澄清一下,我的意思是在无序的意义上"合并",而不是在合并排序中.也许"连接"可能是一个更好的词.

Answer 7

首先,在C++中,链接列表使用起来不应该比使用数组更麻烦.您可以将std :: list或boost指针列表用于链接列表.链表和数组的关键问题是指针和可怕的随机访问所需的额外空间.如果你,你应该使用链表

• 您不需要随机访问数据
• 您将添加/删除元素,尤其是在列表中间

Answer 8

ArrayList和LinkedList的广泛不受重视的争论是LinkedLists在调试时感到不舒服.维护开发人员花在理解程序上的时间,例如发现错误,增加和IMHO确实有时不能证明性能改进中的纳秒或企业应用程序中内存消耗的字节数.有时(当然,这取决于应用程序的类型),最好浪费几个字节,但有一个更易于维护或更容易理解的应用程序.

例如,在Java环境中并使用Eclipse调试器,调试ArrayList将显示一个非常易于理解的结构:

arrayList   ArrayList<String>
  elementData   Object[]
    [0] Object  "Foo"
    [1] Object  "Foo"
    [2] Object  "Foo"
    [3] Object  "Foo"
    [4] Object  "Foo"
    ...

另一方面,观看LinkedList的内容并查找特定对象会成为一个Expand-The-Tree点击噩梦,更不用说过滤掉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>

Answer 9

对我来说就是这样,

1. 访问

   • 链接列表仅允许对元素进行顺序访问.因此算法复杂度是O(n)的阶数
   • 数组允许随机访问其元素,因此复杂度为O(1)的顺序

2. 存储

   • 链接列表需要额外的存储空间以供参考.这使得它们对于诸如字符或布尔值的小数据项列表不实用.
   • 数组不需要额外的存储空间来指向下一个数据项.可以通过索引访问每个元素.

3. 尺寸

   • 链接列表的大小本质上是动态的.
   • 数组的大小仅限于声明.

4. 插入/缺失

   • 可以无限期地在链接列表中插入和删除元素.
   • 插入/删除数组中的值非常昂贵.它需要内存重新分配.

Answer 10

两件事情:

毫无疑问,对链接列表进行编码比使用数组要多一些工作,他想知道什么是合理的额外努力.

使用C++时,切勿对链表进行编码.只需使用STL.实施起来有多难,绝不应该成为选择一种数据结构而不是另一种数据结构的理由,因为大多数数据结构已在那里实现.

至于数组和链表之间的实际差异,对我来说最重要的是你如何计划使用该结构.我将使用术语向量,因为这是C++中可调整大小的数组的术语.

索引到链表是很慢的,因为你必须遍历列表才能到达给定的索引,而向量在内存中是连续的,你可以使用指针数学到达那里.

附加到链接列表的末尾或开头很容易,因为您只需要更新一个链接,在向量中您可能需要调整大小并复制内容.

从列表中删除项目很简单,因为您只需断开一对链接然后将它们重新连接在一起.从矢量中移除项目可以更快或更慢,具体取决于您是否关心订单.将最后一个项目交换到您想要删除的项目上方更快,而在向下移动所有内容后速度较慢但仍保留订购.

Answer 11

Eric Lippert最近发表了一篇关于阵列应该保守使用的原因之一.

Answer 12

快速插入和删除确实是链表的最佳参数.如果您的结构动态增长并且不需要对任何元素进行恒定时间访问(例如动态堆栈和队列),则链接列表是一个不错的选择.

Answer 13

这是一个快速的:删除项目更快.

Answer 14

除了从列表中间添加和删除之外,我更喜欢链接列表,因为它们可以动态增长和缩小.

Answer 15

链接列表在收集不断增长和缩小时特别有用.例如,很难想象尝试使用数组实现队列(添加到最后,从前面删除) - 你将花费所有时间来减少事情.另一方面,链接列表很简单.

Answer 16

没有人再编码自己的链表了.那太傻了.使用链表需要更多代码的前提是错误的.

如今,构建链表只是学生的练习,因此他们可以理解这个概念.相反,每个人都使用预建列表.在C++中,基于我们问题中的描述,这可能意味着一个stl vector(#include <vector>).

因此,选择链表与数组完全是关于权衡每个结构相对于应用需求的不同特征.克服额外的编程负担应该对决策没有任何影响.

Answer 17

这实际上是效率的问题,插入,移除或移动(不是简单地交换)链接列表中的元素的开销是最小的,即操作本身是O(1),对于数组而言是O(n).如果您在数据列表上运行很多,这可能会产生显着差异.您根据操作方式选择数据类型,并为您使用的算法选择最有效的数据类型.

Answer 18

在确切知道项目的确切数量以及按索引搜索有意义的地方,数组是有意义的.例如,如果我想在没有压缩的情况下在给定时刻存储视频输出的确切状态,我可能会使用大小为[1024] [768]的数组.这将为我提供我所需要的,并且列表在获得给定像素的值时要慢得多.在数组没有意义的地方,通常有比列表更好的数据类型来有效地处理数据.

Answer 19

数组链接列表:

1. 由于内存碎片,数组内存分配有时会失败.
2. 在数组中缓存更好,因为所有元素都分配了连续的内存空间.
3. 编码比数组更复杂.
4. 与数组不同,链接列表没有大小限制
5. 链接列表中的插入/删除速度更快,并且在数组中访问速度更快.
6. 从多线程的角度来看,链接列表更好.