集合类

.NET Standard标准中规定了一系列通用集合类，包括大部分常见的数据结构，如线性表、字典、集合、栈、队列等。我们实际开发中，基本不需要再手写这些结构，而应该尽量采用标准库的实现，避免重复造轮子。这里要注意的是.NET Standard只是一个标准，它没有规定底层运行时如何实现这些数据结构，但由于这些都是极为基础的数据结构，无论是.NET Core还是Mono其实现应该是类似的。

System.Collections.Generic 通用泛型集合工具包

System.Collections.Generic包含了一系列用于定义泛型集合的接口和类，允许用户创建强类型集合。常用的有如下几种：

• List 顺序表
• LinkedList 链表
• Dictionary 字典
• SortedDictionary 有序字典
• HashSet 集合
• SortedSet 有序集合
• Stack 栈
• Queue 队列

线性表

线性表包含顺序表（数据结构中也常被称为动态数组）和链表，顺序表通常基于定长数组实现，但额外实现了扩充机制，具有较高的随机访问性能。

// 创建顺序表
List<string> list = new List<string>();

// 顺序插入元素
list.Add("apple");
list.Add("banana");
list.Add("pear");

// 随机插入元素
list.Insert(1, "orange");

// 删除元素
list.Remove("pear");

// 根据索引获取元素
string s = list[1];
Console.WriteLine(s);

// 遍历顺序表
foreach (string item in list)
{
    Console.WriteLine(item);
}

上面例子代码中，简单演示了顺序表List<T>中的一些操作。下面整理了List<T>中其它一些极为常用的成员。

Find等按条件操作的成员配合Lambda表达式使用非常方便，下面是一个例子。

List<int> list = new List<int> { 1, 2, 3, 4, 5 };
int found = list.Find(n => n > 3);        // 4，第一个大于3的元素
List<int> all = list.FindAll(n => n > 3); // 4, 5

如果声明集合的同时初始化其中的元素，可以使用以下语法：

List<string> list = new List<string>
{
    "apple", "banana", "pear"
};

字典

字典分为无序字典和有序字典，无序字典通常采用哈希表实现，插入和搜索性能极高，唯一的缺点是哈希表是无法指定顺序的；而有序字典通常采用二叉搜索树实现（如红黑树），搜索性能比哈希表会低一些，但支持指定顺序。此外我们要知道的一点是，字典的键不能重复，但要注意两种添加方式的行为差异：使用Add()添加重复的键会抛出ArgumentException异常；而使用索引器dict[key] = value赋值时，若键已存在则会覆盖对应的值，若键不存在则直接添加。

// 创建字典
Dictionary<string, string> dict = new Dictionary<string, string>();

// 插入数据
dict.Add("title", "my diary");
dict.Add("content", "hello world");
dict.Add("date", "1994-12-17");

// 通过Key获取值
string s = dict["title"];
Console.WriteLine(s);

// 删除键
dict.Remove("date");

// 遍历Key
foreach (string key in dict.Keys)
{
    Console.WriteLine("key {0}", key);
}

// 遍历字典键值对
foreach (KeyValuePair<string, string> item in dict)
{
    Console.WriteLine("key {0} value {1}", item.Key, item.Value);
}

上面例子演示了哈希字典Dictionary<K,V>的使用。这里还有几点需要特别注意：

1. 通过索引器dict["title"]读取键对应的值时，如果键不存在会抛出KeyNotFoundException异常。实际开发中更推荐使用TryGetValue()方法，它在键不存在时返回false而不抛异常，并且只需一次查找就能同时完成判断和取值，性能也更好。

if (dict.TryGetValue("title", out string? value))
{
    Console.WriteLine(value);
}

1. 如果只需要判断键是否存在而不关心值，可以使用ContainsKey()方法。
2. 无序字典基于哈希表实现，遍历时的元素顺序是不保证的，不要依赖遍历顺序编写逻辑，需要有序遍历时应使用SortedDictionary<K,V>或对键排序后再遍历。

集合

集合和字典的实现类似，也分为无序集合和有序集合两种，分别基于哈希表和二叉搜索树。此外，集合和线性表的区别是集合中不能有重复的元素。

// 创建集合
HashSet<string> set = new HashSet<string>();

// 添加元素
set.Add("apple");
set.Add("banana");
set.Add("pear");

// 删除元素
set.Remove("apple");

// 遍历集合
foreach (string s in set)
{
    Console.WriteLine(s);
}

上面例子演示了哈希集合HashSet<T>的使用。Add()方法返回bool值表示元素是否被真正添加（集合中已存在相同元素时返回false），Contains()方法可以判断元素是否存在。此外，作为数学意义上的集合，HashSet<T>还提供了一系列集合运算方法。

HashSet<int> a = new HashSet<int> { 1, 2, 3 };
HashSet<int> b = new HashSet<int> { 2, 3, 4 };
a.IntersectWith(b); // a 变为 { 2, 3 }

栈

栈结构一般都是基于线性表实现，栈具有后进先出（LIFO）的特性。

// 创建栈
Stack<string> stack = new Stack<string>();

// 元素入栈
stack.Push("apple");
stack.Push("banana");
stack.Push("pear");

// 获取栈顶元素
string peek = stack.Peek();
Console.WriteLine(peek);

// 元素出栈
string pop = stack.Pop();
Console.WriteLine(pop);

// 获取栈高度
int length = stack.Count;
Console.WriteLine(length);

上面例子演示了栈Stack<T>的使用。需要注意的是，在空栈上调用Peek()或Pop()会抛出InvalidOperationException异常，如果不确定栈是否为空，可以使用TryPeek()和TryPop()方法，它们在栈为空时返回false而不抛异常，用法和字典的TryGetValue()类似。

队列

队列一般也都是基于线性表实现，和栈相反，队列具有先进先出（FIFO）的特性。

// 创建队列
Queue<string> queue = new Queue<string>();

// 元素存入队列尾部
queue.Enqueue("apple");
queue.Enqueue("banana");
queue.Enqueue("pear");

// 获取队列头部元素
string peek = queue.Peek();
Console.WriteLine(peek);

// 队列头部元素出队列
string top = queue.Dequeue();
Console.WriteLine(top);

// 获取队列长度
int length = queue.Count;
Console.WriteLine(length);

上面例子演示了队列Queue<T>的使用。和栈一样，在空队列上调用Peek()或Dequeue()会抛出InvalidOperationException异常，可以使用TryPeek()和TryDequeue()方法避免。

其它集合功能

除了上面介绍的几种最常用的集合类，System.Collections.Generic中还有一些特定场景下使用的集合：

• SortedList<K,V>：有序字典的另一种实现，它基于数组而非二叉搜索树，元素占用内存更紧凑，但插入删除时需要移动元素，适合创建后读取多、修改少的场景。
• PriorityQueue<TElement, TPriority>（.NET 6新增）：优先队列，出队时按优先级从小到大弹出元素，常用于任务调度等场景。

除此之外，System.Collections中的是旧版的不支持泛型的集合类，它们的存在只是为了向后兼容，不推荐使用。System.Collections.Concurrent中则包含了一些线程安全的集合类，用于多线程环境使用，相关内容将在并发编程章节详细介绍，这里就不展开演示了。