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

Question

大多数时候,我看到人们试图使用链接列表,在我看来,这似乎是一个穷人(或非常差)的选择.也许有必要探讨链表是否是数据结构的良好选择的情况.

理想情况下,答案将阐述用于选择数据结构的标准,以及哪些数据结构在特定情况下可能最有效.

编辑:我必须说,我不仅对数字,而且对答案的质量印象深刻.我只能接受一个,但如果有一些更好的东西不存在,那么还有两三个我不得不说会值得接受.只有一对(特别是我最终接受的那个)指出了链表提供了真正优势的情况.我确实认为Steve Jessop不仅要提出一个,而且要提出三个不同的答案,值得一提,我发现这些答案令人印象深刻.当然,即使它只是作为评论发布而不是答案,我认为Neil的博客条目也值得一读 - 不仅信息丰富,而且非常有趣.

Answer 1

当您需要在任意(编译时未知)长度的列表上进行大量插入和删除但不进行太多搜索时,链接列表非常有用.

拆分和加入(双向链接)列表非常有效.

您还可以组合链接列表 - 例如,树结构可以实现为连接水平链接列表(兄弟姐妹)的"垂直"链接列表(父/子关系).

为此目的使用基于阵列的列表具有严重的局限性:

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

Answer 2

它们可用于并发数据结构.(现在下面有一个非并发的实际使用示例 - 如果@Neil没有提到FORTRAN 那就不会出现.;-)

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

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

ConcurrentStack<T>是作为新线程池基础的数据结构之一(本质上,"队列"实现为堆栈).(另一个主要支撑结构是ConcurrentQueue<T>.)

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

因此它们肯定是有用的 - 链表目前是至少一项伟大新技术的主要支持结构之一.

(在这些情况下,单个链接列表会产生令人信服的无锁 - 但不是无等待的选择,因为主要操作可以使用单个CAS(+重试)执行.在现代GC-d环境中 - 例如Java和.NET - 可以轻松避免ABA问题.只需将您添加的项目包装在新创建的节点中,不要重复使用这些节点 - 让GC完成其工作.关于ABA问题的页面也提供了锁定的实现 -自由堆栈 - 实际上在.Net(和Java)中使用(GC-ed)节点保存项目.)

编辑:@Neil:实际上,你提到的有关FORTRAN的内容提醒我,在.NET中最常使用和滥用的数据结构中可以找到相同类型的链表:普通的.NET泛型Dictionary<TKey, TValue>.

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

• 它避免了对插入/删除进行许多小(de)分配.
• 哈希表的初始加载速度非常快,因为数组是按顺序填充的(对于CPU缓存非常好).
• 更不用说链接哈希表在内存方面是昂贵的 - 并且这个"技巧"在x64上将"指针大小"减少了一半.

实质上,许多链表存储在一个数组中.(每个桶使用一个.)可重用节点的免费列表在它们之间"交织"(如果有删除).在start/on rehash中分配一个数组,并在其中保存链的节点.还有一个自由指针 - 数组的索引 - 在删除之后.;-)所以 - 信不信由你 - FORTRAN技术仍然存在.(...而在其他地方,比在最常用的.NET数据结构之一;-).

Answer 3

链接列表非常灵活:通过修改一个指针,您可以进行大规模更改,其中相同的操作在数组列表中效率非常低.

Answer 4

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

当您必须对列表本身进行大量修改时,通常链接列表非常有用,而阵列的性能优于直接元素访问上的列表.

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

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

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

从内存分配的角度来看,列表更好,因为不需要将所有元素放在彼此旁边.另一方面,存在将指针存储到下一个(甚至是前一个)元素的(小)开销.

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

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