List<T>是一个链表吗？

Question

System.Collections.Generic.List<T>是一种链表类型吗（不是LinkedList<T>类）？

链表是一种数据结构，由一组节点组成，它们共同表示一个序列。在最简单的形式下，每个节点由数据和对序列中下一个节点的引用（换句话说，链接）组成。

^{一个链表包含两个字段的节点：一个整数值和到下一个节点的链接。
最后一个节点链接到终止符号，用于标识列表的结束。}

wikipedia.org

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

- John Isaiah Carmona

---

@Adrian IftodeпјҡиҝҷдёӘй—®йўҳ并дёҚжҳҜеңЁй—®дҪ•ж—¶йҖүжӢ©List<T>иҖҢдёҚжҳҜLinkedList<T>гҖӮ - BoltClock

@BoltClock的独角兽，是的，我应该把它发布为评论。 - Adrian Iftode

Answer 1

不，List<T>是由数组支持的 - 它本质上是.NET 1.0中ArrayList的通用版本。从文档中可以看出：

“List<T>类是ArrayList类的通用等效类。它使用一个大小根据需要动态增加的数组来实现IList<T>通用接口。”

请注意，由于是由数组支持的，因此通过索引器访问的时间复杂度为O(1)，而链表的时间复杂度为O(N)。

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

- Jon Skeet

---

你的意思是它像数组一样在内存中被管理吗？但我怎么能添加数量不确定的对象呢？而且我可以从中删除一个项吗？ - John Isaiah Carmona

我的意思是它在内部有一个数组变量。该数组具有固定的大小（就像在.NET中所有数组一样），但当列表需要增长时，会创建一个新数组，并将现有元素复制到新数组中。同样，当你移除一个项时，它只是将其余元素复制到它们的新位置。 - Jon Skeet

Answer 2

List<T>，从技术角度来看，不是链表的一种类型。

如果你想在C#中使用链表：

• 可以使用内置的LinkedList<T>类型（双向链表）
• 或者自己创建一个实现（如果需要单向链表）- 这里有一个例子

- Dr.Kameleon

---

示例的链接已失效。 - Edward

@Edward 我已经更新了链接 - undefined