.NET 数据结构：线性表 - 链表

场景

数组需要占用连续的内存空间，当系统内存严重碎片化或没有足够大的连续区块时，创建大数组可能会失败。

相比之下，链表（Linked List） 对内存布局的要求更为灵活。它利用零散的内存碎片，将数据分散存储，通过逻辑上的连接形成线性结构。

基本概念

作为一个线性数据结构，链表与数组的核心区别在于内存布局。链表的每个元素，或称为节点 (Node)，除了存储数据本身外，还记录了下一个节点的引用（在非托管语言中通常是内存地址）。

这种结构允许节点在内存中分散分布，但也带来了额外的开销：

空间开销：每个节点需要额外的内存来存储引用。
时间开销：不支持随机访问，必须按序遍历。

链表结构示意图

最基础的链表是单链表，节点仅指向下一个节点。如果节点同时指向前一个和后一个节点，则称为双向链表。

单链表

单链表的实现

在 .NET 中，借助泛型可以做出以下简单实现：

class LinkedNode<T>(T value)
{
	public T Value { get; set; } = value;  // 节点的值
	
	public LinkedNode<T> Next { get; set; }  // 下一个节点的引用
}

单链表常用操作

初始化

单链表的初始化通常包括实例化节点和建立连接：

1
2
3

var node1 = new LinkedNode<int>(1);
var node2 = new LinkedNode<int>(2);
node1.Next = node2; // node1 -> node2

插入

在链表中插入节点非常高效，时间复杂度为 O(1)（前提是已持有插入位置的前驱节点）。

假设要在节点 A 和 B 之间插入节点 C（即 A -> B 变为 A -> C -> B）：

将 C 的 Next 指向 B。
将 A 的 Next 指向 C。

/* 在 node1 之后插入 insertNode */
void InsertNode<T>(LinkedNode<T> node1, LinkedNode<T> insertNode)
{
	var node2 = node1.Next;  // 保存原有的下一个节点
	insertNode.Next = node2;  // C -> B
	node1.Next = insertNode;  // A -> C
}

删除

删除操作同样高效，只需要修改引用的指向，使目标节点脱离链表即可。

假设链表为 A -> C -> B，要删除节点 C：
通常我们需要操作 C 的前驱节点 A，将其 Next 指针直接指向 B。此时 C 变得不可达，最终会被垃圾回收（GC）。

/* 删除给定节点的后继节点 (即删除 node.Next) */
void RemoveNode<T>(LinkedNode<T> node)
{
	if (node.Next == null)  // 如果没有后继节点，则无需操作
		return;
	
    // node -> middleNode -> nextNode
    // 变为
    // node -> nextNode
	var middleNode = node.Next;
	var nextNode = middleNode.Next;
	node.Next = nextNode;
}

访问

链表的劣势在于访问效率。与数组的随机访问 O(1) 不同，链表必须从头节点开始逐个遍历，时间复杂度为 O(n)。

LinkedNode<T> VisitNode<T>(LinkedNode<T> head, int index)
{
	for(var i = 0; i < index; i++)
	{
		if(head == null)  // 遍历访问时发现节点为 null，意味着不可能达到给定索引的节点
		{
			return null;
		}
		head = head.Next;
	}
	return head;
}

向链表与 LinkedList<T>

双向链表（Doubly Linked List）要求每个节点同时保存前驱引用（Prev）和后继引用（Next），这使得它能够双向遍历。

在 .NET BCL 中，System.Collections.Generic.LinkedList<T> 是双向链表的标准实现。它是一个通用链表，不允许通过索引直接访问元素（不支持下标运算），但支持高效的插入和删除。

var linkedList = new LinkedList<int>();

// AddFirst: O(1)
var firstNode = new LinkedListNode<int>(1);
linkedList.AddFirst(firstNode);  // 链表: 1

// AddAfter: O(1)
var secondNode = new LinkedListNode<int>(4);
linkedList.AddAfter(firstNode, secondNode);  // 链表: 1 -> 4

// AddBefore: O(1)
var thirdNode = new LinkedListNode<int>(5);
linkedList.AddBefore(secondNode, thirdNode);  // 链表: 1 -> 5 -> 4

常用链表类型

单链表
双链表
环形链表：让单链表首尾相接可得，之后任一节点均可视为头节点

虽然在日常业务开发中，动态数组 List<T> 通常是默认选择，但在特定场景下链表具有不可替代的优势：

单链表

栈 (Stack) 与队列 (Queue)：
- 栈：利用头插法，在链表头部进行 Push 和 Pop 操作，时间复杂度均为 O(1)。
- 队列：维护头尾指针，头部删除，尾部插入，时间复杂度均为 O(1)。
哈希表 (Hash Table)：在解决哈希冲突时，链地址法（Chaining）通常使用单链表将散列到同一索引的元素串联起来。
图的邻接表 (Adjacency List)：图的每个顶点维护一个链表，记录与其相连的边。

双向链表

LRU 缓存策略：利用双向链表极其高效地移动节点位置（例如将最近访问的元素移到头部）。
浏览器历史记录：浏览器的“后退”与“前进”功能，本质上是一个双向链表的游标移动。

环形链表

时间片轮转调度：操作系统中，将进程组织成环形链表，依次分配 CPU 时间片。
流媒体缓冲：使用环形缓冲区（Ring Buffer）处理连续的数据流，实现无缝播放

环形链表

数据缓冲：将多媒体的数据流分成缓冲块后，放入一个环形链表，从而实现播放的无缝切换。