26

另一位程序员提到，在他的职业生涯中，他们还没有找到在任何专业软件中使用链表数据结构的用例。我想不出任何好的例子。他主要是 C# 和 Java 开发人员

任何人都可以举一些例子，说明这是解决特定现实世界问题的正确数据结构吗？

相关： 链接列表的实际示例是什么？

4

18 回答 18

24

与静态或动态扩展数组等可比较的数据结构相比，链表提供了几个优势。

  1. LinkedLists 不需要连续的内存块，因此可以帮助减少内存碎片
  2. LinkedLists 支持有效地删除元素（动态数组通常会强制所有元素发生变化）。
  3. LinkedLists 支持元素的有效添加（如果特定添加超出当前容量，动态数组可能会导致重新分配 + 复制）

任何这些优点对程序非常有价值的地方（并且 LinkedList 的缺点可以忽略不计）都将是使用 LinkedList 的地方。

于 2009-03-21T22:22:24.907 回答
21

一个真实的例子是 FIFO 队列。一个简单的基于数组的列表对此非常不利，因为您需要在一端添加并在另一端删除，其中一个操作将是 O(n) 与基于数组的列表（除非您添加额外的逻辑使用开始和结束索引），而两者都是 O(1) 使用链表而不需要额外的努力。

于 2009-03-21T23:14:57.340 回答
17

侵入式链表是游戏开发的有趣野兽。例如，有一个侵入性的单链接或双链接“渲染”列表是一种常见的做法：

class Renderable /* 或 class Object，随便 */
{
  // ...
  可渲染 * m_pNext;
  可渲染 * m_pPrev; // 或者不是，如果是单链接的
  // ...
}

随着 Renderables 的出现和消失，它们可以在这个列表中注册自己——而不会导致任何内存分配。如果他们的渲染深度或优先级被改变，他们可以移除并重新插入自己，等等。

到了渲染的时候，你需要做的就是找到列表的头部并压缩，调用适当的方法！

（当然，这个主题有很多变体，有多个单独的列表等。而且你不需要有一个侵入性的列表来完成这项工作，我只是觉得侵入性的列表很有趣。）

于 2009-03-21T23:56:43.387 回答
15

链表（与散列表配对）对于LRU 缓存非常有用。

每个 Get 都需要将一个节点撞到列表的前面，这个操作对于链表来说真的很便宜。

于 2009-03-22T00:22:00.220 回答
8

单链表的一些例子。

  1. Microsoft Word、Paint 等任何应用程序的撤消按钮：状态链接列表。
  2. GPS 导航：地图数据的链接列表。从起点到终点的旅行是遍历所有节点的示例。GPS 重新路由是地图数据的添加和删除操作的一个示例。

双链表的一些例子。

  1. 浏览器的下一个和上一个按钮：一个链接的 URL 列表。
  2. 图像查看器的下一个和上一个按钮：图像的链接列表
  3. Photoshop 的撤消和重做按钮，状态链接列表。
于 2016-09-02T22:39:11.633 回答
7

堆栈和队列是链表的非常清楚的例子，但正如其他人已经提到的那样，我想添加一些其他例子：

DOM 将节点存储为链表。一个在任何语言中都完全相同的简单 javascript 示例：

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

我会想象一个 java 开发人员在某个时候遇到过 XML。

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

整个讨论对我来说似乎有点愚蠢。链表是一种无处不在的基本数据结构。人们可能认为他/她没有遇到过它们的唯一原因是您实际上不必担心当今高级语言中数据结构的实现，但是它们当然仍然存在。

于 2009-03-21T22:55:35.590 回答
6

它们一直在发生，只要对象具有指向同一类型的另一个对象的属性。在 CLR 中，异常形成一个链表，由于InnerException属性。

于 2009-03-21T23:02:56.027 回答
5

不可变链表是一种非常有价值的结构，因为您可以与其他具有相同尾部的列表“共享结构”。大多数函数式语言都包含一个不可变的链表类型作为它们的基本数据结构之一，并且这些类型在所有地方都被使用。

于 2009-03-21T22:26:37.987 回答
4

我为 USB 主机控制器编写了一个 BIOS 扩展（基本上是 BIOS 的设备驱动程序，用汇编语言编写）。-- 在汇编中实现像链表这样的高级看似抽象的数据结构并不像听起来那么难。-- 控制器使用主存储器中的数据包链表处理键盘和磁盘的 I/O 请求。我在另一个链表中维护了一个免费数据包池。执行 I/O 基本上包括从空闲列表的开头抓取一个空闲数据包，配置数据包，将数据包添加到设备列表中，并在 I/O 完成时将数据包重新添加到空闲池的开头。链表对于像这样在对象周围移动非常快，尤其是当对象很大时，因为对象实际上不必移动。只有它们的指针需要更新。

基于数组的队列需要：

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

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

另一件需要注意的事情是，对于小对象或从传统堆而不是自定义空闲池分配对象的地方，数组可以更快，因为如果不经常进行复制并不会那么慢，并且重复分配每次添加新元素时，链表都需要从堆中获取速度很慢。

当然，您可能希望使用一些一次性测试代码来模拟和测量您的特定场景以找到答案。我喜欢用链表和数组、大小对象运行几百万次循环，并计算每个循环需要多长时间。有时你会感到惊讶。

于 2010-01-28T16:22:11.963 回答
3

作为 .Net 中最好的现实世界示例，请考虑MultiCastDelegate。

以这种方式实现的链接列表，其中列表链接方面直接支持到类型而不是作为单独的容器，可以非常强大和高效。然而，它们伴随着各种权衡。
一个明显的问题是代码重复，您必须在每种类型中烘焙此逻辑。诸如扩展提供指针的基类之类的技术很混乱（如果没有泛型，您将失去强类型），并且从性能的角度来看通常是不可接受的。
另一个是您仅限于每种类型的一个实现。如果不在每个实例中插入一个额外的字段并更新所有相关代码，就无法将单链接结构变成双链接结构。

于 2009-03-22T20:30:01.113 回答
2

如前所述，当您需要插入和删除元素时，链表非常有用。

例如，为了帮助在我的代码中调试内存管理，我最近在我的所有引用计数对象之间实现了一个链接列表，以便在程序结束时（当引用应该全部达到零并删除对象时）我可以确切地看到是什么仍然存在，通常导致我能够找到问题根源的单个对象。

CPython 实现了类似的东西，它几乎在每一个构建时都带有一个庞大的链表，并带有调试功能。

于 2009-03-21T23:55:21.487 回答
2

响应标签“数据结构”，在汇编等低级别，链表是存储其他数据结构的可变长度列表的理想方式。维护列表长度或结尾没有开销，也不需要固定大小的列表项。最后一个原因也适用于高级语言。

于 2009-03-22T07:52:14.350 回答
2

链表是Dancing Links的基本数据结构，它是用于有效实现算法 X的技术，它是一种回溯算法，用于找到 NP 完全精确覆盖问题的所有解决方案，许多难题自然可以简化为。

于 2010-03-12T08:54:09.787 回答
1

正如 daustin777 指出的那样，链表就在你身边，你甚至可能都不知道。但问题的实用性在于它们允许以相对容易和灵活的方式执行一些非常基本的操作。例如，不排序，只是交换指针。需要在任意位置插入或移除？在列表中插入或删除您的指针。需要向前和向后迭代...链表。虽然不完全是一个商业示例，但我希望这足以澄清它，以便您将其应用到您自己的真实世界商业案例中。

于 2009-03-21T22:24:36.040 回答
1

如果我可以以与其他人略有不同的方式回答这个问题，那么最近我一直在使用链接列表来组织音乐列表。这些列表提供了一种按艺术家、歌曲、专辑甚至收视率或歌曲长度存储和排序音乐的绝佳方式。我的是一个双向链表，但我可以看到它也适用于单链表。购物清单也很合适，如果你像我妈妈一样有强迫症，你可以很容易地把它整理成过道和最后的冷冻食品！

如果我们包括堆栈和队列，那么队列显然是打印队列或音乐播放列表（显然任何意义上的列表都很好）。

于 2015-06-25T05:02:16.623 回答
0

堆栈和队列是链表的示例。

于 2009-03-21T22:21:05.270 回答
0

对于最大节点数限制在 100 或以下的问题，链表是一个合理的解决方案。冒泡排序和其他被认为是次优的事情也是如此。

于 2009-03-21T22:21:59.010 回答
-1

链表优点：

  • 动态存储消除碎片
  • 快速插入/移除
  • 快速访问第一个元素（如果双向实现则结束）
  • 有效的内存使用

链表缺点：

  • 慢速穿越

在我的脑海中，我会使用链表来实现堆栈、队列和消息泵。我还将使用多引用链接列表实现数据树，以实现快速插入/删除。

于 2009-03-21T22:47:33.910 回答