链表是一种基础的数据结构，它通过节点（Node）的序列来存储数据，每个节点包含数据域和指向下一个节点的指针（在单链表中）。与数组不同，链表在内存中是非连续存储的，这使得它在插入和删除操作上通常具有更高的效率，但访问特定位置的元素则相对较慢 [ref_1]。在Python中，虽然内置的`list`类型功能强大，但理解并手动实现链表对于深入掌握数据结构和算法至关重要 [ref_3]。 ### 1. 链表节点的定义 链表的构建始于节点。每个节点是一个独立的对象，包含数据（`data`）和指向下一个节点的引用（`next`）。 ```python class Node: """链表节点类""" def __init__(self, data): self.data = data # 存储节点数据 self.next = None # 指向下一个节点的指针，初始为None ``` 这个`Node`类是构成链表的基本单元 [ref_1][ref_4]。 ### 2. 链表类的定义与初始化 接下来，我们定义一个链表类`LinkedList`来管理这些节点。链表类通常维护一个头节点（`head`），它是访问整个链表的起点。 ```python class LinkedList: """单链表类""" def __init__(self): self.head = None # 链表头指针，初始为空链表 ``` 初始化时，`head`为`None`，表示一个空链表 [ref_4]。 ### 3. 增删查改操作详解 以下将详细说明链表的四种基本操作，并对比其特点。 | 操作 | 方法名 (示例) | 核心思想 | 时间复杂度 | 关键步骤 | | :--- | :--- | :--- | :--- | :--- | | **增 (Insert)** | `insert_at_beginning`, `insert_at_end`, `insert_after_node` | 创建新节点，调整指针指向 | O(1) 或 O(n) | 1. 创建新节点<br>2. 新节点`next`指向原后继<br>3. 原前驱`next`指向新节点 | | **删 (Delete)** | `delete_node` | 找到目标节点，绕过它连接前后节点 | O(n) | 1. 遍历找到目标节点及其前驱<br>2. 前驱`next`指向目标`next`<br>3. (可选) 删除目标节点 | | **查 (Search)** | `search` | 从头遍历，比较数据 | O(n) | 1. 从`head`开始遍历<br>2. 比较每个节点的`data`<br>3. 返回找到的节点或`None` | | **改 (Update)** | `update` | 结合“查”与节点赋值 | O(n) | 1. 使用查找定位节点<br>2. 修改该节点的`data`值 | #### 3.1 增加操作 增加操作主要有三种：在头部插入、在尾部插入和在指定节点后插入。 * **头部插入**：时间复杂度为O(1)。 ```python def insert_at_beginning(self, new_data): """在链表头部插入新节点""" new_node = Node(new_data) # 1. 创建新节点 new_node.next = self.head # 2. 新节点指向原头节点 self.head = new_node # 3. 更新头节点为新节点 ``` 这种方法效率最高，因为不涉及遍历 [ref_4]。 * **尾部插入**：需要遍历到链表末尾，时间复杂度为O(n)。 ```python def insert_at_end(self, new_data): """在链表尾部插入新节点""" new_node = Node(new_data) if self.head is None: # 如果链表为空，新节点即为头节点 self.head = new_node return last = self.head while last.next: # 遍历到最后一个节点 last = last.next last.next = new_node # 原尾节点的next指向新节点 ``` * **在指定节点后插入**：首先需要找到该节点，然后调整指针。 ```python def insert_after_node(self, prev_node, new_data): """在给定的prev_node节点之后插入新节点""" if prev_node is None: print("前一个节点不能为空。") return new_node = Node(new_data) new_node.next = prev_node.next # 新节点指向原后继 prev_node.next = new_node # 前驱节点指向新节点 ``` #### 3.2 删除操作 删除操作需要找到待删除节点的前一个节点，修改其`next`指针以“跳过”待删除节点 [ref_4]。 ```python def delete_node(self, key): """删除第一个包含指定数据的节点""" temp = self.head # 情况1：要删除的节点是头节点 if temp is not None and temp.data == key: self.head = temp.next # 将头指针指向第二个节点 temp = None # 释放原头节点内存 (Python中为可选) return # 情况2：要删除的节点在中间或末尾 prev = None while temp is not None and temp.data != key: prev = temp temp = temp.next # 如果没找到包含key的节点 if temp is None: print(f"未找到数据为 {key} 的节点。") return # 找到节点，执行删除 prev.next = temp.next # 前驱节点直接指向待删除节点的后继 temp = None # 释放节点内存 ``` 此操作需要遍历链表，平均时间复杂度为O(n) [ref_3]。 #### 3.3 查找操作 查找操作通过遍历链表，比较每个节点的数据来实现 [ref_3]。 ```python def search(self, key): """查找链表中是否存在包含指定数据的节点""" current = self.head while current is not None: if current.data == key: return True # 找到数据 current = current.next return False # 遍历完毕未找到 ``` 查找操作必须从头开始，时间复杂度为O(n)。 #### 3.4 修改操作 修改操作通常是查找和赋值两个动作的结合。 ```python def update(self, old_data, new_data): """将链表中第一个等于old_data的节点值更新为new_data""" current = self.head while current is not None: if current.data == old_data: current.data = new_data # 找到节点，直接修改其数据域 print(f"已将数据 {old_data} 更新为 {new_data}。") return current = current.next print(f"未找到数据为 {old_data} 的节点，更新失败。") ``` 其时间复杂度同样为O(n)，因为它依赖于查找过程。 ### 4. 完整示例与测试 下面是一个将上述操作整合并测试的完整示例： ```python # 定义 Node 和 LinkedList 类 (此处省略，同上文) if __name__ == "__main__": # 创建链表 llist = LinkedList() # 测试插入操作 llist.insert_at_end(10) llist.insert_at_beginning(5) llist.insert_at_end(20) llist.insert_after_node(llist.head.next, 15) # 在10后面插入15 # 此时链表应为：5 -> 10 -> 15 -> 20 # 测试遍历打印 (辅助函数) def print_list(linked_list): temp = linked_list.head while temp: print(temp.data, end=" -> ") temp = temp.next print("None") print("初始链表：") print_list(llist) # 输出：5 -> 10 -> 15 -> 20 -> None # 测试查找操作 print("\n查找元素 15:", llist.search(15)) # 输出：True print("查找元素 99:", llist.search(99)) # 输出：False # 测试删除操作 llist.delete_node(10) print("\n删除 10 后的链表：") print_list(llist) # 输出：5 -> 15 -> 20 -> None # 测试修改操作 llist.update(15, 100) print("\n修改 15 为 100 后的链表：") print_list(llist) # 输出：5 -> 100 -> 20 -> None ``` ### 5. 应用场景与总结 链表在以下场景中尤为有用：1) **频繁的插入和删除**：例如实现队列、栈或需要动态调整大小的列表；2) **内存管理**：当无法预知数据总量或需要避免大块连续内存分配时 [ref_2]。然而，链表的缺点在于**无法进行高效的随机访问**，访问第k个元素必须从头遍历。 理解并实现链表的增删查改是学习更复杂数据结构（如双向链表、循环链表、树和图）的基础 [ref_5]。通过手动实现，可以更深刻地理解指针（引用）操作和动态数据管理的精髓。