-
第5章 链表
第5章 链表
5.1 引言
在第3章中，我们讨论了数组与Python列表的底层实现——它们依赖连续的内存空间存储元素，从而实现高效的随机访问（时间复杂度O(1)）。但连续存储的特性也带来了局限性：当需要频繁在中间或头部插入/删除元素时，需移动大量元素（时间复杂度O(n)）；且动态扩容时需申请新内存并复制元素，存在性能开销。
链表（Linked List） 作为另一种线性数据结构，通过离散内存存储和指针/引用连接的方式突破了这些限制。链表中的元素（称为“节点”）不必连续存储，每个节点包含数据域和指针域：数据域存储元素值，指针域存储下一个（或上一个）节点的地址。这种结构使得链表的插入、删除操作在已知节点位置时可达到O(1)时间复杂度，且内存分配更加灵活（无需预分配连续空间）。
本章将从链表的定义与类型出发，详细讲解单链表、双链表的Python实现，深入分析核心操作的底层原理，并通过“反转链表”“环检测”等典型问题展示其工程应用，最终对比链表与数组的适用场景，帮助读者建立“数据结构选择”的工程思维。
5.2 链表的定义与类型
5.2.1 链表的基本定义
定义5.1 链表：由有限个节点（Node）组成的线性数据结构，节点间通过指针/引用连接，形成逻辑上的连续序列。
节点（Node）：链表的基本单元，包含两部分：
o数据域（Data）：存储元素的值（如整数、字符串、对象等）；
o指针域（Pointer/Reference）：存储相邻节点的地址（在Python中表现为对象引用）。
头节点（Head Node）：链表的第一个节点，是访问整个链表的入口（若链表为空，头节点为None）。
尾节点（Tail Node）：链表的最后一个节点，其指针域通常指向None（非循环链表）。
5.2.2 链表的核心特性
与数组对比，链表的核心特性可总结为：
特性 链表（离散存储） 数组（连续存储）
内存分配 动态分配，无需连续空间 需预分配连续空间，大小固定或动态扩容
随机访问 不支持，需从头部遍历（O(n)） 支持，通过索引直接访问（O(1)）
插入/删除（已知位置） O(1)（仅需修改指针） O(n)（需移动大量元素）
空间效率 需额外存储指针（如单链表每个节点多一个引用） 无额外开销，空间利用率高
5.2.3 链表的常见类型
根据节点指针的数量和连接方式，链表可分为以下几类：
-
单链表（Singly Linked List）
结构：每个节点仅包含一个指针域（next），指向后一个节点；尾节点的next为None。
特点：结构简单，实现容易，但只能从头部向尾部遍历，无法反向访问。
图示：
Head → Node1(data1, next) → Node2(data2, next) → ... → NodeN(dataN, None) -
双链表（Doubly Linked List）
结构：每个节点包含两个指针域：prev（指向前一个节点）和next（指向后一个节点）；头节点的prev为None，尾节点的next为None。
特点：支持双向遍历，插入/删除操作更灵活（可通过prev指针直接访问前驱节点），但需额外存储prev指针，内存开销略大。
图示：
None ← Head.prev ← Node1(prev, data1, next) ↔ Node2(prev, data2, next) ↔ ... ↔ NodeN(prev, dataN, next) → None -
循环链表（Circular Linked List）
结构：尾节点的指针域不指向None，而是指向头节点（单循环链表）或其他节点（如双循环链表的尾节点next指向头节点，头节点prev指向尾节点）。
特点：可从任意节点开始遍历整个链表，适合实现“环形缓冲区”等场景（如操作系统的进程调度队列）。
5.3 单链表的实现与核心操作
单链表是最基础的链表类型，其实现仅需关注next指针的维护。本节通过Python实现单链表，并详细讲解核心操作的步骤与边界情况处理。
5.3.1 单链表节点定义
首先定义单链表的节点类，包含数据域（data）和指针域（next）：
python
class ListNode:
"""单链表节点类"""
def __init__(self, data):
self.data = data # 数据域
self.next = None # 指针域（初始指向None）
def __str__(self):
"""节点数据的字符串表示"""
return str(self.data)
5.3.2 单链表的基本实现
单链表类需支持初始化、判空、求长度、插入（头插/尾插/指定位置插入）、删除、查找、遍历等核心操作。以下是完整实现：
python
class SinglyLinkedList:
"""单链表类"""
def __init__(self):
self.head = None # 头节点（初始为空）
self._size = 0 # 链表长度（元素个数）
def is_empty(self):
"""判断链表是否为空"""
return self.head is None
def size(self):
"""返回链表长度"""
return self._size
def traverse(self):
"""遍历链表，返回元素列表（从头部到尾部）"""
result = []
current = self.head # 从头部开始遍历
while current:
result.append(current.data)
current = current.next # 移动到下一个节点
return result
def head_insert(self, data):
"""头插法：在链表头部插入新节点（时间复杂度O(1)）"""
new_node = ListNode(data)
new_node.next = self.head # 新节点next指向原头节点
self.head = new_node # 更新头节点为新节点
self._size += 1
def tail_insert(self, data):
"""尾插法：在链表尾部插入新节点（时间复杂度O(n)，需遍历到尾节点）"""
new_node = ListNode(data)
if self.is_empty():
# 空链表：直接将头节点指向新节点
self.head = new_node
else:
# 非空链表：遍历到尾节点（next为None的节点）
current = self.head
while current.next: # 注意：循环条件是current.next不为空
current = current.next
current.next = new_node # 尾节点next指向新节点
self._size += 1
def insert(self, index, data):
"""指定位置插入：在索引index处插入新节点（索引从0开始，时间复杂度O(n)）"""
if index < 0 or index > self._size:
raise IndexError("插入索引越界（索引范围：0~size）")
if index == 0:
# 索引0：头插法
self.head_insert(data)
elif index == self._size:
# 索引size：尾插法
self.tail_insert(data)
else:
# 中间位置：遍历到index-1处的节点（前驱节点）
current = self.head
for _ in range(index - 1):
current = current.next
new_node = ListNode(data)
new_node.next = current.next # 新节点next指向前驱节点的原next
current.next = new_node # 前驱节点next指向新节点
self._size += 1
def delete_head(self):
"""删除头节点（时间复杂度O(1)）"""
if self.is_empty():
raise IndexError("删除空链表节点")
# 头节点指向原头节点的next
self.head = self.head.next
self._size -= 1
def delete_tail(self):
"""删除尾节点（时间复杂度O(n)，需遍历到倒数第二个节点）"""
if self.is_empty():
raise IndexError("删除空链表节点")
if self._size == 1:
# 只有一个节点：直接将头节点置为None
self.head = None
else:
# 遍历到倒数第二个节点（current.next.next为None）
current = self.head
while current.next.next:
current = current.next
current.next = None # 倒数第二个节点next置为None（原尾节点被删除）
self._size -= 1
def delete(self, index):
"""删除指定索引处的节点（索引从0开始，时间复杂度O(n)）"""
if index < 0 or index >= self._size:
raise IndexError("删除索引越界（索引范围：0~size-1）")
if index == 0:
# 删除头节点
self.delete_head()
elif index == self._size - 1:
# 删除尾节点
self.delete_tail()
else:
# 中间位置：遍历到index-1处的前驱节点
current = self.head
for _ in range(index - 1):
current = current.next
# 前驱节点next指向待删除节点的next
current.next = current.next.next
self._size -= 1
def find(self, data):
"""查找第一个值为data的节点，返回索引（未找到返回-1，时间复杂度O(n)）"""
current = self.head
index = 0
while current:
if current.data == data:
return index
current = current.next
index += 1
return -1
def __str__(self):
"""链表的字符串表示（格式：Head → data1 → data2 → ... → None）"""
if self.is_empty():
return "Head → None"
result = ["Head"]
current = self.head
while current:
result.append(str(current.data))
current = current.next
result.append("None")
return " → ".join(result)
5.3.3 单链表操作示例与解析
基本操作示例
python
if __name__ == "__main__":
# 初始化空链表
sll = SinglyLinkedList()
print("初始链表:", sll) # 输出：Head → None
# 尾插操作
sll.tail_insert(10)
sll.tail_insert(20)
sll.tail_insert(30)
print("尾插后:", sll) # 输出：Head → 10 → 20 → 30 → None
print("链表长度:", sll.size()) # 输出：3
# 头插操作
sll.head_insert(5)
print("头插5后:", sll) # 输出：Head → 5 → 10 → 20 → 30 → None
# 指定位置插入
sll.insert(2, 15) # 在索引2处插入15（位于10和20之间）
print("插入15后:", sll) # 输出：Head → 5 → 10 → 15 → 20 → 30 → None
# 查找元素
print("查找20的索引:", sll.find(20)) # 输出：4
# 删除操作
sll.delete(3) # 删除索引3处的20
print("删除索引3后:", sll) # 输出：Head → 5 → 10 → 15 → 30 → None
sll.delete_tail() # 删除尾节点30
print("删除尾节点后:", sll) # 输出：Head → 5 → 10 → 15 → None
核心操作解析
头插法（head_insert）：
无需遍历链表，直接创建新节点并将其next指向原头节点，再更新头节点为新节点，时间复杂度O(1)。适合需要频繁在头部插入元素的场景（如实现栈）。
尾插法（tail_insert）：
必须遍历到尾节点（current.next is None），才能将其next指向新节点，时间复杂度O(n)。若需频繁尾插，可通过维护“尾指针”（记录尾节点地址）将时间复杂度优化为O(1)（见5.3.4节扩展）。
指定位置插入/删除：
需先遍历到目标位置的前驱节点（索引index-1），再修改指针完成操作。遍历过程耗时O(n)，因此整体时间复杂度O(n)。
边界情况处理：
对空链表、只有一个节点的链表、插入/删除头节点/尾节点等场景需特殊处理，避免出现AttributeError（如访问None.next）。
5.3.4 单链表的优化：维护尾指针
标准单链表的尾插操作需遍历到尾节点（O(n)），若在链表类中增加一个tail指针记录尾节点地址，可将尾插优化为O(1)：
python
class OptimizedSinglyLinkedList(SinglyLinkedList):
"""带尾指针的单链表（优化尾插操作）"""
def __init__(self):
super().__init__()
self.tail = None # 尾指针（初始为空）
def head_insert(self, data):
"""头插：需同步更新尾指针（若原链表为空）"""
new_node = ListNode(data)
new_node.next = self.head
self.head = new_node
if self.tail is None: # 原链表为空，尾指针指向新节点
self.tail = new_node
self._size += 1
def tail_insert(self, data):
"""尾插：直接通过尾指针操作（O(1)）"""
new_node = ListNode(data)
if self.is_empty():
# 空链表：头、尾指针均指向新节点
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node # 尾节点next指向新节点
self.tail = new_node # 更新尾指针为新节点
self._size += 1
def delete_tail(self):
"""删除尾节点：需遍历到倒数第二个节点（仍为O(n)，因无法通过尾指针直接获取前驱）"""
if self.is_empty():
raise IndexError("删除空链表节点")
if self._size == 1:
# 只有一个节点：头、尾指针均置空
self.head = None
self.tail = None
else:
# 遍历到倒数第二个节点
current = self.head
while current.next != self.tail:
current = current.next
current.next = None # 倒数第二个节点next置空
self.tail = current # 更新尾指针
self._size -= 1
说明：尾指针可优化尾插操作，但无法优化尾删（因单链表无prev指针，仍需遍历到前驱节点），这也体现了单链表在反向操作上的局限性——双链表的价值正在于此。
5.4 双链表的实现与核心操作
双链表通过增加prev指针，允许节点访问前驱和后继，从而优化了反向遍历、尾部删除等操作。本节实现双链表并对比其与单链表的差异。
5.4.1 双链表节点定义
双链表节点需包含prev（指向前驱节点）和next（指向后继节点）两个指针域：
python
class DoublyListNode:
"""双链表节点类"""
def __init__(self, data):
self.data = data # 数据域
self.prev = None # 前驱指针（指向前一个节点）
self.next = None # 后继指针（指向后一个节点）
def __str__(self):
return str(self.data)
5.4.2 双链表的基本实现
双链表的核心操作与单链表类似，但需同时维护prev和next指针，确保链表的双向连接性。以下是完整实现：
python
class DoublyLinkedList:
"""双链表类"""
def __init__(self):
self.head = None # 头节点
self.tail = None # 尾节点（维护尾指针，优化尾操作）
self._size = 0 # 链表长度
def is_empty(self):
return self.head is None
def size(self):
return self._size
def traverse_forward(self):
"""正向遍历（从头部到尾部）"""
result = []
current = self.head
while current:
result.append(current.data)
current = current.next
return result
def traverse_backward(self):
"""反向遍历（从尾部到头部，双链表特有）"""
result = []
current = self.tail
while current:
result.append(current.data)
current = current.prev
return result
def head_insert(self, data):
"""头插法（O(1)）"""
new_node = DoublyListNode(data)
if self.is_empty():
# 空链表：头、尾指针均指向新节点
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head # 新节点next指向原头节点
self.head.prev = new_node # 原头节点prev指向新节点
self.head = new_node # 更新头节点为新节点
self._size += 1
def tail_insert(self, data):
"""尾插法（O(1)，通过尾指针实现）"""
new_node = DoublyListNode(data)
if self.is_empty():
self.head = new_node
self.tail = new_node
else:
new_node.prev = self.tail # 新节点prev指向原尾节点
self.tail.next = new_node # 原尾节点next指向新节点
self.tail = new_node # 更新尾节点为新节点
self._size += 1
def insert(self, index, data):
"""指定位置插入（O(n)，需遍历到目标位置）"""
if index < 0 or index > self._size:
raise IndexError("插入索引越界（0~size）")
if index == 0:
self.head_insert(data)
elif index == self._size:
self.tail_insert(data)
else:
# 遍历到目标位置的前驱节点（根据索引选择更近的遍历方向，优化效率）
if index <= self._size // 2:
# 索引在前半段：从头部遍历
current = self.head
for _ in range(index - 1):
current = current.next
else:
# 索引在后半段：从尾部遍历（双链表优势）
current = self.tail
for _ in range(self._size - index):
current = current.prev
# 插入新节点（需同时修改prev和next）
new_node = DoublyListNode(data)
new_node.prev = current # 新节点prev指向前驱
new_node.next = current.next # 新节点next指向后继
current.next.prev = new_node # 后继节点prev指向新节点
current.next = new_node # 前驱节点next指向新节点
self._size += 1
def delete_head(self):
"""删除头节点（O(1)）"""
if self.is_empty():
raise IndexError("删除空链表节点")
if self._size == 1:
# 只有一个节点：头、尾指针均置空
self.head = None
self.tail = None
else:
self.head = self.head.next # 头节点指向原头节点的next
self.head.prev = None # 新头节点prev置空
self._size -= 1
def delete_tail(self):
"""删除尾节点（O(1)，双链表优势）"""
if self.is_empty():
raise IndexError("删除空链表节点")
if self._size == 1:
self.head = None
self.tail = None
else:
self.tail = self.tail.prev # 尾节点指向原尾节点的prev
self.tail.next = None # 新尾节点next置空
self._size -= 1
def delete(self, index):
"""指定位置删除（O(n)）"""
if index < 0 or index >= self._size:
raise IndexError("删除索引越界（0~size-1）")
if index == 0:
self.delete_head()
elif index == self._size - 1:
self.delete_tail()
else:
# 遍历到目标节点（可优化为从近的一端遍历）
if index <= self._size // 2:
current = self.head
for _ in range(index):
current = current.next
else:
current = self.tail
for _ in range(self._size - 1 - index):
current = current.prev
# 删除当前节点：修改前驱和后继的指针
prev_node = current.prev
next_node = current.next
prev_node.next = next_node # 前驱节点next指向后继
next_node.prev = prev_node # 后继节点prev指向前驱
self._size -= 1
def __str__(self):
"""双链表的字符串表示（正向）"""
if self.is_empty():
return "Head ↔ Tail → None"
result = ["Head"]
current = self.head
while current:
result.append(str(current.data))
current = current.next
result.append("None")
return " ↔ ".join(result)
5.4.3 双链表的优势与适用场景
对比单链表，双链表的核心优势体现在：
1. **反向遍历与操作**：支持从尾部向头部遍历（`traverse_backward`），便于实现“逆序处理”场景（如逆序打印链表）。
2. **高效的尾部删除**：通过`tail.prev`可直接访问尾节点的前驱，删除尾节点时间复杂度O(1)（单链表需O(n)）。
3. **插入/删除优化**：指定位置操作时，可根据索引与链表中点的距离选择从头部或尾部遍历，减少遍历次数（如索引为n-2时，从尾部遍历只需1步）。
**适用场景**：需频繁在头部/尾部插入删除、需要双向遍历的场景（如实现双端队列、LRU缓存淘汰算法等）。
5.5 链表的典型应用
链表的动态特性使其在算法设计中应用广泛，本节聚焦两个经典问题：单链表反转与环检测，深入分析其底层原理与工程实现。
5.5.1 应用一：单链表反转
**问题描述**：给定单链表的头节点，将链表反转（如原链表为`1→2→3→None`，反转后为`3→2→1→None`）。
方法一：迭代法（推荐，空间复杂度O(1)）
**核心思想**：通过三个指针（`prev`、`current`、`next`）逐步反转节点的`next`指针方向，遍历一次完成反转。
**步骤**：
1. 初始化`prev = None`（反转后链表的头节点初始为`None`），`current = head`（当前节点从原头节点开始）。
2. 遍历链表：
- 记录`current.next`到`next`（避免修改后丢失原后继节点）；
- 将`current.next`指向`prev`（反转指针）；
- 更新`prev = current`、`current = next`（移动指针）。
3. 遍历结束后，`prev`即为反转后链表的头节点。
**代码实现**：
python
def reverse_singly_linked_list(head):
"""迭代法反转单链表，返回反转后链表的头节点"""
prev = None
current = head
while current:
next_node = current.next # 步骤1：保存原next
current.next = prev # 步骤2：反转current.next
prev = current # 步骤3：prev移动到current
current = next_node # 步骤4：current移动到next_node
return prev # 遍历结束后，prev为新头节点
# 测试示例
if __name__ == "__main__":
# 构建原链表：1→2→3→4→None
sll = SinglyLinkedList()
for num in [1, 2, 3, 4]:
sll.tail_insert(num)
print("原链表:", sll) # 输出：Head → 1 → 2 → 3 → 4 → None
# 反转链表
new_head = reverse_singly_linked_list(sll.head)
# 构建反转后的链表（仅为打印，实际工程中可直接操作头节点）
reversed_sll = SinglyLinkedList()
reversed_sll.head = new_head
reversed_sll._size = sll.size() # 手动同步长度（实际实现中需维护）
print("反转后:", reversed_sll) # 输出：Head → 4 → 3 → 2 → 1 → None
复杂度分析：时间复杂度O(n)（遍历一次链表），空间复杂度O(1)（仅用三个指针）。
方法二：递归法（理解递归思想，空间复杂度O(n)）
核心思想：递归到链表尾部，然后从后向前逐步反转指针（本质是利用递归栈保存节点引用）。
代码实现：
python
def reverse_singly_linked_list_recursive(head):
"""递归法反转单链表"""
# 基准情况：空链表或只有一个节点，直接返回head
if head is None or head.next is None:
return head
# 递归反转剩余链表（假设从head.next开始的链表已反转完成，返回新头节点new_head）
new_head = reverse_singly_linked_list_recursive(head.next)
# 反转当前节点与后继节点的指针
head.next.next = head # 后继节点的next指向当前节点
head.next = None # 当前节点的next置空（避免成环）
return new_head # 返回新头节点（原尾节点）
说明：递归法逻辑简洁，但递归栈深度为O(n)，空间复杂度较高，实际工程中优先选择迭代法。
5.5.2 应用二：单链表环检测
问题描述：判断一个单链表是否存在环（即尾节点的next指向链表中的某个节点，形成环形结构）。
方法：快慢指针法（Floyd's Tortoise and Hare Algorithm）
核心思想：设置两个指针——慢指针（slow）每次走1步，快指针（fast）每次走2步。若链表存在环，两指针终将在环内相遇；若不存在环，快指针会先到达None。
原理：若环长为L，当慢指针进入环时，快指针已在环内领先d步（d < L）。由于快指针比慢指针快1步/次，每走一次两指针距离减少1，最终会相遇（距离为0）。
代码实现：
python
def has_cycle(head):
"""判断单链表是否有环，返回True/False"""
if head is None or head.next is None:
return False # 空链表或只有一个节点，无环
slow = head.next # 慢指针初始走1步
fast = head.next.next # 快指针初始走2步
while fast and fast.next:
if slow == fast:
return True # 相遇，有环
slow = slow.next # 慢指针走1步
fast = fast.next.next # 快指针走2步
return False # 快指针到达None，无环
# 测试示例
if __name__ == "__main__":
# 构建有环链表：1→2→3→4→2（环从4指向2）
head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
head.next = node2
node2.next = node3
node3.next = node4
node4.next = node2 # 形成环（4→2）
print("有环链表检测:", has_cycle(head)) # 输出：True
# 构建无环链表：1→2→3→4→None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
print("无环链表检测:", has_cycle(head)) # 输出：False
扩展：若需找到环的入口节点，可在两指针相遇后，将慢指针重置为头节点，两指针均以1步/次前进，再次相遇的节点即为环入口（证明略，可参考算法导论相关章节）。
5.6 本章总结
链表的本质：通过离散节点和指针连接实现线性结构，突破连续内存限制，插入/删除操作（已知位置）时间复杂度O(1)，但随机访问能力弱（O(n)）。
核心类型：
o单链表：仅含next指针，实现简单但反向操作低效；
o双链表：含prev和next指针，支持双向遍历和高效尾部操作，适合复杂场景；
o循环链表：尾节点指向头节点，适合环形数据处理（如约瑟夫问题）。
实现要点：
o单链表需重点维护头节点，尾插可通过尾指针优化为O(1)；
o双链表需同时维护prev和next指针，确保插入删除时指针关系正确；
o边界情况（空链表、单节点链表、头/尾操作）需特殊处理，避免空指针异常。
典型应用：
o单链表反转：迭代法（三指针）或递归法，迭代法空间效率更优；
o环检测：快慢指针法，通过指针速度差判断是否有环，时间复杂度O(n)，空间复杂度O(1)。
链表作为动态数据结构的基础，其“指针操作”思想是理解树、图等复杂数据结构的关键。在工程实践中，需根据场景权衡链表与数组的取舍：需频繁随机访问时选数组，需频繁插入删除时选链表。
思考题
1.
设计一个函数，合并两个有序单链表（假设升序），返回合并后的有序链表（要求时间复杂度O(n+m)，空间复杂度O(1)，不得创建新节点，仅调整指针）。
给定单链表的头节点，求链表的中间节点（若长度为偶数，返回第二个中间节点）。要求时间复杂度O(n)，空间复杂度O(1)（提示：快慢指针）。
实现一个LRU缓存淘汰算法（最近最少使用），要求get和put操作的时间复杂度均为O(1)（提示：用哈希表+双链表，哈希表记录键到节点的映射，双链表维护节点访问顺序）。
如何判断两个单链表是否相交（即存在公共节点，且从公共节点开始后续节点完全相同）？若相交，求出第一个公共节点。
本站原创，转载请注明出处：https://www.xin3721.com/python3/python49291.html
