C# 算法与数据结构：开发者完整指南

轻松学习Python，无需理论负担。在浏览器中直接解决带自动检查的实践任务，无需安装任何东西。

C# 算法与数据结构入门

算法与数据结构是构建任何高质量软件的基石。在 .NET 生态系统和 C# 语言中，理解这些概念不仅能让你编写更高效的代码，还能帮助你从丰富的标准库 (BCL — Base Class Library) 中明智地选择工具。数据结构的选择直接影响应用程序的运行速度、内存消耗，并最终影响用户体验。

在本文中，我们将剖析每位 C# 开发者都应掌握的关键数据结构与算法。我们将探讨它们的实现、性能特性 (Big O 表示法) 以及实际的代码示例。本文适合希望系统化知识的初学者和经验丰富的程序员。

C# 中的基本数据结构

数组与列表 (Array vs List<T>)

数组 (Array) 是一种固定大小的数据结构，将相同类型的元素存储在连续的内存区域中。通过索引访问的时间复杂度为 O(1)，但插入和删除元素（末尾除外）由于需要移位，时间复杂度为 O(n)。

int[] numbers = new int[5] { 10, 20, 30, 40, 50 };Console.WriteLine(numbers[2]); // 30

List<T> 是一个动态数组。它在添加元素时会自动增加容量。内部使用数组实现，因此通过索引访问的速度也是 O(1)。然而，在中间或开头插入元素的时间复杂度为 O(n)。

List<string> names = new List<string>() { "安娜", "鲍里斯" };names.Add("维克多");names.Insert(1, "格列布"); // O(n)Console.WriteLine(names[0]); // 安娜

栈与队列 (Stack<T> 和 Queue<T>)

Stack<T> (栈) 遵循后进先出 (LIFO) 原则。用于遍历算法、表达式解析和调用管理。

Stack<int> stack = new Stack<int>();stack.Push(1);stack.Push(2);stack.Push(3);int top = stack.Pop(); // 3

Queue<T> (队列) 遵循先进先出 (FIFO) 原则。应用于任务处理系统和数据缓冲。

Queue<string> queue = new Queue<string>();queue.Enqueue("任务 1");queue.Enqueue("任务 2");string next = queue.Dequeue(); // "任务 1"

这两种结构都基于数组（循环缓冲区）实现，平均情况下插入和删除操作的时间复杂度为 O(1)。

字典 (Dictionary<TKey, TValue>)

Dictionary<TKey, TValue> 是一个哈希表。它在平均情况下（使用良好的哈希函数）提供 O(1) 时间复杂度的按键查找、插入和删除操作。这是 C# 中最常用的数据结构之一。

Dictionary<string, int> ages = new Dictionary<string, int>();ages["爱丽丝"] = 30;ages["鲍勃"] = 25;

if (ages.ContainsKey("爱丽丝")){    Console.WriteLine(ages["爱丽丝"]); // 30}

重要提示： Dictionary 中的键必须是唯一的，并且必须实现 IEquatable<T> 接口，或者正确重写 GetHashCode() 和 Equals() 方法。

链表 (LinkedList<T>)

LinkedList<T> 是一个双向链表。与 List 不同，在链表中间插入和删除元素的时间复杂度为 O(1)（如果你有对节点的引用）。然而，通过索引访问的时间复杂度为 O(n)。它使用较少，但对于需要双向访问的队列和 LRU 缓存来说是不可或缺的。

LinkedList<int> list = new LinkedList<int>();list.AddLast(1);list.AddLast(2);list.AddFirst(0);

LinkedListNode<int> node = list.Find(1);list.AddAfter(node, 10); // O(1)