在什么情况下链接列表有用？ [英] Under what circumstances are linked lists useful?

问题描述

大多数时候，我看到人们尝试使用链表，在我看来，像一个穷人（或很穷）的选择。也许探索链表是或不是数据结构的好选择的情况是有用的。

理想情况下，答案将阐述使用的标准在选择数据结构时，哪些数据结构在特定情况下可能最有效。

编辑：我必须说，我不仅仅是数字，但质量的答案。我只能接受一个，但是还有两三个我不得不说，如果没有那么好的东西，那么这个值得接受。只有一对（特别是我最终接受的）指出了链表提供了真正的优势的情况。我认为史蒂夫·杰西普（Steve Jessop）值得一提，不仅提出了一个，而且提出了三个不同的答案，所有这一切都是令人印象深刻的。当然，即使它只是作为一个评论，而不是一个答案，我认为Neil的博客条目是非常值得阅读 - 不仅信息丰富，但相当有趣。

解决方案

它们对并发数据结构很有用。
（现在有一个非并发的实际使用示例，如果 @Neil 没有提到FORTRAN。;-)

例如， ConcurrentDictionary< TKey，TValue> 在.NET 4.0 RC中使用链接列表链接哈希到相同存储桶的项目。

的底层数据结构ConcurrentStack< T> 也是一个链表。

ConcurrentStack< T> 作为新的线程池，（本地的队列实现为堆栈，基本上）。 （另一个主要支持结构是 ConcurrentQueue< T> 。）

新的线程池依次提供基础对于新
的工作安排任务并行库。

所以他们肯定是有用的 - 一个链表目前是至少一个伟大的新技术的主要支持结构之一。

（单链接列表令人信服的无锁但在这些情况下不能等待 - 选择，因为主要操作可以使用单个 CAS （+ retries）
在现代GC-d环境（如Java和.NET）中， ABA问题可以很容易地避免
只是包装项目你添加新创建的节点，不要重用这些节点 - 让GC执行其工作。
ABA问题的页面还提供了一个无锁堆栈的实现，该堆栈实际上在具有保存项目的（GC-ed）节点的.Net（&Java）中。） / p>

修改：
@Neil：
实际上，你提到的关于FORTRAN的提醒我，同样的链接可以在.NET中找到最常用和滥用的数据结构：
简单的.NET通用字典< TKey，TValue>

不是一个，但是许多链表存储在数组中。

• 它避免了对插入/删除的许多小（de）分配。


• 初始加载哈希表很快，因为数组是顺序填充的（与CPU缓存一起播放非常好）。更不用说链接哈希表在内存方面是昂贵的，而这个技巧在x64上将指针大小减半。

本质上，许多链表存储在数组中。 （每个桶使用一个。）
可重用节点的空闲列表在它们之间交织（如果有删除）。
在start / on rehash上分配一个数组，链中的节点保存在其中。还有一个免费的指针 - 数组中的一个索引，跟随删除。 ;-)所以 - 相信与否 - FORTRAN技术依然存在。 （...和其他地方，而不是最常用的.NET数据结构之一; - ）。

Most times I see people try to use linked lists, it seems to me like a poor (or very poor) choice. Perhaps it would be useful to explore the circumstances under which a linked list is or is not a good choice of data structure.

Ideally, answers would expound on the criteria to use in selecting a data structure, and which data structures are likely to work best under specified circumstances.

Edit: I must say, I'm quite impressed by not only the number, but the quality of answers. I can only accept one, but there are two or three more I'd have to say would have been worth accepting if something a bit better hadn't been there. Only a couple (especially the one I ended up accepting) pointed to situations where a linked list provided a real advantage. I do think Steve Jessop deserves some sort of honorable mention for coming up with not just one, but three different answers, all of which I found quite impressive. Of course, even though it was posted only as a comment, not an answer, I think Neil's blog entry is well worth reading as well -- not only informative, but quite entertaining as well.

解决方案

They can be useful for concurrent data structures. (There is now a non-concurrent real-world usage sample below - that would not be there if @Neil hadn't mentioned FORTRAN. ;-)

For example, ConcurrentDictionary<TKey, TValue> in .NET 4.0 RC use linked lists to chain items that hash to the same bucket.

The underlying data structure for ConcurrentStack<T> is also a linked list.

ConcurrentStack<T> is one of the data structures that serve as the foundation for the new Thread Pool, (with the local "queues" implemented as stacks, essentially). (The other main supporting structure being ConcurrentQueue<T>.)

The new Thread Pool in turn provides the basis for the work scheduling of the new Task Parallel Library.

So they can certainly be useful - a linked list is currently serving as one of the main supporting structures of at least one great new technology.

(A singly-linked list makes a compelling lock-free - but not wait-free - choice in these cases, because main operations can be carried out with a single CAS (+retries). In a modern GC-d environment - such as Java and .NET - the ABA problem can easily be avoided. Just wrap items you add in freshly created nodes and do not reuse those nodes - let the GC do its work. The page on the ABA problem also provides the implementation of a lock-free stack - that actually works in .Net (&Java) with a (GC-ed) Node holding the items.)

Edit: @Neil: actually, what you mentioned about FORTRAN reminded me that the same kind of linked lists can be found in probably the most used and abused data structure in .NET: the plain .NET generic Dictionary<TKey, TValue>.

Not one, but many linked lists are stored in an array.

• It avoids doing many small (de)allocations on inserts/deletes.
• Initial loading of the hash table is pretty fast, because the array is filled sequentially (plays very nice with CPU cache).
• Not to mention that a chaining hash table is expensive in terms of memory - and this "trick" cuts "pointer sizes" in half on x64.

Essentially, many linked lists are stored in an array. (one for each bucket used.) A free list of reusable nodes is "interwoven" between them (if there were deletes). An array is allocated at the start/on rehash and nodes of chains are kept in it. There is also a free pointer - an index into the array - that follows deletes. ;-) So - believe it or not - the FORTRAN technique still lives on. (...and nowhere else, than in one of the most commonly used .NET data structures ;-).

这篇关于在什么情况下链接列表有用？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！