链表应该在哪些真实世界的情况下使用？

Question

有另一位程序员提到在他的职业生涯中没有发现过使用链表数据结构的实际应用场景。我也无法立即想出任何好的例子。他主要是C#和Java开发人员。

有没有人可以给出一些例子，说明这是解决特定实际问题的正确数据结构？

相关链接：链表的实际应用需要什么样的场景？

- mek

---

如果你真正阅读了这两个问题，它们并不是重复的。相关的问题想要一个链表的现实世界类比，而这个问题则想要使用链表的现实世界例子。 - mmcdole

Answer 1

链表相对于静态或动态扩展数组等可比较的数据结构具有以下几个优势：

1. 链表不需要连续的内存块，因此可以帮助减少内存碎片化
2. 链表支持高效的元素删除操作（动态数组通常需要移动所有元素）。
3. 链表支持高效的元素添加操作（如果特定添加超过了当前容量，则动态数组可能会导致重新分配和复制）。

当这些优点在程序中具有显著的价值（且链表的缺点可以忽略不计）时，就应当使用链表。

- JaredPar

---

删除元素通常需要先搜索它们，这是链表不擅长的操作 :) - cwap

@Meeh，是的，如果您还没有该元素，则必须进行搜索。这是其中一个缺点。但在某些情况下，您可能已经拥有要删除的节点，因此更有效率。 - JaredPar

不是要贬低你，但简单列出其优点并建议在想要这些优点时使用它，并不足以成为例子。那个人正在寻找实际的示例。 - core

@克里斯，@安德烈亚斯，这些不是具体的例子。我选择使用场景而非示例，因为它适用于更广泛的受众。我可以举一个过去我使用链表的例子，但这对任何人来说都不太相关。相反，我列出了原因。 - JaredPar

@Jared 如果不是秘密的话，我很想听听这个例子。有时候自己进行推断也是很好的。 - flq

Answer 2

一个现实世界的例子是FIFO队列。一个简单的基于数组的列表对此非常糟糕，因为你需要在一端添加，在另一端移除，而对于基于数组的列表中的其中一个操作来说，这将是O(n)的（除非你添加额外的逻辑来使用起始和结束索引），而使用链表，这两个操作都是O(1)的，无需额外努力。

- Michael Borgwardt

---

基于数组的先进先出队列通常具有 O(1) 的入队和出队操作。唯一需要 O(n) 操作的时候是当队列增长/调整大小时。此外，基于数组的队列相对于基于链表的队列具有一些优势，例如占用更少的空间和不会使数据碎片化。 - C. Dragon 76

我应该说有时候需要更少的空间。这取决于数组有多满以及链表的节点指针/索引有多大等因素。 - C. Dragon 76

嗯，我想可以保存起始和结束索引来使两个操作都是O(1)，但这需要额外的努力。会重新修改我的答案以反映这一点。 - Michael Borgwardt

再者，比如说C#有一个队列类。我宁愿使用那个，不是吗？ - flq

我同意@flq的观点--这确实不能反驳“为什么不只是使用队列”。我认为这并没有回答问题。 - alelom

Answer 3

对于游戏开发来说，侵入式链表是一种有趣的数据结构。例如，通常会使用一种侵入式单向或双向“渲染”列表：

class Renderable /* 或者 class Object，随意 */
{
  // ...
  Renderable * m_pNext;
  Renderable * m_pPrev; // 如果是单向链表则不需要
  // ...
}

当Renderable对象被创建或销毁时，它们可以在不引起任何内存分配的情况下向该列表注册自己。如果它们的渲染深度或优先级发生变化，它们可以将自己从列表中移除并重新插入。

当需要进行渲染时，你只需要找到列表的头部并快速遍历整个列表，调用相应的方法即可！

当然，这个主题有很多变化，比如使用多个独立的列表等等。而且你不需要使用侵入式链表来实现这个功能，我只是觉得侵入式链表很有趣。

- leander

---

我希望我可以收藏一个答案。 =] - strager

Answer 4

与哈希表配对使用的链表非常适用于LRU缓存。每次Get操作都需要将一个节点移到列表的最前面，这个操作用链表实现非常便宜。

- sambo99

Answer 5

单向链表的一些例子。

1. 任何应用程序（例如 Microsoft Word、Paint等）的撤销按钮：状态的链表。
2. GPS导航：地图数据的链表。从起点到终点的行进是遍历所有节点的例子。通过GPS进行重新路线规划是地图数据的添加和删除操作的示例。

双向链表的一些例子。

1. 浏览器的“前进”和“后退”按钮：URL的链表。
2. 图片查看器的“下一个”和“上一个”按钮：图像的链表。
3. Photoshop 的“撤销”和“重做”按钮：状态的链表。

- Merin Nakarmi

Answer 6

栈和队列是链表的明显例子，但是其他人已经提到了它们，我想再举几个例子：

DOM将节点存储为链表。以下是一个简单的JavaScript示例，实际上任何语言都一样：

for (var node = parent.firstChild; node != null; node = node.nextSibling) {
    // ..
}

我想象一下，Java开发人员在某个时候肯定遇到过XML。

树是链表的另一个很好的例子，尽管它们不是简单的一维链表。做过很多Java开发的人可能已经遇到了TreeMaps和TreeSets。

整个讨论对我来说有点傻。链表是一种基本的数据结构，在任何地方都被使用。唯一可能会认为自己没有遇到它们的原因是您不必真正担心今天高级语言中数据结构的实现，但当然它们仍然存在。

- Emil H

Answer 7

在任何一个对象具有指向同类型另一个对象的属性时，异常都可能发生。在CLR中，由于InnerException属性，异常形成了一个链接列表。

- Earwicker

Answer 8

不可变的链表是一种非常有价值的数据结构，因为可以与具有相同尾部的其他链表“共享结构”。大多数函数式编程语言都包括不可变的链表类型作为其基本数据结构之一，并且这些类型广泛应用于各个领域。

- Brian

---

使用数组也可以共享数据结构的部分，不是吗？ - Tobias Bergkvist

Answer 9

我写了一个BIOS扩展（基本上是一个用汇编语言编写的BIOS设备驱动程序），用于USB主机控制器。在汇编中实现高级似乎抽象的数据结构，如链表，并不像听起来那么困难。该控制器使用内存中的数据包链表处理键盘和磁盘的I/O请求。我在另一个链接列表中维护了一组自由数据包。执行I/O基本上涉及从自由列表的开头获取一个自由数据包，配置数据包，将数据包添加到设备列表中，并在I/O完成时将数据包重新添加到自由池的开头。对于移动这样的对象，链表非常快，特别是当对象很大时，因为实际上对象并不需要移动。只需要更新它们的指针即可。

基于数组的队列需要：

- 使用开始/结束索引指针，这很快但需要固定队列大小，因此当消费者队列已满时，生产者必须等待，并且如果有多个生产者，则在填充整个数据包时锁定队列。 - 每次插入/删除时移动队列中的所有元素，这对于大型对象而言速度较慢。

因此，链表是实现任意长度的先进先出队列的大型对象的好方法。

还要注意的另一件事是，对于小型对象或在从传统堆中分配对象而不是自定义自由池的情况下分配对象，数组可能更快，因为如果不经常进行复制，则复制并不真正缓慢，并且链表每次添加新元素时都需要从堆中重复分配，这很慢。

当然，您可能希望使用一些一次性测试代码模拟和测量特定场景以找到答案。我喜欢在链接列表和数组中运行几百万次循环，使用小型和大型对象，并计算它们在实际时间中花费的时间。有时您会感到惊讶。

- Matthew

Answer 10

作为 .Net 中可能是最好的实际示例，考虑 MultiCastDelegate。

使用这种方式实现的链表，其中列表链接方面直接嵌入到类型中而不是作为单独的容器，可以非常强大和高效。但它们具有各种权衡。
一个明显的问题是代码重复，您必须在每个类型中添加此逻辑。诸如通过扩展提供指针的基类之类的技术很混乱（没有泛型会导致强类型失效），通常从性能角度来看是不可接受的。
另一个问题是，您每种类型只能有一种实现。如果要将单向链式结构转换为双向链式结构，则必须在每个实例中插入额外的字段并更新所有相关代码。

- ShuggyCoUk