链接列表在什么情况下有用？
大多数时候，我看到人们尝试使用链表，在我看来，像一个穷人（或非常贫穷）的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：
- 你只需要一个堆栈，所以一个单链表就足够了。
- 一切都已经分成节点。 如果单元格足够大以包含指针，则不存在侵入列表节点的分配开销。
- 一个向量或者deque会为每个块增加一个指针的开销。 这是非常重要的，因为当你第一次创build堆时，所有单元都是空闲的，所以这是一个前期成本。 在最坏的情况下，每个单元的内存需求翻倍。
双链表是定义哈希映射的顺序的一个很好的select，哈希映射也定义了元素的顺序（Java中的LinkedHashMap），特别是当按上一次访问sorting时：
- 更多的内存开销比关联的向量或双向（2个指针而不是1），但更好的插入/删除性能。
- 没有分配开销，因为无论如何您都需要一个哈希条目的节点。
- 引用的局部性与指针的向量或双向引擎相比没有其他问题，因为您必须以任何方式将每个对象拉入内存。
当然，你可以争论一下LRUcaching是否是一个好主意，相比之下更复杂和可调的，但是如果你打算有一个，这是一个相当不错的实现。 您不希望在每次读取访问时对vector或deque执行delete-from-middle-and-end-to-end-end，但是将节点移动到尾部通常没问题。
当你需要高速推送，popup和旋转时，它们非常有用，并且不介意O（n）索引。
单向链接列表是function性编程语言中常见的“列表”数据types的明显实现：
- 添加到头部是很快的，并且
(append (list x) (L))和(append (list y) (L))可以共享几乎所有的数据。 无需使用无写入的语言进行写入时复制。 function程序员知道如何利用这一点。 - 增加到尾巴是不幸的，但也会有其他的实现。
相比之下，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））以及相关的哈希映射条目（因此反向链接来自哈希映射的列表是必要的。）
