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

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

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

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

1> JaredPar..：

---

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

LinkedLists不需要连续的内存块,因此可以帮助减少内存碎片

LinkedLists支持有效删除元素(动态数组通常会强制移动所有元素).

LinkedLists支持有效添加元素(如果特定添加超过当前容量,动态数组可能导致重新分配+复制)

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

---

不要贬低你,但列出它的优点,并说当你想要这些优点时使用它并不具备足够的例子.这家伙要求现实世界的例子.

2> Michael Borg..：

---

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

---

基于数组的FIFO队列通常具有O(1)队列和出队操作.唯一一次需要成为O(n)的时候就是它的成长/调整大小.此外,基于阵列的队列与基于链表的队列相比具有一些优势,例如需要更少的空间而不会分割数据.

---

再说一次，例如C＃有一个Queue类。我宁愿使用它，不是吗？

3> Sam Saffron..：

---

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

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

4> leander..：

---

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

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

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

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

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

5> Emil H..：

---

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

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

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

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

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

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

6> Daniel Earwi..：

---

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

7> Brian..：

---

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