C# 常用集合(一):数组、List、LinkedList、Stack、Queue
先了解:复杂度和缓存
时间复杂度描述操作耗时随元素数量 n 增长的趋势:
| 记法 | 含义 | 例子 |
|---|---|---|
| O(1) | 与 n 无关 | 数组按下标访问 |
| O(log n) | n 翻倍只多一步 | 二分查找、平衡树 |
| O(n) | 与 n 成正比 | 遍历、在数组中间插入 |
但复杂度不是全部。现代 CPU 读内存时会把相邻的一整块数据加载到缓存中,所以连续存储的数据遍历起来非常快,而分散在堆上各处的数据(比如链表节点)每访问一个都可能要重新从内存读取,慢得多。这也是下面”链表理论上更快、实际却更慢”的原因。
数组(T[])
原理
数组是一块连续的内存,所有元素大小相同、紧挨着存放:
地址: 1000 1004 1008 1012 1016 ┌──────┬──────┬──────┬──────┬──────┐int[] │ 10 │ 20 │ 30 │ 40 │ 50 │ └──────┴──────┴──────┴──────┴──────┘ [0] [1] [2] [3] [4]访问 arr[i] 时,地址 = 起始地址 + i × 元素大小,一步就能算出来,所以按下标访问是 O(1)。
- 长度固定:创建后不能改变大小,要”扩容”只能新建一个更大的数组,再把数据复制过去。
- 数组本身是引用类型,总在堆上。值类型数组(如
Vector3[])的元素直接存在数组内存里;引用类型数组存的是一个个引用,对象本身散落在堆的其他地方。
多维数组与交错数组
int[,] grid = new int[10, 10]; // 多维数组:一整块连续内存int[][] jagged = new int[10][]; // 交错数组:数组的数组,每行可以不同长度在 .NET 中,交错数组的访问通常比多维数组更快,因为运行时对一维数组有专门的优化。性能敏感的地方,也可以用一维数组模拟二维:arr[y * width + x]。
数组协变的坑
object[] arr = new string[3]; // 编译通过:引用类型数组支持协变arr[0] = 1; // 运行时抛出 ArrayTypeMismatchException为了保证类型安全,每次往引用类型数组写入元素时,运行时都要检查类型,这也带来一点额外开销。
List<T>
原理:会自动扩容的数组
List<T> 内部就是一个数组,加上一个记录元素个数的字段:
// 简化后的结构class List<T>{ T[] _items; // 实际存储 int _size; // 元素个数(Count)}- Count:当前有多少个元素。
- Capacity:内部数组的长度,也就是不扩容最多能放多少个。
扩容机制
new List<int>() Capacity = 0第 1 次 Add Capacity = 4第 5 次 Add Capacity = 8 ← 新建长度 8 的数组,复制 4 个元素第 9 次 Add Capacity = 16 ← 新建长度 16 的数组,复制 8 个元素...每次满了就翻倍扩容时要分配新数组 + 复制全部元素,是 O(n) 的操作,旧数组变成垃圾等待 GC。
虽然单次扩容是 O(n),但因为每次容量翻倍,扩容发生得越来越少,平均下来每次 Add 仍然是 O(1)(均摊复杂度)。
实践:能预估数量时,创建时就指定容量,避免多次扩容和产生垃圾:
var enemies = new List<Enemy>(100);各操作的复杂度
| 操作 | 复杂度 | 说明 |
|---|---|---|
list[i] 读写 | O(1) | 直接访问数组 |
Add | 均摊 O(1) | 满了才扩容 |
Insert(i, x) | O(n) | 要把 i 之后的元素都往后挪一位 |
RemoveAt(i) | O(n) | 要把 i 之后的元素都往前挪一位;删最后一个是 O(1) |
Remove(x) | O(n) | 先线性查找,再挪动 |
Contains、IndexOf | O(n) | 线性查找 |
Sort | O(n log n) | 内省排序(快速排序为主),不稳定 |
不在乎顺序时的 O(1) 删除:把要删的元素和最后一个交换,再删除最后一个:
void RemoveAtSwapBack<T>(List<T> list, int index){ int last = list.Count - 1; list[index] = list[last]; list.RemoveAt(last);}注意点
- 遍历时不能修改:
List内部有一个版本号,每次增删都会加一。foreach过程中检测到版本号变化,就抛出InvalidOperationException。需要边遍历边删除时,用倒序 for 循环。 - foreach 不产生 GC:
List<T>的枚举器是结构体,直接foreach一个List<T>不会分配内存;但如果是通过IEnumerable<T>接口遍历,枚举器会被装箱。 - 元素是结构体时,
list[i].x = 1会编译报错,因为索引器返回的是副本(见 值类型与引用类型)。 Clear()只把 Count 置零,不会缩小内部数组。想释放多余容量可以调用TrimExcess()。
LinkedList<T>
原理:双向链表
┌────────────────────────────────────────┐ ▼ │┌─────────┐ ┌─────────┐ ┌─────────┐ ││ prev │◀───│ prev │◀───│ prev │ ││ 10 │ │ 20 │ │ 30 │ ││ next │───▶│ next │───▶│ next │─────┘└─────────┘ └─────────┘ └─────────┘ head每个元素都包装在一个 LinkedListNode<T> 节点对象里,节点记录前一个和后一个节点。.NET 的实现是双向循环链表:最后一个节点的 next 指回头节点。
| 操作 | 复杂度 |
|---|---|
| 在已知节点前后插入、删除已知节点 | O(1),只需要改几个指针 |
| 头尾插入、删除 | O(1) |
| 按位置访问、查找某个值 | O(n),只能从头一个个走 |
为什么实际很少用
理论上链表插入删除是 O(1),但实际项目中,大多数时候 List 反而更快:
- 每个节点都是一个独立的堆对象:每次添加都分配内存,删除后产生垃圾,GC 压力大。
- 节点分散在内存各处:遍历时缓存几乎不起作用。
- 要先找到节点才能 O(1) 插入删除,而查找本身是 O(n)。
适合用链表的情况很少:元素非常多、需要频繁在中间插入删除,并且手里已经持有节点引用(比如 LRU 缓存,用字典存节点,链表维护使用顺序)。
Stack<T>
原理
后进先出(LIFO)。内部是一个数组加一个栈顶下标,和 List 很像,只在数组末尾操作:
Push(1) Push(2) Push(3) Pop() → 3┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐│ 1 │ 2 │ 3 │ │ │ 1 │ 2 │ │ │└───┴───┴───┴───┘ └───┴───┴───┴───┘ ▲ 栈顶 ▲ 栈顶Push:均摊 O(1),满了翻倍扩容。Pop、Peek:O(1)。
典型用途
- 撤销(Undo):每次操作入栈,撤销时出栈。
- UI 界面栈:打开界面入栈,按返回键关闭栈顶界面,回到上一个。
- 深度优先搜索、表达式求值、括号匹配。
Queue<T>
原理:环形数组
先进先出(FIFO)。如果用普通数组,每次从头部取出元素都要把后面的元素整体前移,是 O(n)。Queue<T> 用环形数组解决:维护头、尾两个下标,取出时只移动头下标,到了数组末尾就绕回开头。
初始容量 4,依次 Enqueue(A, B, C),再 Dequeue 两次,再 Enqueue(D, E)
┌───┬───┬───┬───┐│ E │ │ C │ D │└───┴───┴───┴───┘ ▲ ▲ tail head ← 尾部写到末尾后绕回了下标 0Enqueue:均摊 O(1)。元素个数达到容量时扩容,扩容时会把数据按正确顺序复制到新数组的开头。Dequeue、Peek:O(1)。
典型用途
- 消息、事件队列:按顺序处理。
- 分帧处理:任务放进队列,每帧取出若干个执行。
- 广度优先搜索(如格子地图寻路)。
非泛型集合
ArrayList、Hashtable、Stack、Queue(非泛型版本)存的都是 object,放入值类型会装箱,取出时要强制转换。它们是 .NET 有泛型之前的产物,新代码中一律使用泛型版本。装箱的开销见 装箱与拆箱。
选型对比
包含下一篇介绍的哈希表和有序集合:
| 集合 | 底层结构 | 按下标访问 | 查找 | 插入 / 删除 | 有序 | 适合 |
|---|---|---|---|---|---|---|
T[] | 连续数组 | O(1) | O(n) | 不能改变大小 | 按下标 | 数量固定 |
List<T> | 动态数组 | O(1) | O(n) | 尾部 O(1),中间 O(n) | 按插入顺序 | 大多数场景的默认选择 |
LinkedList<T> | 双向链表 | 不支持 | O(n) | 已知节点 O(1) | 按插入顺序 | 持有节点、频繁中间插删 |
Stack<T> | 数组 | 不支持 | O(n) | 栈顶 O(1) | 后进先出 | 撤销、界面栈 |
Queue<T> | 环形数组 | 不支持 | O(n) | 头尾 O(1) | 先进先出 | 消息队列、分帧任务 |
Dictionary<K,V> | 哈希表 | 按 key O(1) | O(1) | O(1) | 无序 | 按 key 快速查找 |
HashSet<T> | 哈希表 | 不支持 | O(1) | O(1) | 无序 | 去重、判断是否存在 |
SortedDictionary<K,V> | 红黑树 | 按 key O(log n) | O(log n) | O(log n) | 按 key 排序 | 需要有序遍历 |
SortedList<K,V> | 两个有序数组 | O(1) / 按 key O(log n) | O(log n) | O(n) | 按 key 排序 | 数据少、插入少、需要有序 |
哈希表的原理见 C# 常用集合(二):Dictionary 与 HashSet。
常见追问
数组为什么能 O(1) 访问? 内存连续、元素大小相同,地址 = 起始地址 + 下标 × 元素大小,直接算出来。
List 是怎么扩容的? 内部是数组,满了就新建一个两倍大小的数组,把元素复制过去。单次扩容 O(n),但均摊到每次 Add 是 O(1)。能预估数量时应该指定初始容量。
List 的 Insert 和 RemoveAt 为什么慢? 要把插入或删除位置之后的元素整体挪动一位,是 O(n)。删除最后一个元素是 O(1)。
为什么 foreach 时不能修改 List? List 有版本号,增删时会改变。枚举器发现版本号变了就抛异常。需要边遍历边删可以倒序 for 循环。
链表插入删除是 O(1),为什么一般还是用 List? 链表每个节点都是堆对象,分配多、GC 压力大,节点分散导致缓存命中率低,而且找到节点本身就要 O(n)。
Queue 是怎么实现 O(1) 出队的? 环形数组:出队只移动头下标,不移动元素,下标到末尾后绕回开头。
Stack 和 Queue 在游戏中有什么用? Stack:撤销、UI 界面返回。Queue:消息队列、分帧处理任务、广度优先寻路。
文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!