什么是应该使用链接列表的真实世界示例？

Question

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

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

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

Answer 1

链接列表与可比较的数据结构(如静态或动态扩展阵列)相比具有多个优势.

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

任何这些优点对程序非常有价值的地方(以及LinkedList的缺点可以忽略不计)都是使用LinkedList的地方.

Answer 2

一个真实的例子是FIFO队列.一个简单的基于数组的列表非常糟糕,因为你需要在一端添加并在另一端删除,其中一个操作将是带有基于数组的列表的O(n)(除非你添加额外的逻辑到使用起始和结束索引),而两者都是带有链表的O(1)而无需额外的努力.

Answer 3

链接列表(与哈希表配对)对LRU缓存非常有用.

每个Get都需要将一个节点撞到列表的前面,这是一个非常便宜的链接列表操作.

Answer 4

侵入式链表是游戏开发的有趣动物.例如,有一种常见的做法是拥有一个侵入性的单一或双重链接的"渲染"列表:

class Renderable /* or class Object, whatever */
{
  // ...
  Renderable * m_pNext;
  Renderable * m_pPrev; // or not, if singly-linked
  // ...
}

当Renderables进入和退出时,他们可以使用此列表注册自己 - 而不会导致任何内存分配.如果他们的渲染深度或优先级被更改,他们可以删除并重新插入自己,等等.

当需要渲染时,您需要做的就是找到列表的头部并压缩,调用适当的方法!

(当然,这个主题有很多变化,有多个单独的列表,等等.你不需要有一个侵入性列表来完成这项工作,我只是发现有趣的侵入性.)

Answer 5

堆栈和队列是链接列表的非常清晰的示例,但正如其他人已经提到的那样,我想添加一些其他示例:

DOM将节点存储为链接列表.一个简单的javascript示例,在任何语言中都是相同的:

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

我认为java开发人员在某些时候遇到过XML.

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

整个讨论对我来说似乎有点傻.链接列表是一种在任何地方都使用的基本数据结构.人们可能认为他/她没有碰到它们的唯一原因是你不必担心当今高级语言中数据结构的实现,但当然它们仍然存在.

Answer 6

它们始终出现在对象具有指向同一类型的另一个对象的属性的任何地方.在CLR中,由于InnerException属性,异常形成链表.

Answer 7

单链表的一些例子。

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

双链表的一些例子。

1. 浏览器的下一个和上一个按钮：URL 的链接列表。
2. 图像查看器的下一个和上一个按钮：图像的链接列表
3. Photoshop 的撤消和重做按钮，状态链接列表。

Answer 8

一个不可变的链表是一个非常有价值的结构,因为你可以"股权结构"与同尾其他列表.大多数函数式语言都包含一个不可变的链表类型作为其基本数据结构之一,并且这些类型在所有地方都使用.