C# 中的LinkedListT详解

1. 基础概念与用法

1.1 什么是 LinkedList<T>？

LinkedList<T> 是 .NET 中位于 System.Collections.Generic 命名空间下的一个泛型双向链表集合类。它内部由一系列节点（LinkedListNode<T>）组成，每个节点包含：

• 数据（Value）
• 指向前一个节点的引用（Previous）
• 指向后一个节点的引用（Next）

与 List<T>（基于数组的顺序存储）不同，LinkedList<T> 不要求内存连续，插入和删除操作在已知节点位置时效率极高（O(1)），但随机访问效率较低（O(n)）。

✅ 关键特点：

• 双向遍历（可向前也可向后）
• 插入/删除快（在已知节点处）
• 不支持索引访问（如 list[0] 会报错！）
• 内存开销略大（每个节点需额外存储前后指针）

1.2 常用方法与属性

方法/属性	说明
AddFirst(T value)	在链表开头添加元素
AddLast(T value)	在链表末尾添加元素
AddBefore(LinkedListNode<T> node, T value)	在指定节点前插入新节点
AddAfter(LinkedListNode<T> node, T value)	在指定节点后插入新节点
Remove(T value)	删除第一个匹配的值
Remove(LinkedListNode<T> node)	删除指定节点
RemoveFirst()	删除第一个节点
RemoveLast()	删除最后一个节点
Find(T value)	查找第一个匹配值的节点（返回 LinkedListNode<T>）
First / Last	获取第一个/最后一个节点（LinkedListNode<T> 类型）
Count	获取元素个数

⚠️ 注意：LinkedList<T> 没有索引器（即不能用 [index] 访问），必须通过遍历或 Find() 获取节点。

1.3 简单示例

using System;
using System.Collections.Generic;class Program
{static void Main(){// 创建一个存储字符串的 LinkedListLinkedList<string> linkedList = new LinkedList<string>();// 添加元素linkedList.AddLast("苹果");linkedList.AddLast("香蕉");linkedList.AddFirst("葡萄"); // 插入到开头Console.WriteLine("当前链表内容：");foreach (string fruit in linkedList){Console.WriteLine(fruit);}// 输出：// 葡萄// 苹果// 香蕉// 查找节点并插入var appleNode = linkedList.Find("苹果");if (appleNode != null){linkedList.AddAfter(appleNode, "橙子");}Console.WriteLine("\n插入“橙子”后：");foreach (string fruit in linkedList){Console.WriteLine(fruit);}// 输出：// 葡萄// 苹果// 橙子// 香蕉// 删除元素linkedList.Remove("香蕉");linkedList.RemoveFirst(); // 删除“葡萄”Console.WriteLine("\n删除后：");foreach (string fruit in linkedList){Console.WriteLine(fruit);}// 输出：// 苹果// 橙子}
}

💡 提示：通过 foreach 遍历 LinkedList<T> 是安全且高效的，底层使用了迭代器。

---

2. 进阶知识点

2.1 节点（LinkedListNode<T>）操作

LinkedList<T> 的核心在于对 节点 的操作。每个节点都是 LinkedListNode<T> 类型，包含 Value、Next、Previous 属性。

var list = new LinkedList<int>();
list.AddLast(10);
list.AddLast(20);var node = list.First; // 获取第一个节点（LinkedListNode<int>）
Console.WriteLine(node.Value);      // 10
Console.WriteLine(node.Next.Value); // 20

你可以直接操作节点，实现高效插入/删除，而无需重新遍历整个链表。

2.2 性能对比：LinkedList<T> vs List<T>

操作	LinkedList<T>	List<T>
在开头插入	O(1)	O(n)（需移动所有元素）
在末尾插入	O(1)	O(1)（均摊）
在中间插入（已知位置）	O(1)	O(n)
随机访问（如第100个）	O(n)	O(1)
查找元素	O(n)	O(n)
内存开销	较高（每个节点多两个指针）	较低（连续数组）

✅ 结论：

• 如果频繁在两端或中间插入/删除，且不需要随机访问，选 LinkedList<T>。
• 如果需要频繁通过索引访问或顺序遍历为主，选 List<T>。

2.3 线程安全性

LinkedList<T> 不是线程安全的。在多线程环境中，必须手动加锁：

private static readonly object lockObj = new object();
private static LinkedList<string> safeList = new LinkedList<string>();// 多线程操作时
lock (lockObj)
{safeList.AddLast("安全添加");
}

如需线程安全的链表，可考虑使用 ConcurrentBag<T> 或自行封装同步逻辑。

2.4 与 IEnumerable<T> 和 LINQ 的兼容性

LinkedList<T> 实现了 IEnumerable<T>，因此可以使用 LINQ：

var numbers = new LinkedList<int> { 1, 2, 3, 4, 5 };
var evenNumbers = numbers.Where(n => n % 2 == 0).ToList();

但注意：LINQ 操作（如 Where、Select）会遍历整个链表，无法利用链表的局部操作优势。

---

3. 实际工作中的使用场景

虽然 LinkedList<T> 不如 List<T> 常用，但在以下场景中非常合适：

3.1 实现“撤销/重做”（Undo/Redo）功能

在图形编辑器、文本编辑器中，用户操作历史通常用链表存储。

• 每次操作生成一个“命令对象”，添加到链表末尾。
• “撤销”时，从末尾移除并执行逆操作。
• “重做”时，将撤销的命令重新加回。

为什么用链表？

• 频繁在末尾添加/删除（O(1)）
• 不需要随机访问历史记录
• 可轻松限制历史长度（如只保留最近50步）

LinkedList<ICommand> history = new LinkedList<ICommand>();// 执行命令
history.AddLast(command);
command.Execute();// 撤销
if (history.Count > 0)
{var last = history.Last.Value;history.RemoveLast();last.Undo();
}

3.2 实现 LRU 缓存（Least Recently Used）

LRU 缓存需要快速将“最近使用”的元素移到头部，淘汰“最久未用”的元素。

• 使用 LinkedList<T> 存储缓存项（按使用时间排序）
• 配合 Dictionary<TKey, LinkedListNode<T>> 实现 O(1) 查找

优势：

• 访问某个元素后，可将其 Remove(node) 再 AddFirst(node)，实现“移到头部”
• 淘汰时直接 RemoveLast()

📌 .NET 中 MemoryCache 并非基于链表，但自定义高性能 LRU 常用此结构。

3.3 游戏开发中的“消息队列”或“事件缓冲区”

在游戏循环中，可能需要按顺序处理玩家输入、AI行为、网络包等。

• 使用 LinkedList 作为事件队列
• 每帧从头部取出事件处理
• 新事件从尾部加入

优点：

• 插入（尾部）和删除（头部）都是 O(1)
• 避免数组扩容带来的性能抖动

3.4 实现浏览器的“前进/后退”历史

浏览器地址栏的前进后退功能天然适合双向链表：

• 当前页面是一个节点
• “后退” = 移动到 Previous
• “前进” = 移动到 Next
• 新页面 = RemoveAfter(current)（清除前进历史） + AddAfter(current, newPage)

这种结构能高效维护线性但可回溯的导航路径。

---

总结

项目	说明
适用场景	频繁在两端或中间插入/删除、无需索引访问
不适用场景	需要随机访问、大量只读遍历、内存极度受限
核心优势	O(1) 插入/删除（已知节点）、双向遍历
核心劣势	无索引、内存开销大、缓存局部性差

作为初学者，建议先掌握 List<T>，再在需要高效局部修改时考虑 LinkedList<T>。理解其底层结构（节点、指针）有助于你做出更合理的数据结构选择。

🌟 记住：没有“最好”的集合，只有“最合适”的集合。根据操作模式选择数据结构，是写出高性能代码的关键！