| 类型 | 插入时间复杂度 | 查找时间复杂度 | 删除时间复杂度 | 索引访问 | 排序 | 数据结构 | 备注 |
|---|---|---|---|---|---|---|---|
| Array | O(n)；尾部为O(1) | O(n) | O(n)；尾部为O(1) | O(1) | O(n log n) | 数组 | 有序数组二分查找为 O(log n) |
| BitArray | O(n)；尾部为O(1) | O(n) | O(n)；尾部为O(1) | O(1) | O(n log n) | 数组 | 元素为bit，提供位运算方法 |
| ArrayList | O(n)；尾部为O(1) | O(n) | O(n)；尾部为O(1) | O(1) | O(n log n) | 数组 | 在 Array 的基础上添加了自动扩容和常用增删操作，不支持泛型 |
| HashSet<T> | O(1) | O(1) | O(1) | - | - | 哈希表 | 理想情况下为 O(1)，哈希冲突时退化为 O(n) |
| List<T> | Add：O(1)；Insert：O(n)； | O(n) | O(n) | O(1) | O(n log n) | 数组 | 在 ArrayList 的基础上添加了泛型支持；排序根据数据情况结合快速排序、插入排序和堆排序 |
| LinkedList<T> | AddLast：O(1)；AddFirst：O(1) | O(n) | Remove：O(n)；RemoveFirst：O(1)；RemoveLast：O(1) | - | - | 双向链表 | |
| Queue/Queue<T> | Enqueue：O(1) | Contains: O(n)；Peek：O(1) | Dequeue：O(1) | - | - | 动态循环数组 | Queue<T> 为 Queue 的泛型版本 |
| Stack/Stack<T> | Push：O(1) | O(n) | Pop：O(1) | - | - | 数组 | Stack<T> 为 Stack 的泛型版本；插入需扩容时为 O(n) |
| HashTable | O(1) | ContainsKey：O(1)；ContainsValue：O(n) | O(1) | O(1) | - | 哈希表 | 不支持泛型 |
| Dictionary<TKey, TValue> | O(1) | ContainsKey：O(1)；ContainsValue：O(n) | O(1) | O(1) | - | 哈希表 | HashTable 的泛型版本 [3] |
| SortedList<TKey, TValue> | O(n) | O(log n) | O(n) | 双数组 | 查找算法使用二分查找 | ||
| SortedSet<T> | O(log n) | O(log n) | O(log n) | - | - | 红黑树 | 有序，获取 Min/Max 元素时为 O(1) |
| SortedDictionary<TKey, TValue> | O(log n) | O(log n) | O(log n) | O(1) | - | 红黑树 | 查找与 SortedList 类似 |
| OrderedDictionary | Add：O(1)；Insert：O(n)； | O(1) | O(1) | O(1) | - | 数组+哈希表 | ArrayList + Hashtable，不支持泛型，添加数据时保持数据的顺序 |
| ListDictionary | Add：O(1) | O(n) | O(n) | O(1) | - | 单向链表 | 适合处理超小列表 |
| HybridDictionary | O(1) | O(1) | O(1) | O(1) | - | 数组/哈希表 | ListDictionary 的扩展，用于处理更大的列表，元素 ≥8 时转换为 HashTable |
[1] Array 和 ArrayList 的区别
[2] 双向链表
LinkedList 为双向链表，C# 并未提供单项链表。单项链表的时间复杂度为：
[3] 哈希表
[4] 红黑树（二叉查找树）