什么是应该使用链接列表的真实世界示例？
另一位程序员提到他们在职业生涯中没有找到在任何专业软件中使用链表数据结构的用例。 我想不出任何好的例子。 他主要是C＃和Java开发人员
任何人都可以提供一些例子来说明这是解决特定现实世界问题的正确数据结构吗？
相关： 链接列表的实际现实示例是什么？
一个真实的例子是FIFO队列。 一个简单的基于数组的列表非常糟糕，因为你需要在一端添加并在另一端删除，其中一个操作将是带有基于数组的列表的O（n）（除非你添加额外的逻辑到使用起始和结束索引），而两者都是带有链表的O（1）而无需额外的努力。
链接列表与可比较的数据结构（如静态或动态扩展arrays）相比具有多个优势。
- LinkedLists不需要连续的内存块，因此可以帮助减少内存碎片
- LinkedLists支持有效删除元素（动态数组通常会强制移动所有元素）。
- LinkedLists支持有效添加元素（如果特定添加超过当前容量，动态数组可能导致重新分配+复制）
任何这些优点对程序非常有价值的地方（以及LinkedList的缺点可以忽略不计）都是使用LinkedList的地方。
链接列表（ 与哈希表配对 ）对LRU缓存非常有用。
每个Get都需要将节点撞到列表的前面，这是一个链接列表非常便宜的操作。
侵入式链表是游戏开发的有趣动物。 例如，有一种常见的做法是拥有一个侵入式单链或双链“渲染”列表：
class Renderable / *或类Object，无论* /
{
// ...
可渲染* m_pNext;
可渲染* m_pPrev; //或不，如果单链接
// ...
}
当Renderables进入和退出时，他们可以使用此列表注册自己 – 而不会导致任何内存分配。 如果他们的渲染深度或优先级被更改，他们可以删除并重新插入自己，等等。
当需要渲染时，您需要做的就是找到列表的头部并压缩，调用适当的方法！
（当然，这个主题有很多变化，有多个单独的列表，等等。你不需要有一个侵入性列表来完成这项工作，我只是觉得有趣的侵入性。）
堆栈和队列是链接列表的非常清晰的示例，但正如其他人已经提到的那样，我想添加一些其他示例：
DOM将节点存储为链接列表。 一个简单的javascript示例，在任何语言中都是相同的：
for (var node = parent.firstChild; node != null; node = node.nextSibling) { // .. } 我想象一下java开发人员在某些时候遇到过XML。
树是链表的另一个很好的例子，即使它们不是简单的一维链表。 做过很多java开发的人可能遇到过TreeMaps和TreeSets。
整个讨论对我来说似乎有点傻。 链接列表是一种在任何地方都使用的基本数据结构。 人们可能认为他/她没有遇到过这种情况的唯一原因是你不必担心当今高级语言中数据结构的实现，但当然它们仍然存在。
它们始终发生在对象具有指向同一类型的另一个对象的属性的任何地方。 在CLR中，由于InnerException属性，exception形成链表。
不可变链表是一种非常有价值的结构，因为您可以与具有相同尾部的其他列表“共享结构”。 大多数函数式语言都包含一个不可变的链表类型作为其基本数据结构之一，并且这些类型在所有地方都使用。
也许.Net中最好的现实世界的例子可以考虑MultiCastDelegate 。
以这种方式实现的链接列表，其中列表链接方面直接支持该类型而不是作为单独的容器，可以非常强大和高效。 然而，他们有各种各样的权衡。
一个显而易见的是代码重复，你必须在每种类型中烘焙这个逻辑。 诸如扩展提供指针的基类之类的技术是混乱的（在没有generics的情况下丢失强类型）并且从性能的角度来看通常是不可接受的。
另一个是每种类型限制为一个实现。 如果不在每个实例中插入额外的字段并更新所有相关代码，则无法将单链接结构制作为双链接结构。
如上所述，当您需要插入和删除元素时，已经链接的列表非常有用。
例如，为了帮助在我的代码中调试内存管理，我最近在所有我的refrence计数对象之间实现了一个链接列表，以便在程序结束时（当refrences都应该为零并删除对象时）我可以看到究竟是什么仍然离开，有用导致我能够找到问题根源的单个对象。
CPython实现了一些similir，它几乎在每次构建调试时都有一个庞大的链表。
回答标签’数据结构’，在汇编等低级别，链表是存储其他数据结构的可变长度列表的理想方式。 维护列表长度或结束没有开销，并且不需要固定大小的列表项。 最后一个原因也适用于更高级别的语言。
我为USB主控制器编写了一个BIOS扩展（基本上是用于BIOS的设备驱动程序，用汇编编写）。 – 在汇编中实现像链接列表这样的高级看似抽象的数据结构并不像听起来那么难。 – 控制器使用主存储器中的链接列表来处理键盘和磁盘的I / O请求。 我在另一个链表中维护了一个免费数据包池。 执行I / O主要涉及从空闲列表的开头抓取一个空闲数据包，配置数据包，将数据包添加到设备列表，并在I / O完成时将数据包重新添加到空闲池的开头。 链接列表可以快速移动这样的对象，特别是当对象很大时，因为对象实际上不必移动。 只有他们的指针需要更新。
基于数组的队列需要：
- 使用开始/结束索引指针，这很快但需要修复队列的大小，以便生产者必须在消费者的队列已满时等待并在整个数据包被填满时锁定队列（如果有多个生产者）
- 插入/移除时移动队列中的所有元素，这对于大对象来说很慢
因此，链接列表是实现大型对象的任意长的先进先出队列的好方法。
另外需要注意的是，对于小对象或者从传统堆而不是自定义空闲池分配对象的情况，数组可以更快，因为如果不经常进行复制并且重复分配，则复制并不是那么慢每次添加新元素时，链表所需的堆很慢。
当然，您可能希望使用一些一次性测试代码来模拟和测量您的特定场景以找到答案。 我喜欢使用链表和数组运行循环几百万次，包含小型和大型对象，以及每次实时获取的时间。 有时你会感到惊讶。
正如daustin777指出的那样，链接列表就在你身边，你甚至可能都不知道。 但问题的实际意义在于它们允许以相对容易和灵活的方式执行一些非常基本的操作。 例如，不要排序，只需交换指针。 需要在任意位置插入或移除？ 在列表中插入或删除指针。 需要向前和向后迭代……链表。 虽然这不是一个商业榜样，但我希望这足以让您将其应用到您自己的真实世界商业案例中。
链接列表是Dancing Links的基本数据结构，它是用于有效实现算法X的技术， 算法X是一种回溯算法，可以找到NP完全精确覆盖问题的所有解决方案，许多难题本身可以自然地减少。
堆栈和队列是链接列表的示例。
对于最大节点数被约束为100或更低的问题，链表是合理的解决方案。 对于诸如冒泡排序和其他被认为是次优的事物，情况也是如此。
如果我可以用与其他人略有不同的方式回答这个问题，最近我一直在使用链接列表来组织音乐列表。 这些列表提供了一种通过艺术家，歌曲，专辑，甚至评级或歌曲长度来存储和分类音乐的绝佳方式。 我是一个双重链接列表，但我可以看到它也适用于单链表。 购物清单也适合，如果你像我的妈妈那样是强迫症，你可以很容易地把它整理成过道和冷冻食品！
如果我们包括堆栈和队列，那么明显的队列是打印队列或音乐播放列表（任何意义上的列表显然都很好）。
单链表的一些示例。
- 撤消任何应用程序的按钮，如Microsoft Word，Paint等：状态的链接列表。
- GPS导航：地图数据的链接列表。 从始发地到目的地的旅行是遍历所有节点的示例。 通过GPS重新路由是地图数据的添加和删除操作的示例。
双链表的一些例子。
- 浏览器的下一个和上一个按钮：Microsoft的URL链接列表
- 图像查看器的下一个和上一个按钮：图像的链接列表
- Photoshop的撤消和重做按钮，状态链接列表。
链接列表专业：
- 动态存储会使碎片无效
- 快速插入/移除
- 快速访问第一个元素（如果实现双向，则结束）
- 高效的内存使用
链表缺点：
- 慢速穿越
在我的脑海中，我将使用链接列表实现堆栈，队列和消息泵。 我还将使用多引用链接列表实现数据树，以便快速插入/删除。