Python数据结构实战：链表的构建与操作

Python数据结构实战：链表的构建与操作 一、链表（LinkedList）基础 1. 定义与特性

链表是一种动态数据结构，其特点如下：

元素（节点）通过指针连接，内存空间非连续插入/删除时间复杂度为 O(1)（已知位置时）访问元素时间复杂度为 O(n)无需预先分配内存空间

---

2. 单链表 vs 双链表 类型结构特点单链表节点含 data 和 next 指针单向遍历，内存占用更小双链表节点含 data, prev, next双向遍历，支持反向操作

---

二、单链表实现 1. 节点类定义 class Node: def __init__(self, data): self.data = data # 数据域 self.next = None # 指针域

---

2. 链表类框架 class LinkedList: def __init__(self): self.head = None # 头节点 def is_empty(self): return self.head is None def __len__(self): count = 0 current = self.head while current: count += 1 current = current.next return count def __str__(self): values = [] current = self.head while current: values.append(str(current.data)) current = current.next return " -> ".join(values)

---

3. 核心操作实现 插入操作 # 头部插入 def insert_at_head(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node # 尾部插入 def append(self, data): new_node = Node(data) if self.is_empty(): self.head = new_node return current = self.head while current.next: current = current.next current.next = new_node # 指定位置插入 def insert_at(self, index, data): if index < 0 or index > len(self): raise IndexError("索引超出范围") if index == 0: self.insert_at_head(data) return new_node = Node(data) current = self.head for _ in range(index-1): current = current.next new_node.next = current.next current.next = new_node

---

删除操作 # 删除头部 def delete_head(self): if self.is_empty(): raise Exception("空链表") self.head = self.head.next # 删除尾部 def delete_tail(self): if self.is_empty(): return if self.head.next is None: self.head = None return current = self.head while current.next.next: current = current.next current.next = None # 按值删除 def delete_by_value(self, value): if self.is_empty(): return if self.head.data == value: self.delete_head() return current = self.head while current.next: if current.next.data == value: current.next = current.next.next return current = current.next

---

三、双链表实现（扩展） class DNode: def __init__(self, data): self.data = data self.prev = None self.next = None class DoublyLinkedList: def __init__(self): self.head = None self.tail = None # 实现类似单链表的操作方法（需维护prev指针） # ...

---

四、每日挑战：反转单链表 1. 迭代法实现 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 2. 递归法实现 def reverse_recursive(self, node): if node is None or node.next is None: return node new_head = self.reverse_recursive(node.next) node.next.next = node node.next = None return new_head

---

五、性能对比 操作数组单链表双链表随机访问O(1)O(n)O(n)头部插入O(n)O(1)O(1)尾部插入O(1)O(n)O(1)中间插入O(n)O(n)O(n)内存占用连续非连续非连续

---

六、应用场景 实现栈/队列音乐播放列表浏览器历史记录内存管理系统图算法中的邻接表

---

实战建议：

使用纸笔绘制节点变化过程添加异常处理完善代码编写单元测试验证边界条件尝试实现其他变种（循环链表）