C# 什么时候应该使用链表的真实世界例子是什么？

What are real world examples of when Linked Lists should be used?

提问by leora

Another programmer was mentioning that they haven't found a use case for using a linked list data structure in any professional software in his career. I couldn't think of any good examples off the top of my head. He is mostly a C# and Java developer

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

Can anyone give some examples where this was the correct data structure to solve a particular real world problem?

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

Related:What is a practical, real world example of the Linked List?

相关：什么是链接列表的实用、真实示例？

采纳答案by Michael Borgwardt

A real-world example would be a FIFO queue. An simple array-based list is pretty bad for that because you need to add at one end and remove at the other end, and one of those operations will be O(n) with an array-based list (unless you add extra logic to work with a start AND end index), while both are O(1) with a linked list without extra effort.

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

回答by daustin777

Stacks and Queues are examples of linked lists.

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

回答by Brian Mitchell

For problems where the number of maximal nodes are constrained to 100 or below or so, linked lists are a reasonable solution. The same can be true of things like bubble sort and other things that are thought to be sub-optimal.

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

回答by JaredPar

Linked Lists offer several advantages over comparable data structures such as static or dynamically expanding arrays.

与静态或动态扩展数组等类似数据结构相比，链表具有多种优势。

1. LinkedLists dose not require contiguous blocks of memory and therefore canhelp reduce memory fragmentation
2. LinkedLists support efficient removal of elements (dynamic arrays usually force a shift in all of the elements).
3. LinkedLists support efficient addition of elements (dynamic arrays can cause a re-allocation + copy if a particular add exceeds the current capacity)

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

Any place where these advantages would be significantly valuable to a program (and the disadvantages of a LinkedList were negligible) would be a place to use a LinkedList.

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

回答by billb

As daustin777 points out, linked lists are all around you and you may not even know it. But the practicality of the matter is that they allow for some pretty basic operations to be performed with relative ease and flexibility. For example, not to sort, just swap pointers around. Need to insert or remove at arbitrary places? Insert or remove your pointers within the list. Need to iterate forwards and backwards ... linked list. While not precisely a business example, I hope this clarifies it enough for you to apply it to your own real world business case.

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

回答by Brian

An immutablelinked list is a very valuable structure, since you can 'share structure' with other lists with the same tail. Most functional languages include an immutable linked list type as one of their fundamental data structures, and these types are used all over the place.

一个不可变的链表是一个非常有价值的结构，因为你可以“股权结构”与同尾其他列表。大多数函数式语言都包含一个不可变的链表类型作为它们的基本数据结构之一，并且这些类型被到处使用。

回答by cwap

Linked list pros:

链表优点：

• Dynamic storage nullifies fragmentation
• Fast insertion / removal
• Fast access to first element (and end if implemented bidirectional)
• Efficient memory usage

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

Linked list cons:

链表的缺点：

• Slow traversing

• 慢速穿越

Out of my head, I'd implement stacks, queues and messagepumps using linked lists. I'd also implement a datatree using multi-reference linked-lists for fast insertion / removal.

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

回答by Emil H

Stacks and queues are very clear examples of linked lists, but as other already have mentioned them I'd like to add a few other examples:

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

DOM stores nodes as linked lists. A simple javascript sample that is really the same in any language:

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

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

I would imagine that a java developer has come across XML at some point.

我想Java 开发人员在某个时候遇到过XML。

Trees are another good examples of linked lists, even though they aren't simple one dimensional ones. Someone who's done a lot of java development has probably come across TreeMaps and TreeSets.

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

The entire discussion seems a bit silly to me. Linked lists are a fundamental data structure that is used everywhere. The only reason that one might think that he/she hasn't come across them is that you don't really have to worry about the implementation of data structures in todays high level languages, but of course they're still there.

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

回答by Daniel Earwicker

They occur all the time, anywhere an object has a property that points to another object of the same type. In the CLR, exceptions form a linked list, due to the InnerExceptionproperty.

它们一直发生在任何一个对象具有指向另一个相同类型对象的属性的地方。在 CLR 中，由于InnerException属性的原因，异常形成了一个链表。

回答by Fire Lancer

As said already linked lists are very useful when you need to insert and delete elements.

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

For example to help debug memory management in my code I recently implemeneted a link list between all my refrence counted objects so that at the end of the program (when the refrences should all have hit zero and deleted the objects) I could see exactly what was still left, useually resulting in me being able to find a single object at the root of the problem.

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

CPython implements something similir with a massive linked list between nearly every when its built with debugging.

CPython 实现了一些类似的东西，它在几乎每个使用调试构建的时候都有一个巨大的链表。