c# - List<T> 是链表吗？

Question

是System.Collections.Generic.List<T>一种 linked list (不是 LinkedList<T> 类)？

A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the sequence.

^{A linked list whose nodes contain two fields: an integer value and a link to the next node.
The last node is linked to a terminator used to signify the end of the list.}

wikipedia.org

如果是，它是什么样的链表？

Answer 1

不， List<T> 由数组支持 - 它本质上是 ArrayList 的通用版本来自.NET 1.0。来自文档:

The List<T> class is the generic equivalent of the ArrayList class. It implements the IList<T> generic interface using an array whose size is dynamically increased as required.

请注意，由于由数组支持，它通过索引器的访问是 O(1) 而不是链表的 O(N)。

如果你想要一个链表，使用 LinkedList<T> .请注意，这是一个双向链表。我不相信 .NET 会公开单链表类型。