## 单链表实现与核心操作 ### 1. 基础结构设计 链表由节点（Node）组成，每个节点包含数据域和指向下一个节点的指针域。 ```python class Node: """链表节点类""" def __init__(self, data): self.data = data # 节点存储的数据 self.next = None # 指向下一个节点的指针 class LinkedList: """单链表类""" def __init__(self): self.head = None # 链表头节点 ``` ### 2. 核心操作方法 #### 2.1 插入操作 | 操作类型 | 时间复杂度 | 适用场景 | |---------|-----------|---------| | 头部插入 | O(1) | 需要快速在开头添加数据 | | 尾部插入 | O(n) | 维护数据顺序，类似队列 | | 指定位置插入 | O(n) | 在特定位置插入数据 | ```python def append(self, data): """尾部追加节点""" new_node = Node(data) if not self.head: # 空链表情况 self.head = new_node return current = self.head while current.next: # 遍历到链表末尾 current = current.next current.next = new_node def prepend(self, data): """头部插入节点""" new_node = Node(data) new_node.next = self.head self.head = new_node def insert_after(self, prev_node, data): """在指定节点后插入""" if not prev_node: print("前驱节点不能为空") return new_node = Node(data) new_node.next = prev_node.next prev_node.next = new_node ``` #### 2.2 删除操作 ```python def delete_node(self, key): """删除指定值的节点""" current = self.head # 删除头节点的情况 if current and current.data == key: self.head = current.next current = None return prev = None while current and current.data != key: prev = current current = current.next if not current: # 未找到节点 return prev.next = current.next current = None def delete_at_position(self, position): """删除指定位置的节点""" if not self.head: return current = self.head # 删除头节点 if position == 0: self.head = current.next current = None return # 找到要删除节点的前一个节点 for _ in range(position - 1): current = current.next if not current: return if not current.next: # 位置超出链表长度 return next_node = current.next.next current.next = None current.next = next_node ``` #### 2.3 查找与遍历 ```python def search(self, key): """查找节点是否存在""" current = self.head while current: if current.data == key: return True current = current.next return False def get_length(self): """获取链表长度""" count = 0 current = self.head while current: count += 1 current = current.next return count def print_list(self): """遍历打印链表""" current = self.head while current: print(current.data, end=" -> ") current = current.next print("None") ``` ### 3. 应用实例：任务管理系统 ```python class TaskManager: """基于链表的任务管理系统""" def __init__(self): self.tasks = LinkedList() def add_task(self, task_name, priority='normal'): """添加新任务""" task = { 'name': task_name, 'priority': priority, 'status': 'pending' } # 高优先级任务插入头部 if priority == 'high': self.tasks.prepend(task) else: self.tasks.append(task) def complete_task(self, task_name): """标记任务完成""" current = self.tasks.head while current: if current.data['name'] == task_name: current.data['status'] = 'completed' print(f"任务 '{task_name}' 已完成") return current = current.next print(f"未找到任务: {task_name}") def show_tasks(self): """显示所有任务""" print("\n=== 当前任务列表 ===") current = self.tasks.head index = 1 while current: task = current.data status_icon = '✓' if task['status'] == 'completed' else '○' print(f"{index}. [{status_icon}] {task['name']} ({task['priority']})") current = current.next index += 1 # 使用示例 manager = TaskManager() manager.add_task("写报告", "high") manager.add_task("开会", "normal") manager.add_task("检查邮件", "low") manager.show_tasks() manager.complete_task("写报告") manager.show_tasks() ``` ### 4. 性能对比分析 | 操作 | 数组 | 链表 | 说明 | |------|------|------|------| | 随机访问 | O(1) | O(n) | 链表需要遍历 | | 头部插入 | O(n) | O(1) | 链表优势明显 | | 尾部插入 | O(1)* | O(n) | *数组在空间足够时 | | 内存使用 | 连续 | 分散 | 链表更灵活 | ### 5. 高级操作示例 ```python def reverse(self): """反转链表""" prev = None current = self.head while current: next_node = current.next current.next = prev prev = current current = next_node self.head = prev def detect_cycle(self): """检测链表是否有环（Floyd算法）""" slow = self.head fast = self.head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False def merge_sorted_lists(self, other_list): """合并两个有序链表""" dummy = Node(0) tail = dummy l1 = self.head l2 = other_list.head while l1 and l2: if l1.data <= l2.data: tail.next = l1 l1 = l1.next else: tail.next = l2 l2 = l2.next tail = tail.next tail.next = l1 if l1 else l2 merged_list = LinkedList() merged_list.head = dummy.next return merged_list ``` ### 6. 实际应用场景 1. **浏览器历史记录**：使用双向链表实现前进后退功能 2. **音乐播放列表**：链表适合频繁插入删除操作 3. **撤销操作栈**：每个操作作为节点，支持多级撤销 4. **内存管理**：操作系统使用链表管理空闲内存块 5. **图算法**：邻接表表示法使用链表存储边 ### 7. 最佳实践建议 1. **边界条件处理**：始终检查空链表、头尾节点等特殊情况 2. **内存管理**：Python有垃圾回收，但显式设置`None`有助于逻辑清晰 3. **复杂度分析**：根据操作频率选择合适的数据结构 4. **测试覆盖**：编写单元测试验证各种边界情况 ```python # 测试用例示例 def test_linked_list(): ll = LinkedList() assert ll.get_length() == 0 ll.append(1) ll.append(2) ll.prepend(0) assert ll.get_length() == 3 assert ll.search(1) == True assert ll.search(5) == False ll.delete_node(1) assert ll.get_length() == 2 print("所有测试通过！") ``` 链表在需要频繁插入删除的场景中表现优异，但随机访问效率较低。理解其实现原理和时间复杂度对算法优化至关重要 [ref_1][ref_2][ref_4]。在实际开发中，Python内置的`collections.deque`提供了双向链表的实现，在大多数情况下是更好的选择。