C# 常用集合(一):数组、List、LinkedList、Stack、Queue

2419 字
12 分钟
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、IndexOfO(n)线性查找
SortO(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 ← 尾部写到末尾后绕回了下标 0
  • Enqueue:均摊 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:消息队列、分帧处理任务、广度优先寻路。

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

C# 常用集合(一):数组、List、LinkedList、Stack、Queue
https://xslab.cloud/posts/csharp/collections/linear-collections/
作者
LuxFire
发布于
2026-10-10
许可协议
CC BY-NC-SA 4.0
相关文章 智能推荐
1
C# 常用集合(二):Dictionary 与 HashSet 的哈希表原理
C#底层/数据结构 哈希表的基本原理与哈希冲突的两种解决方式;.NET Dictionary 的内部结构(buckets 与 entries 数组)、查找流程、扩容为什么用质数;GetHashCode 与 Equals 的约定,结构体作 key 的装箱问题,GameObject 作 key 为什么慢;以及 HashSet、SortedDictionary、SortedList 的对比。
2
C# 关键字速查
C#底层/关键字 按类别整理 C# 常用关键字,每个一两句话说明用途和要点,复杂的关键字链接到专题文章。适合复习时快速过一遍。
3
C# 访问修饰符与类型修饰符
C#底层/关键字 六种访问级别的可见范围对比,protected internal 与 private protected 的区别,各种成员的默认访问级别;以及 static、sealed、abstract、partial 修饰类型时的含义和限制,附 Unity 中 asmdef 与静态字段的注意点。
4
C# 常量与只读:const、readonly 与 static readonly
C#底层/关键字 const 与 readonly 的本质区别(编译期常量与运行时只读),为什么修改 const 要重新编译引用方,readonly 引用类型字段的误区,readonly struct、readonly 成员与防御性复制,以及 init 访问器。
5
C# 继承与多态关键字:virtual、override、new、abstract、sealed
C#底层/关键字 virtual 与 override 如何实现运行时多态,override 与 new 的本质区别,abstract 与 sealed 的用法,base 和 this,构造函数的执行顺序与构造函数中调用虚方法的陷阱,以及 Unity 中 Awake、Update 等消息方法的继承写法。
随机文章 随机推荐
Profile Image of the Author
LuxFire
Hello, I'm LuxFire.
公告
欢迎来到我的博客!这是一则示例公告。
音乐
封面

音乐

暂未播放

0:00 0:00
暂无歌词
分类
标签
站点统计
文章
60
分类
6
标签
164
总字数
171,869
运行时长
0 天
最后活动
0 天前

文章目录