链接列表在什么情况下有用?

大多数时候,我看到人们尝试使用链表,在我看来,像一个穷人(或非常贫穷)的select。 也许探索一个链表是不是数据结构的好select的情况是有用的。

理想情况下,答案将阐述在select数据结构时使用的标准,以及在特定情况下哪些数据结构可能工作得最好。

编辑:我必须说,不仅数量,而且答案的质量都令我印象深刻。 我只能接受一个,但如果事情好一些的话,还有两三个我不得不说的是值得接受的。 只有一对(尤其是我最终接受的那个)指出了链接列表提供了真正优势的情况。 我认为,史蒂夫·杰索普(Steve Jessop)应该得到某种荣誉提名,不仅提出了一个,而且提出了三个不同的答案,所有这些都给我留下了深刻的印象。 当然,即使它仅作为评论发布,并不是一个答案,但我认为尼尔的博客作品也非常值得一读 – 不仅仅是内容丰富,而且相当有趣。

它们可以用于并发数据结构。 (现在有一个非并发的真实世界使用示例 – 如果@Neil没有提到FORTRAN,则不会存在.-)

例如,.NET 4.0 RC中的ConcurrentDictionary<TKey, TValue>使用链表来链接散列到同一个存储桶的项目。

ConcurrentStack<T>的底层数据结构也是一个链表。

ConcurrentStack<T>是作为新线程池基础的数据结构之一(实质上将本地“队列”实现为堆栈)。 (另一个主要的支持结构是ConcurrentQueue<T> 。)

新的线程池反过来为新的任务并行库的工作调度提供了基础。

所以它们当然可以是有用的 – 链接列表目前是至less一个伟大的新技术的主要支持结构之一。

(一个单链表在这些情况下使用了一个非locking的无等待select,因为主操作可以用一个CAS (+重试)进行。在一个现代GC-d环境中 – 比如Java和.NET– ABA问题很容易避免,只需要把你添加到新创build的节点中的项目,不要重复使用这些节点 – 让GC工作,ABA问题的页面也提供了一个locking -免费的堆栈 – 实际上工作在.Net(&Java)与一个(GC版)节点持有的项目。)

编辑 :@Neil:实际上,你提到的FORTRAN提醒我,可能在.NET中使用最多的和被滥用的数据结构中find了同样的链表:普通的.NETgenericsDictionary<TKey, TValue>

不是一个,但许多链接列表存储在一个数组中。

  • 它避免了在插入/删除上做很多小的(de)分配。
  • 哈希表的初始加载非常快,因为数组是按顺序填充的(对CPU高速caching起到非常好的作用)。
  • 更不要说链接哈希表在内存方面是昂贵的 – 这个“技巧”在x64上将“指针大小”减半。

本质上,许多链接列表存储在一个数组中。 (每个桶使用一个)。可重用节点的空闲列表在它们之间“交织”(如果有删除的话)。 数组在开始/重新散列时被分配,并且链中的节点被保存在其中。 还有一个空闲的指针 – 数组的索引 – 在删除之后。 ;-)所以 – 不pipe你信不信 – FORTRAN技术依然存在。 (…和其他任何地方,比在最常用的.NET数据结构之一;-)。

链表是非常有用的,当你需要做大量的插入和删除,但没有太多的search,在任意(编译时未知)的长度的列表。

拆分和连接(双向链接)列表非常有效。

您还可以组合链表 – 例如,树结构可以实现为连接在一起的水平链表(同胞)的“垂直”链接列表(父/子关系)。

为这些目的使用基于数组的列表具有严格的限制:

  • 添加一个新项目意味着数组必须被重新分配(或者你必须分配更多的空间来满足未来的增长需要,并减less重新分配的次数)
  • 删除项目留下浪费的空间或需要重新分配
  • 在除了结尾之外的任何地方插入项目涉及(可能重新分配和)将大量数据复制到一个位置

链表是非常灵活的:通过修改一个指针,你可以做一个巨大的改变,在数组列表中相同的操作是非常低效的。

数组是通常比较链接列表的数据结构。

通常链接列表是非常有用的,当你需要对列表本身进行大量的修改时,数组的性能比直接访问列表要好。

下面是列表和arrays可以执行的操作列表,与相对运算成本(n =列表/数组长度)相比:

  • 添加一个元素:
    • 在列表中,您只需为新元素分配内存并redirect指针即可。 O(1)
    • 在数组上,你必须重新定位数组。 上)
  • 删除一个元素
    • 在列表中你只是redirect指针。 O(1)。
    • 在数组上,如果要移除的元素不是数组的第一个或最后一个元素,则花费O(n)时间重新定位数组; 否则只需将指针重新定位到数组的开始位置或减小数组长度即可
  • 获取已知位置的元素:
    • 在列表中,您必须将列表从第一个元素移动到特定位置中的元素。 最坏的情况:O(n)
    • 在数组上,您可以立即访问该元素。 O(1)

这是对这两种stream行和基本数据结构的非常低级别的比较,您可以看到,在您必须对列表进行大量修改(删除或添加元素)的情况下,列表执行得更好。 另一方面,当你必须直接访问数组的元素时,数组的性能要比列表要好。

从内存分配的angular度来看,列表更好,因为不需要将所有元素相邻。 另一方面,存储指向下一个(甚至前一个)元素的指针的开销很小。

了解这些差异对开发人员在其实现中的列表和数组之间进行select非常重要。

请注意,这是列表和数组的比较。 这里报告的问题有很好的解决scheme(例如:SkipLists,Dynamic Arrays等等)。 在这个答案中,我已经考虑了每个程序员应该知道的基本数据结构。

单链表对于单元分配器或对象池中的空闲列表是一个不错的select:

  1. 你只需要一个堆栈,所以一个单链表就足够了。
  2. 一切都已经分成节点。 如果单元格足够大以包含指针,则不存在侵入列表节点的分配开销。
  3. 一个向量或者deque会为每个块增加一个指针的开销。 这是非常重要的,因为当你第一次创build堆时,所有单元都是空闲的,所以这是一个前期成本。 在最坏的情况下,每个单元的内存需求翻倍。

双链表是定义哈希映射的顺序的一个很好的select,哈希映射也定义了元素的顺序(Java中的LinkedHashMap),特别是当按上一次访问sorting时:

  1. 更多的内存开销比关联的向量或双向(2个指针而不是1),但更好的插入/删除性能。
  2. 没有分配开销,因为无论如何您都需要一个哈希条目的节点。
  3. 引用的局部性与指针的向量或双向引擎相比没有其他问题,因为您必须以任何方式将每个对象拉入内存。

当然,你可以争论一下LRUcaching是否是一个好主意,相比之下更复杂和可调的,但是如果你打算有一个,这是一个相当不错的实现。 您不希望在每次读取访问时对vector或deque执行delete-from-middle-and-end-to-end-end,但是将节点移动到尾部通常没问题。

当你需要高速推送,popup和旋转时,它们非常有用,并且不介意O(n)索引。

单向链接列表是function性编程语言中常见的“列表”数据types的明显实现:

  1. 添加到头部是很快的,并且(append (list x) (L))(append (list y) (L))可以共享几乎所有的数据。 无需使用无写入的语言进行写入时复制。 function程序员知道如何利用这一点。
  2. 增加到尾巴是不幸的,但也会有其他的实现。

相比之下,vector或deque通常在任一端添加的速度都很慢,要求(至less在两个不同的附加的例子中)复制整个列表(向量)或索引块和数据块被附加到(deque)。 实际上,在大型列表中可能有些东西需要说明,因为某些原因需要在尾部添加,我没有充分了解函数式编程来判断。

根据我的经验,实施稀疏matrix和斐波那契堆。 链接列表让您更好地控制这些数据结构的整体结构。 虽然我不确定稀疏matrix是否最好使用链表来实现 – 可能有更好的方法,但它确实有助于学习在undergrad CS中使用链表的稀疏matrix的出入。

当你无法控制数据的存储位置时,链接列表是一个很自然的select,但是你仍然需要以某种方式从一个对象到另一个对象。

例如,在C ++中实现内存跟踪(新build/删除replace)时,您需要一些控制数据结构来跟踪哪些指针已被释放,您完全需要实现自己。 另一种方法是在每个数据块的开始处过度使用和添加一个链表。

因为你总是直觉地知道,你在列表中的哪个位置被调用时,你可以很容易地放弃O(1)中的内存。 在O(1)中,还添加了一个新的chunk。 在这种情况下很less需要走清单,所以O(n)的成本在这里不是问题(反正走一个结构是O(n))。

考虑一个链接列表在一个系统的领域驱动devise风格实现中可能非常有用,该系统包括与重复联动的部分。

一个想到的例子可能是如果你正在build模挂链。 如果你想知道任何特定环节的紧张程度,你的界面可能包含一个“明显”重量的吸气剂。 其实施将包括一个链接询问其下一个链接的明显的重量,然后加上自己的重量的结果。 这样,通过来自客户端的单个调用来评估到底部的整个长度。

作为一个像自然语言一样阅读的代码的支持者,我喜欢这种方式如何让程序员问一个链接链接多less重量。 它还保留了在链路实施的边界内计算这些孩子的属性的关注,消除了对连锁权重计算服务的需要“。

一个很好的使用链表的例子是列表元素非常大,即。 足够大以至于只有一两个可以同时装入CPUcaching。 在这一点上,像迭代向量或数组这样的连续块容器的优势已经或多或less被取消,并且如果许多插入和删除正在实时发生,则性能优势是可能的。

我曾经在C / C ++应用程序中使用链表(甚至是双链表)。 这之前的.NET甚至STL。

我现在可能不会在.NET语言中使用链表,因为所有需要的遍历代码都是通过Linq扩展方法为您提供的。

有两个互补的操作,在列表中很普通的O(1),而在其他数据结构的O(1)中很难实现 – 假定你需要维护元素的顺序,从任意位置移除和插入一个元素。

哈希映射显然可以在O(1)中插入和删除,但是不能按顺序迭代元素。

考虑到上述事实,哈希映射可以和一个链表相结合,创build一个漂亮的LRUcaching:一个映射,存储固定数量的键值对,并丢弃最近访问最less的键,为新的空间腾出空间。

哈希映射中的条目需要具有指向链接列表节点的指针。 当访问哈希映射时,链表节点与当前位置不关联,并移动到列表的头部(O(1),对于链接列表y!)。 当需要删除最近最less使用的元素时,需要删除列表尾部的元素(假设您保持指向尾部节点的O(1))以及相关的哈希映射条目(因此反向链接来自哈希映射的列表是必要的。)