数组与链表

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

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

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

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

1> Alex Miller..：

---

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

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

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

---

亚历克斯 - 这是一个我从未想过的有趣的考虑因素.非常好的答案.如果可以的话,我会两次投票.:-)

---

查看跳过列表(特别是Java 6中的ConcurrentSkipListMap),了解可以使用它的位置.CSLM是一个排序好的并发映射,具有出色的性能.远远超过同步的TreeMap.http://tech.puredanger.com/2007/10/03/skip-lists/

2> Ryan..：

---

在链表中存储不同大小的数据更容易.数组假定每个元素的大小完全相同.

正如您所提到的,链表更容易有机增长.数组的大小需要提前知道,或者在需要增长时重新创建.

改组链表只是改变指向什么的问题.混乱阵列更复杂和/或占用更多内存.

只要您的迭代都发生在"foreach"上下文中,您就不会在迭代中失去任何性能.

---

由于数据局部性,迭代链接列表会不会更慢？

---

我想说洗一个数组就不那么复杂了.

---

这个答案是不正确和误导的.(除非在声明数组时需要知道数组的大小)

---

如何处理不同尺寸的物品？链表要么使用带有下一个字段的固定结构(需要固定大小),要么存储指向汽车中数据的指针(可变大小OK).使用矢量两种方法都很简单.洗牌也一样.

---

@Rick,向量通常会分配他们需要的空间,这样他们就不需要在每次大小增加时分配新的空间.结果是,向量通常要少得多,而不是链接列表.

---

是的,我测试了这个.迭代稍慢,但不是很多.

---

@Hugh:我同意,它可能会占用更多内存,具体取决于阵列所持有的内容.

3> 小智..：

---

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

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

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

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

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

---

这是完美的答案.简洁地描述了两者的优缺点.

4> Brian..：

---

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

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

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操作可以自由发生而不必复制原始数据 - 当您将数据视为不可变时非常重要的功能.

---

另一个我永远不会想到的非常有趣的考虑因素.谢谢.

5> Tom Ritter..：

---

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

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

---

非常正确,大部分时间都是在搜索之后插入和删除,因此需要考虑时间复杂度的总和.

6> rampion..：

---

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

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

---

@Herms,但你可以合并两个已排序的链表而不分配任何额外的内存,只需遍历两个列表并适当地设置指针.合并两个数组通常至少需要一个额外的数组.

---

只有当你只是将一个列表附加到另一个列表时.如果您实际上正在合并两个已排序的列表,那么它将采用超过O(1)的日志.

---

Alexei Averchenko:连接两个列表,甚至合并排序两个排序列表,可以使用O(1)内存完成.连接两个数组必然需要O(n)内存,除非数组已经在内存中相邻.我认为你的目标是,n个元素的列表和n个元素的数组都需要O(n)内存,但链表的系数更高.

7> David Nehme..：

---

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

您不需要随机访问数据

您将添加/删除元素,尤其是在列表中间

8> mhaller..：

---

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

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

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

另一方面,观看LinkedList的内容并查找特定对象会成为一个Expand-The-Tree点击噩梦,更不用说过滤掉LinkedList内部所需的认知开销:

linkedList  LinkedList
    header  LinkedList$Entry
        element E
        next    LinkedList$Entry
            element E   "Foo"
            next    LinkedList$Entry
                element E   "Foo"
                next    LinkedList$Entry
                    element E   "Foo"
                    next    LinkedList$Entry
                    previous    LinkedList$Entry
                    ...
                previous    LinkedList$Entry
            previous    LinkedList$Entry
        previous    LinkedList$Entry

9> 小智..：

---

对我来说就是这样,

访问

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

数组允许随机访问其元素,因此复杂度为O(1)的顺序

存储

链接列表需要额外的存储空间以供参考.这使得它们对于诸如字符或布尔值的小数据项列表不实用.

数组不需要额外的存储空间来指向下一个数据项.可以通过索引访问每个元素.

尺寸

链接列表的大小本质上是动态的.

数组的大小仅限于声明.

插入/缺失

可以无限期地在链接列表中插入和删除元素.

插入/删除数组中的值非常昂贵.它需要内存重新分配.

10> bradtgmurray..：

---

两件事情:

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

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

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

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

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

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

11> Rik..：

---

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

---

不可否认,这是一篇好文章,但在链表中与阵列的讨论无关.

---

我建议Eric的文章很多都是相关的,因为它讨论了数组的缺点和列表的优点,不管列表实现如何.

12> Firas Assaad..：

---

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

13> itsmatt..：

---

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

14> Vasil..：

---

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

---

向量(=基本上是数组)也可以这样做,并且由于引用的局部性问题,它们的摊销成本通常小于列表的成本.

15> James Curran..：

---

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

---

您可以拥有一个基于阵列的队列,而不需要太多工作,但仍然快速/高效.你只需要跟踪哪个索引是"头",哪个索引是"尾巴".如果您需要固定大小的队列(例如,内核中的键盘缓冲区),这可以很好地工作.

---

如果你想在你最喜欢的算法参考中查找它,它被称为"循环缓冲区".

16> Joel Coehoor..：

---

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

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

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

---

Er..umm .. std :: vector是一个数组,而不是链表.标准的链表是std :: list.

17> Steve Baker..：

---

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

18> tloach..：

---

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

19> AKS..：

---

数组链接列表:

由于内存碎片,数组内存分配有时会失败.

在数组中缓存更好,因为所有元素都分配了连续的内存空间.

编码比数组更复杂.

与数组不同,链接列表没有大小限制

链接列表中的插入/删除速度更快,并且在数组中访问速度更快.

从多线程的角度来看,链接列表更好.

---

因此,它将为您提供讨论的总结视图.我喜欢这类答案,所以我不必一次又一次地阅读相同的解释.我为那些和我一样思考的人做了这件事.不同的人有不同的风格.没什么新鲜的.