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

链表是线性的数据结构，其特点是会将元素分散地存储在内存空间中。

场景

数组会连续地占用内存空间，这导致内存在部分情况下难以提供很大的连续空间给一个非常大的数组。

相反，空闲的内存空间通常情况下是分散的，使用链表这一数据结构就可以充分利用。

基本概念

作为一个线性数据结构，它与数组的不同之处在于它的每个元素不仅仅有值，还记录了下一个元素的引用（内存地址）。所以一个链表的元素通常被称为节点，而节点可以通过存储引用来访问下一个节点。

因为每个节点都保存了下一个节点的引用，链表得以让各个节点分散地存储于内存中。

同时，由于每个节点包含了值和引用，这也导致该数据结构在相同数据量下，相比于数组占用更多的内存空间。

只保存一个引用的节点被称为单链表，如果有两个则是双链表。

单链表

单链表的实现

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

1
2
3
4
5
6

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

单链表常用操作

初始化

单链表的初始化分为两步：

1. 实例化节点对象
2. 连接节点

1
2
3

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

插入

单链表中，可以简单地调整三个节点（两个已在链表中的节点和待插入的节点）的引用，从而做到更高效的插入操作，不同于数组，单链表中插入操作的时间复杂度为O(1)

考虑链表节点 A -> B，待插入C节点：

1. 将C节点指向B
2. 将A节点指向C

然后，链表变为 A -> C -> B

在链表节点node1后插入insertNode：

1
2
3
4
5
6

void InsertNode<T>(LinkedNode<T> node1, LinkedNode<T> insertNode)
{
	var node2 = node1.Next;  // 根据 node1 找到它的下一个节点
	insertNode.Next = node2;  // 将插入节点指向该节点
	node1.Next = insertNode;  // 将 node1 指向插入节点
}

删除

与插入操作类似，只需要改变一个节点的引用就能实现删除节点的效果。

考虑链表节点 A -> C -> B，待删除C节点，只需将 A 节点指向 B 即可，C 则不可访问。

1
2
3
4
5
6
7
8
9

/* 删除给定节点的下一个节点 */
void RemoveNode<T>(LinkedNode<T> node)
{
	if (node.Next == null)  // 如果下一个节点不存在
		return;
	var middleNode = node.Next;
	var nextNode = middleNode.Next;
	node.Next = nextNode;
}

访问

链表的短板在于访问节点的效率较低，为了访问给定索引的节点，往往需要以O(n)的时间复杂度进行。

1
2
3
4
5
6
7
8
9
10
11
12

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>

双链表仅仅是比单链表多保存了个引用（指向上一个节点），从而允许任一节点返回到上个节点。

在.NET中，可以使用LinkedList<T>来使用双链表。

通过查看相关源代码实现，会发现LinkedList<T>提供了AddAfter和AddBefore方法。

1
2
3
4
5
6
7
8
9
10

var linkedList = new LinkedList<int>();

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

var secondNode = new LinkedListNode<int>(4);
linkedList.AddAfter(firstNode, secondNode);  // 1 4

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

常用链表类型

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

链表的应用

工程项目中，用到链表的场景很少，更不用说实现一个链表了

单链表

• 栈和队列
  • 栈：由于先进后出的特性，可以使用单链表在一端新增和删除
  • 队列：由于先进先出的特性，可以使用单链表在一端新增，另一端删除
• 解决哈希表的哈希冲突：链式地址。冲突的元素会被放到所在位置的链表中。
• 通过邻接表来表示图：图的每个顶点与一个链表关联，链表中的每个元素代表了该顶点与其他顶点相连。

双链表

• 浏览器历史浏览保存：网页的前进与后退，对应双链表记录前后节点的特性。

环形链表

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