登录链表LinkedList
更新: 2025/2/24 字数: 0 字 时长: 0 分钟
内存空间是所有程序的公共资源，在一个复杂的系统运行环境下，空闲的内存空间可能散落在内存各处。我们知道，存储数组的内存空间必须是连续的，而当数组非常大时，内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。
链表简介
数据结构
链表（Linked List）是一种线性数据结构，其中的每个元素都是一个节点对象（Node），各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。这种设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。
建议
图中浅蓝色的存储节点指针是占用一块内存地址吗？还是和节点值各占一半呢？该示意图只是定性表示，定量表示需要根据具体情况进行分析。不同类型的节点值占用的空间是不同的，比如 int、long、double 和实例对象等。指针变量占用的内存空间大小根据所使用的操作系统及编译环境而定，大多为 8 字节或 4 字节。
节点对象
链表的组成单位是节点对象（Node），每个节点都包含两项数据：节点的“值”和指向下一节点的“引用”。
- 链表的首个节点被称为“头节点”，最后一个节点被称为“尾节点”。
- 尾节点指向的是“空”，它在 Java、C++ 和 Python 中分别被记为
null、nullptr和None。 - 在 C、C++、Go 和 Rust 等支持指针的语言中，上述“引用”应被替换为“指针”。
链表节点 ListNode 除了包含值，还需额外保存一个引用（指针）。因此在相同数据量下，链表比数组占用更多的内存空间。
python
class ListNode:
"""链表节点类"""
def __init__(self, val: int):
self.val: int = val # 节点值
self.next: ListNode | None = None # 指向下一节点的引用链表操作
创建链表
利用上面的 ListNode 链表节点类初始化链表分为如下两步：
- 第一步是初始化各个节点对象。
- 第二步是构建节点之间的引用关系。
python
# 初始化链表 1 -> 3 -> 2 -> 5 -> 4
# 初始化各个节点
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)
# 构建节点之间的引用
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4建议
数组整体是一个变量，比如数组 nums 包含元素 nums[0] 和 nums[1] 等，而链表是由多个独立的节点对象组成的。我们通常将头节点当作链表的代称，比如以上代码中的链表可记作链表 n0 。
建议
链表由节点组成，节点之间通过引用（指针）连接，各个节点可以存储不同类型的数据，例如 int、double、string、object 等。
访问节点
初始化完成后，我们就可以从链表的头节点出发，通过引用指向 next 依次访问所有节点。
python
# 从头节点n0输出三个节点值
print(n0.val) # 输出：1
print(n0.next.val) # 输出：3
print(n0.next.next.val) # 输出：2不过正由于访问节点必须从头节点出发，逐个向后遍历，直至找到目标节点。也就是说，访问链表的第 个节点需要循环 i−1 轮，时间复杂度为 。因此，在链表中访问节点的效率较低。
python
# 访问第i个节点
i = 3
node = n0
# 循环i-1轮
for _ in range(i-1):
node = node.next
print(f'第{i}个节点值为{node.val}。') # 输出：第3个节点值为2。查找节点
遍历链表，查找其中值为 2 的节点，输出该节点在链表中的索引。此过程也属于线性查找。
python
node = n0
index = 0
search_val = 2
while node != None:
if node.val == search_val:
print(f'节点值为{search_val}的节点在链表中的索引为{index}。') # 输出：节点值为2的节点在链表中的索引为2。
break
node = node.next
index += 1
else:
print(f'节点值为{search_val}的节点在链表中不存在。')建议
访问节点的中例子中，第 节点是从 1 开始计数。而查找节点中，节点的索引是从 0 开始计数。
插入节点
在链表中插入节点非常容易。假设我们想在相邻的两个节点 n0 和 n1 之间插入一个新节点 P ，则只需改变两个节点引用（指针）即可，时间复杂度为 。
python
# 插入节点P
p = ListNode(0)
p.next = n1
n0.next = p
# 从头节点n0输出三个节点值
print(n0.val) # 输出：1
print(n0.next.val) # 输出：0
print(n0.next.next.val) # 输出：3
删除节点
在链表中删除节点也非常方便，只需改变一个节点的引用（指针）即可。
python
# 删除节点P
n0.next = n1
# 从头节点n0输出三个节点值
print(n0.val) # 输出：1
print(n0.next.val) # 输出：3
print(n0.next.next.val) # 输出：2
警告
请注意，尽管在删除操作完成后节点 P 仍然指向 n1 ，但实际上遍历此链表已经无法访问到 P ，这意味着 P 已经不再属于该链表了。
链表特点
优点缺点
链表优点：新增节点、删除节点快（在单向链表中，新增一个元素最多只会影响上一个节点，比在数组中的新增效率要高的多）。
链表缺点：查询速度慢，查询从头部开始一直查询到尾部，如果元素刚好是在最尾部那么查询效率势必非常低；链表像对于数组多了一个指针域的开销，内存相对占用会比较大。
总结：数据量较小，需要频繁增加，删除操作的场景，查询操作相对较少场景。
相比数组
总结了数组和链表的各项特点并对比了操作效率。由于它们采用两种相反的存储策略，因此各种性质和操作效率也呈现对立的特点。
| 区别 | 数组 | 链表 |
|---|---|---|
| 元素类型 | 元素必须是一个类型 | 元素可以是不同类型 |
| 存储方式 | 连续内存空间 | 分散内存空间 |
| 容量扩展 | 长度不可变 | 可灵活扩展 |
| 内存效率 | 元素占用内存少，但可能浪费空间。 | 元素占用内存多 |
| 访问元素 | ||
| 添加元素 | ||
| 删除元素 |
链表类型
上面我们介绍了最普通的链表，其实常见的链表类型有如下三种：
- 单向链表：即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空
None。 - 环形链表：如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
- 双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。
python
class ListNode:
"""双向链表节点类"""
def __init__(self, val: int):
self.val: int = val # 节点值
self.next: ListNode | None = None # 指向后继节点的引用
self.prev: ListNode | None = None # 指向前驱节点的引用
链表应用
单向链表通常用于实现栈、队列、哈希表和图等数据结构。
- 栈与队列：当插入和删除操作都在链表的一端进行时，它表现出先进后出的特性，对应栈；当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现出先进先出的特性，对应队列。
- 哈希表：链式地址是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。
- 图：邻接表是表示图的一种常用方式，其中图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点。
双向链表通常用于需要快速查找前一个和后一个元素的场景。
- 高级数据结构：比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
- 浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
- LRU 算法：在缓存淘汰（LRU）算法中，我们需要快速找到最近最少使用的数据，以及支持快速添加和删除节点。这时候使用双向链表就非常合适。
环形链表通常用于需要周期性操作的场景，比如操作系统的资源调度。
- 时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
- 数据缓冲区：在某些数据缓冲区的实现中，也可能会使用环形链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个环形链表，以便实现无缝播放。