当前位置：首页 > web >正文

40、C# 数组、链表、哈希、队列、栈数据结构的特点、优点和缺点

web 2025/5/13 12:11:58

一、数组（Array）

1.特点

固定长度，初始化后大小不可变。
元素在内存中连续存储，通过索引直接访问。
支持多维数组（如二维、三维数组）。

2.优点

快速随机访问：通过索引访问元素的时间复杂度为O(1)。
内存连续：连续存储有助于缓存优化，提升访问效率。
简单易用：语法直观，适合处理固定大小的集合。

3.缺点

大小固定：无法动态扩展，需手动创建新数组并复制元素。
插入/删除效率低：在中间插入或删除元素需移动大量元素，时间复杂度为O(n)。

4.代码示例

int[] array = new int[5] { 1, 2, 3, 4, 5 };// 访问元素
int element = array[2]; // 返回3// 修改元素
array[1] = 10; // 数组变为 [1, 10, 3, 4, 5]// 遍历数组
foreach (int num in array)
{Console.WriteLine(num);
}

二、链表（LinkedList）

1.特点

动态长度，节点通过指针连接，无需连续内存。
支持双向链表（LinkedList），可前后遍历。

2.优点

动态扩展：无需预先分配空间，可随时增删节点。
高效插入/删除：在头部或尾部操作时间复杂度为O(1)，中间操作为O(n)（需遍历）。

3.缺点

随机访问效率低：需从头节点遍历，时间复杂度为O(n)。
额外内存开销：每个节点需存储指针，占用更多空间。

4.代码示例

using System.Collections.Generic;LinkedList<int> linkedList = new LinkedList<int>();// 添加元素
linkedList.AddLast(1); // 链表: 1
linkedList.AddLast(2); // 链表: 1 -> 2// 插入元素
var node = linkedList.Find(1);
linkedList.AddAfter(node, 3); // 链表: 1 -> 3 -> 2// 删除元素
linkedList.Remove(3); // 链表: 1 -> 2// 遍历链表
foreach (int num in linkedList)
{Console.WriteLine(num);
}

三、哈希表（Dictionary）

1.特点

键值对存储，通过哈希函数快速定位元素。
键唯一，值可重复。

2.优点

快速查找/插入/删除：平均时间复杂度为O(1)，适合高频操作。
动态扩容：自动调整大小，适应数据变化。

3.缺点

无序存储：元素顺序不固定，可能影响遍历逻辑。
哈希冲突：极端情况下性能退化为O(n)，需合理设计哈希函数。
内存开销：需存储哈希桶和冲突解决机制。

4.代码示例

using System.Collections.Generic;Dictionary<string, int> dict = new Dictionary<string, int>();// 添加键值对
dict.Add("Alice", 25);
dict["Bob"] = 30; // 添加或更新// 查找元素
if (dict.TryGetValue("Alice", out int age))
{Console.WriteLine($"Alice's age: {age}"); // 输出25
}// 删除元素
dict.Remove("Bob");// 遍历键值对
foreach (var kvp in dict)
{Console.WriteLine($"Key: {kvp.Key}, Value: {kvp.Value}");
}

四、队列（Queue）

1.特点

先进先出（FIFO），元素从队尾入队，从队头出队。

2.优点

高效顺序处理：入队和出队时间复杂度均为O(1)。
动态大小：无需预先分配空间。

3.缺点

随机访问受限：仅能访问队头和队尾元素。
线程安全需额外处理：多线程环境下需同步机制。

4.代码示例

using System.Collections.Generic;Queue<string> queue = new Queue<string>();// 入队
queue.Enqueue("Task1");
queue.Enqueue("Task2"); // 队列: Task1 -> Task2// 出队
string firstTask = queue.Dequeue(); // 返回"Task1"，队列变为 [Task2]// 查看队头元素
string peekTask = queue.Peek(); // 返回"Task2"// 遍历队列
while (queue.Count > 0)
{Console.WriteLine(queue.Dequeue());
}

五、栈（Stack）

1.特点

后进先出（LIFO），元素从栈顶压入和弹出。

2.优点

高效操作：压栈和弹栈时间复杂度为O(1)。
支持递归：天然适合递归算法（如函数调用栈）。

3.缺点

随机访问受限：仅能访问栈顶元素。
容量有限：需注意栈溢出风险（可通过动态扩容缓解）。

4.代码示例

using System.Collections.Generic;Stack<int> stack = new Stack<int>();// 压栈
stack.Push(1);
stack.Push(2); // 栈: 2 -> 1// 弹栈
int top = stack.Pop(); // 返回2，栈变为 [1]// 查看栈顶元素
int peek = stack.Peek(); // 返回1// 遍历栈
while (stack.Count > 0)
{Console.WriteLine(stack.Pop());
}