C-#常用数据结构总结
目录
数组(Array):固定大小的同类型元素集合，访问速度快
列表(List):动态大小的同类型元素集合，支持增删改查
栈(Stack):后进先出(LIFO)的元素集合，常用于递归和回溯
队列(Queue):先进先出(FIFO)的元素集合，常用于任务调度
字典(Dictionary):键值对集合，通过键快速查找值
一、基础数据结构
数组(Array)
// 一维数组
int[] numbers = new int[5];
int[] numbers2 = {1, 2, 3, 4, 5};
// 多维数组
int[,] matrix = new int[3,3];
// 交错数组
int[][] jaggedArray = new int[3][];字符串(string)
string str = "Hello";
string str2 = new string('a', 5);二、集合框架(System.Collections)
List - 动态数组
List<int> list = new List<int>();
list.Add(1);
list.AddRange(new[] {2, 3, 4});
list.insert(0, 0);
list.Remove(3); // 删除第一个等于3的元素，若存在多个只删除一个，不存在不抛异常
list.RemoveAt(0); // 删除 索引为 0 的元素(第一个元素)，若索引越界会抛异常 ArgumentOutOfRangeException
list.Sort();
int count = list.Count();
bool contains = list.Contains(2);Dictionary<Tkey, TValue> - 哈希表
Dictionary<string, int> dict = new Dictionary<string, int>();
dict.Add("one", 1);
dict["two"] = 2; // 添加或修改
dict.TryGetValue("one", out int value); // 根据key获取对应的value,不会抛异常,返回bool
bool hasKey = dict.ContainsKey("two");
dict.Remove("one");HashSet - 无序不重复集合
HashSet<int> set = new HashSet<int>();
set.Add(1);
set.Add(2);
set.Add(1); // 不会重复添加
bool added = set.Add(3); // 返回是否成功添加
bool contains = set.Contains(2);
set.Remove(1);SortedSet - 有序不重复集合
SortedSet<int> sortedSet = new SortedSet<int>();
sortedSet.Add(3);
sortedSet.Add(1);
sortedSet.Add(2); // 自动排序: 1, 2, 3
int min = sortedSet.Min; // 当前集合中的最小值
int Max = sortedSet.Max; // 当前集合中的最大值Queue - 队列(先进先出)
Queue<string> queue = new Queue<string>();
queue.Enqueue("first"); // 入队
queue.Enqueue("second");
string first = queue.Dequeue(); // 出队:移除队首元素，返回被移除元素，队列为空抛异常：InvalidOperationException； 这里队首为： "first"
string peek = queue.Peek(); // 返回队首元素，不删除 队列为空抛异常：InvalidOperationException；此处队首为： "second"
bool isEmpty = queue.Count == 0; // 判断空队列的方式Stack - 栈(后进先出)
Stack<string> stack = new Stack<string>();
stack.Push("first"); // 入栈
stack.Push("second");
string top = stack.Pop(); // 弹栈： 移除栈顶元素，返回被移除元素，栈为空抛异常：InvalidOperationException; 这里栈顶元素为： "second"
string peek = stack.Peek(); // 查看栈顶，返回栈顶元素，不删除，空栈抛异常：InvalidOperationException; 此处栈顶为："first"LinkedList - 双向链表
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(1); // 链表：1 ; 若再执行linkedList.AddLast(0),则链表结构为: 1 <-> 0; LinkedList<T>是：双向链表，每个节点有 Previous 和 next，不连续内存。
linkedList.AddFirst(0); // 把新节点插到头部，链表变为: 0 <-> 1;此时 Head = 0,Tail = 1。
LinkedListNode<int> node = linkedList.Find(1); // 线性查找，返回第一个匹配节点，此处指向值为1的节点： 0 <-> [1]
linkedList.AddAfter(node, 2); // 链表变为 0 <-> 1 <->2 ;因为Find(1)已经拿过了节点引用
linkedList.Remove(0); // 按值删除(线性查找), 结果为：1 <-> 2SortedDictionary<Tkey, TValue> - 有序字典
SortedDictionaty<string, int> sortedDict = new SortedDictionary<string, int>();
sortedDict.Add("zebra", 1);
sortedDict.Add("apple", 2);
sortedDict.Add("banana", 3);
// 按键自动排序: apple, banana, zebraSortedList<Tkey, TValue> - 有序列表
SortedList<string, int> sortedList = new SortedList<string, int>();
sortedList.Add("zebra", 1);
sortedList.Add("apple", 2);
// 按键排序三、并发集合(System.Collections.Concurrent)
ConcurrentBag - 线程安全的无序集合
ConcurrentBag<int> bag = new ConcurrentBag<int>();
bag.Add(1);
bag.TryTake(out int result); // 尝试移除一个元素，返回bool，赋值给rsult，失败(集合为空)不抛异常ConcurrentDictionary - 线程安全的高并发字典
ConcurrentDictionary<string, int> concurrentDict =
new ConcurrentDictionary<string, int>();
concurrentDict.TryAdd("key", 1); // 返回bool，不会抛异常
concurrentDict.AddOrUpdate("key", 2, (k, v) => v + 1);
// 方法签名为：
TValue AddOrUpdate(
TKey key,
TValue addValue,
Func<TKey, TValue, TValue> updateValueFactory
)
// 情况A: key不存在，使用addValue，即插入2
// 情况B(当前情况): key已存在，更新key
ConcurrentQueue 和 ConcurrentStack
ConcurrentQueue<int> concurrentQueue = new ConcurrentQueue<int>();
concurrentQueue.Enqueue(1);
concurrentQueue.TryDequeue(out int item);
ConcurrentStack<int> concurrentStack = new ConcurrentStack<int>();
concurrentStack.Push(1);
concurrentStack.TryPop(out int popped);
// 空时不抛异常，返回falseBlockingCollection - 线程安全的阻塞集合
BlockingCollection<int> blockingCollection = new BlockingCollection<int>();
// 支持生产者-消费者模式四、不可变集合(System.Collections.Immutable)
ImmutableList
ImmutableList<int> immutableList = ImmutableList.Create<int>();
immutableList = immutableList.Add(1);
immutableList = immutableList.Remove(1);ImmutableDictionary<TKey, TValue>
ImmutableDictionary<string, int> immutableDict = ImmutableDictionary.Create<string, int>();
immutableDict = immutableDict.Add("key", 1);ImmutableHashSet 和 ImmutableSortedSet
ImmutableHashSet<int> immutableSet = ImmutableHashSet.Create<int>();
immutableSet = immutableSet.Add(1);五、特殊用途集合
ObservableCollection - 支持数据绑定的集合
ObservableCollection<string> observable = new ObservableCollection<string>();
observable.CollectionChanged += (sender, e) =>
{
// 集合改变时触发
};BitArray - 位数组(按位存储布尔值的紧凑结构)
BitArray bits = new BitArray(8); // 创建一个长度为8的位数组。默认值：索引： 0 -7；值：00000000
bits[0] = true; // 索引赋值，此处结果为:10000000;
bits.Set(1, true); // 等价于 bits[1] = true; 此处结果为11000000;
bits.And(anotherBitArray); // 与另一个BitArray(此处为anotherBitArray)进行按位"与"，两个BitArray长度必须相同，否则抛出ArgumentException.NameValueCollection - 键值对集合(支持重复键)
NameValueCollection collection = new NameValueCollection();
collection.Add("key", "value1");
collection.Add("key", "value2");六、数据结构选择指南
| 数据结构 | 主要用途 | 时间复杂度 | 特点 |
|---|---|---|---|
| List | 需要随机访问，元素数量变化 | 访问：O(1) 插入,删除：O(n) |
动态数组，最常用 |
| Dictionary<Tkey,TValue> | 键值对查找 | 平均：O(1) | 哈希表实现，快速查找 |
| HashSet | 去重，集合运算 | 平均: O(1) | 不重复元素集合 |
| Queue | 先进先出 | 入队/出队:O(1) | 顺序处理任务 |
| Stack | 后进先出 | 入栈/出栈：O(1) | 撤销操作，深度优先搜索 |
| LinkedList | 频繁插入删除 | 插入删除：O(1), 访问：O(n) |
双向链表,适合中间操作 |
| SortedDictionary | 需要排序的键值队 | 操作：O(log n) | 红黑树实现 |
| ConcurrentDictionary | 多线程字典操作 | 线程 | 并发编程 |
七、性能最佳实践
预分配容量：如果知道大概大小
List<int> list = new List<int>(10000);
Dictionary<string, int> dict = new Dictionary<string, int>(100);选择合适的相等比较器
HashSet<string> set = new HashSet<string>(StringComparer.OrdinallgnoreCase);值类型集合使用Span
Span<int> span = stackallo int[10];使用IEnumerable延迟加载
IEnumerable<int> numbers = GetNumbers();
var result = numbers.Where(n => n > 0).Take(10);