在什么情况下链表是有用的？

小开

我过去在 C/C + + 应用程序中使用过链表(甚至是双链表)。这是之前的事了。NET，甚至是 stl。

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

小开

当你需要高速推动、弹出和旋转，不要介意 O (n)索引时，它们是有用的。

小开

链表非常灵活: 通过修改一个指针，您可以进行大量的更改，在数组列表中，同样的操作将非常低效。

小开

最佳答案

它们对于并发数据结构非常有用。 (现在有一个非并发的现实世界使用样本如下-这将不会有，如果尼尔没有提到 FORTRAN。;-)

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

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

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

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

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

(在这些情况下，单链表是一个令人信服的没有锁-但不是无等待的-选择，因为主要操作可以用单个民安队(+ 重试)执行。在现代的 GC-d 环境中，比如 Java 和.NET，可以很容易地避免使用 ABA 的问题。只需将添加到新创建的节点中的项打包，不要重用这些节点——让 GC 完成它的工作。关于 ABA 问题的页面还提供了一个无锁堆栈的实现——它实际上可以在。Net (& Java) ，其中(GC-ed)节点保存项目。)

编辑 : @ Neil: 实际上，你提到的 FORTRAN 提醒了我，同样的链表可以在可能最常用和滥用的数据结构中找到。网址: 普通的.NET 通用 Dictionary<TKey, TValue>。

不是一个，而是许多链表存储在一个数组中。

它避免了对插入/删除执行许多小(反)分配。
哈希表的初始加载非常快，因为数组是按顺序填充的(非常适合 CPU 缓存)。
更不用说链式散列表在内存方面是昂贵的——这个“技巧”在 x64上将“指针大小”减少了一半。

实际上，许多链表存储在一个数组中(每个桶使用一个链表) 可重用节点的空闲列表在它们之间“交织”(如果有删除的话)。在 start/on rehash 中分配一个数组，链节点保存在其中。还有一个自由指针-数组的索引-在删除之后。因此——信不信由你—— FORTRAN 技术仍然存在。(... 没有其他地方，比在一个最常用的。NET 数据结构; ——。

小开

当您需要对任意(编译时未知)长度的列表执行大量插入和删除操作(但不要进行太多搜索)时，链表非常有用。

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

你也可以组合链表-例如，树结构可以实现为“垂直”链表(父/子关系)连接在一起的水平链表(兄弟姐妹)。

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

添加一个新项意味着数组必须重新分配(或者您必须分配比未来增长所需要的更多的空间，并减少重新分配的数量)
删除项目会留下浪费的空间或需要重新分配
除了末端，在任何地方插入项目都涉及(可能是重新分配和)将大量数据复制到一个位置

小开

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

您只需要一个堆栈，所以单链表就足够了。
所有东西都已经划分成节点了。只要单元格足够大，能够包含指针，就不会有侵入式列表节点的分配开销。
向量或 deque 会在每个块上施加一个指针的开销。这一点非常重要，因为在第一次创建堆时，所有单元格都是空闲的，所以这是一个预先开销。在最坏的情况下，它会使每个单元的内存需求增加一倍。

小开

双链表是定义散列表顺序的一个很好的选择，它也定义了元素的顺序(Java 中的 LinkedHashMap) ，特别是在最后一次访问时:

比关联的向量或 deque (2个指针而不是1个)更多的内存开销，但是更好的插入/删除性能。
没有分配开销，因为您无论如何都需要一个散列条目的节点。
与向量或指针集相比，访问局部性并不是额外的问题，因为无论如何你都必须将每个对象拉入内存。

当然，您可以争论一开始 LRU 缓存是否是一个好主意，与更复杂和可调优的东西相比，但是如果您将要拥有一个，那么这是一个相当不错的实现。您不希望在每次读访问时对向量或 deque 执行从中间删除并添加到末尾的操作，但是将节点移动到尾部通常是可行的。

小开

数组是通常与链表进行比较的数据结构。

通常，当需要对列表本身进行大量修改时，链表非常有用，而数组在直接元素访问方面比列表表现得更好。

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

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

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

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

了解这些差异对于开发人员在实现中选择列表和数组非常重要。

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

小开

单链表是函数式编程语言中常见的“列表”数据类型的明显实现:

添加到头部是快速的，并且 (append (list x) (L))和 (append (list y) (L))可以共享几乎所有的数据。不需要在没有写的语言中进行写上复制。函数式程序员知道如何利用这一点。
不幸的是，添加到尾部的过程很慢，但是其他任何实现也是如此。

相比之下，向量或 deque 在两端的添加通常比较慢，需要(至少在我的两个不同附加的例子中)获取整个列表(向量)的副本，或者索引块和数据块被附加到(deque)。实际上，对于大型列表中由于某种原因确实需要在尾部添加的 deque，这里可能有些话要说，我对函数式编程的了解还不够充分，无法做出判断。

小开

根据我的经验，实现稀疏矩阵和斐波那契堆。链表使您能够更好地控制这种数据结构的总体结构。虽然我不确定稀疏矩阵是否最好使用链表来实现——也许有更好的方法，但是它确实有助于在本科生 CS 中使用链表来学习稀疏矩阵的内部和外部

小开

当您无法控制数据的存储位置，但仍然需要以某种方式从一个对象转移到下一个对象时，链表是自然而然的选择之一。

例如，当在 C + + 中实现内存跟踪(新增/删除替换)时，您需要一些控制数据结构来跟踪哪些指针已被释放，您完全需要自己实现这些控制数据结构。另一种方法是过度分配并在每个数据块的开头添加一个链表。

因为当调用 delete 时，您总是立即知道您在列表中的位置，所以您可以轻松地放弃 O (1)中的内存。在 O (1)中还添加了一个刚刚被错配的新块。在这种情况下，很少需要遍历列表，因此 O (n)开销在这里不是问题(反正遍历结构是 O (n))。

小开

在列表中有两个互补的操作，它们通常是 O (1) ，而在其他数据结构中 O (1)很难实现——假设需要保持元素的顺序，从任意位置移除和插入元素。

散列映射显然可以在 O (1)中执行插入和删除操作，但是不能按顺序迭代元素。

鉴于上述事实，散列映射可以与链表结合，创建一个漂亮的 LRU 缓存: 一个映射，存储固定数量的键-值对，并删除最近访问的键，以腾出空间给新的。

哈希映射中的条目需要有指向链表节点的指针。当访问散列映射时，链表节点从当前位置解除链接并移动到列表的头部(O (1) ，为链表欢呼!).当需要删除最近使用最少的元素时，需要删除列表尾部的元素(同样是 O (1) ，假设您保留指向尾部节点的指针)以及相关的散列映射条目(因此从列表到散列映射的反向链接是必要的)

小开

考虑到链表可能在领域驱动设计风格的系统实现中非常有用，该系统包括与重复相互锁定的部分。

我想到的一个例子可能是，如果你要做一个挂链的模型。如果你想知道任何特定链接的张力是什么，你的界面可以包括一个“明显”重量的读取器。其实现将包括一个链接询问它的下一个链接的明显权重，然后添加自己的权重的结果。这样，从链的客户端发出的一个调用就可以计算整个长度到底部。

作为读起来像自然语言的代码的支持者，我喜欢这样的方式，程序员可以问一个链式链接它承载了多少重量。它还将计算这些子属性的关注保持在链接实现的边界内，从而消除了对链式权重计算服务的需求”。

小开

链表良好用法的一个例子是链表元素非常大的地方。大到只有一个或两个可以容纳在 CPU 缓存同时。此时，像向量或数组这样用于迭代的连续块容器所具有的优势或多或少已经失效，如果实时发生许多插入和删除操作，那么性能优势就可能成为可能。

小开

我发现，在网格和图像处理、物理引擎和光线跟踪等性能关键领域，使用链表最有用的一个例子是，与简单的替代方案相比，使用链表实际上提高了访问局部性，减少了堆分配，有时甚至减少了内存使用。

现在看来，这似乎是一个完全矛盾的做法，链表可以做到这一切，因为他们是臭名昭著的往往相反的做法，但他们有一个独特的属性，每个列表节点有一个固定的大小和对齐的要求，我们可以利用这一点，使他们能够连续存储和删除在固定时间的方式，可变大小的东西不能。

因此，让我们假设我们想要存储一个包含一百万个嵌套的可变长度子序列的可变长度序列。一个具体的例子是一个索引网格存储一百万个多边形(一些三角形，一些四边形，一些五边形，一些六边形等) ，有时多边形从网格的任何地方删除，有时多边形重建插入一个顶点到一个现有的多边形或删除一个。在这种情况下，如果我们存储一百万个微小的 std::vectors，那么我们最终将面临每个向量的堆分配，以及潜在的爆炸性内存使用。在一般情况下，一百万个小小的 SmallVectors可能不会遇到这样的问题，但是它们预先分配的缓冲区(不是单独分配的堆)仍然可能导致内存使用爆炸性增加。

这里的问题是，一百万个 std::vector实例将尝试存储一百万个可变长度的东西。可变长度的东西往往需要一个堆分配，因为它们不能非常有效地连续存储，如果它们没有将内容存储在堆的其他地方，它们就不能以常量时间(至少在没有非常复杂的分配器的情况下)移除。

相反，如果我们这样做:

struct FaceVertex
{
// Points to next vertex in polygon or -1
// if we're at the end of the polygon.
int next;
...
};


struct Polygon
{
// Points to first vertex in polygon.
int first_vertex;
...
};


struct Mesh
{
// Stores all the face vertices for all polygons.
std::vector<FaceVertex> fvs;


// Stores all the polygons.
std::vector<Polygon> polys;
};

那么我们就大大减少了堆分配和缓存丢失的数量。我们现在不需要为我们访问的每一个多边形都要求堆分配和潜在的强制缓存丢失，我们只需要当存储在整个网格中的两个向量中的一个超过了它们的容量(一个摊销的成本)时才需要堆分配。虽然从一个顶点到下一个顶点的跨度可能仍然会导致缓存丢失，但这仍然比每个单独的多边形存储一个单独的动态数组要少，因为节点是连续存储的，并且有可能在驱逐之前访问邻近的顶点(特别是考虑到许多多边形会同时添加它们所有的顶点，这使得大部分的多边形顶点是完全连续的)。

下面是另一个例子:

网格细胞被用来加速粒子与粒子的碰撞比如说，一千六百万个粒子在每一帧中移动。在粒子网格的例子中，使用链表，我们可以通过改变3个索引将一个粒子从一个网格单元移动到另一个单元格。从一个向量中擦除并推回到另一个向量可能要昂贵得多，并且会引入更多的堆分配。链表还将单元格的内存减少到32位。根据实现的不同，向量可以预先分配其动态数组到一个空向量可以占用32字节的位置。如果我们有大约一百万个网格单元，那就大不相同了。

... 这就是我发现链表最有用的地方，我特别发现“索引链表”的多样性很有用，因为32位索引将64位机器上链接的内存需求减半，这意味着节点是连续存储在一个数组中的。

我还经常将它们与索引空闲列表结合起来，以允许在任何地方进行常量删除和插入:

在这种情况下，如果节点已被删除，则 next索引指向下一个空闲索引，如果节点未被删除，则指向下一个使用的索引。

这是我最近发现的链表的头号用例。当我们想要存储一百万个平均长度为4个元素的可变子序列时(但是有时需要将元素移除并添加到其中一个子序列中) ，链表允许我们连续存储400万个链表节点，而不是100万个单独堆分配的容器: 一个巨大的向量，而不是一百万个小的向量。

小开

链表相对于连续集合的另一个优点是 链表可以将对象分配到任何适合的位置。
当连续内存中有成千上万个对象时，就很难重新分配内存——如果连续集合需要重新分配，在某些时候需要两倍或更多的内存。

使用链表，您可以进行小的分配，以填补未使用内存的“空白”。

小开

我知道这不是这个问题的直接答案，但是在 collections.deque中找到的名为 deque的抽象数据类型的 Python 标准实现使用了一个双向链表。