用Python实战解析链表与顺序表：从原理到LeetCode刷题技巧
数据结构是计算机科学的基石，而链表和顺序表作为最基础的线性结构，在算法面试和实际开发中无处不在。但很多初学者在理论学习后依然无法灵活运用，本文将用Python带你从零实现这两种结构，并通过LeetCode真题巩固理解。
1. 顺序表：数组的Python实现
顺序表的核心在于连续内存空间，Python中的list就是基于顺序表实现的动态数组。我们先手动实现一个简化版：
class SequentialList: def __init__(self, capacity=10): self._capacity = capacity self._size = 0 self._data = [None] * capacity def __getitem__(self, index): if 0 <= index < self._size: return self._data[index] raise IndexError("Index out of range") def append(self, value): if self._size == self._capacity: self._resize() self._data[self._size] = value self._size += 1 def _resize(self): self._capacity *= 2 new_data = [None] * self._capacity for i in range(self._size): new_data[i] = self._data[i] self._data = new_data关键操作时间复杂度对比：
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 访问 | O(1) | 直接通过索引计算内存地址 |
| 插入 | O(n) | 需要移动后续所有元素 |
| 删除 | O(n) | 同样需要移动元素 |
| 扩容 | O(n) | 分配新空间并复制所有元素 |
提示：Python内置list的append()操作平均时间复杂度是O(1)，这是因为采用了动态扩容策略——不是每次添加都扩容，而是按几何级数增长。
2. 链表：非连续存储的艺术
链表通过节点间的指针链接实现非连续存储，我们先实现单链表：
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class LinkedList: def __init__(self): self.head = None self.size = 0 def add_at_head(self, val): new_node = ListNode(val) new_node.next = self.head self.head = new_node self.size += 1 def add_at_tail(self, val): if not self.head: self.add_at_head(val) return current = self.head while current.next: current = current.next current.next = ListNode(val) self.size += 1链表与顺序表的性能差异主要体现在：
- 插入/删除优势：链表在已知节点位置时操作只需O(1)时间
- 空间开销：每个节点需要额外存储指针
- 缓存不友好：非连续存储导致CPU缓存命中率低
3. 双链表实现与优化
双链表通过增加前驱指针提升某些操作效率：
class DoublyListNode: def __init__(self, val=0, prev=None, next=None): self.val = val self.prev = prev self.next = next class DoublyLinkedList: def __init__(self): self.head = None self.tail = None self.size = 0 def add_at_tail(self, val): new_node = DoublyListNode(val) if not self.tail: self.head = self.tail = new_node else: self.tail.next = new_node new_node.prev = self.tail self.tail = new_node self.size += 1双链表的典型应用场景包括：
- 实现LRU缓存淘汰算法
- 浏览器前进后退功能
- 文本编辑器的撤销操作
4. LeetCode实战：反转链表
LeetCode第206题是检验链表理解的经典题目：
问题描述：给定单链表的头节点，返回反转后的链表。
迭代解法：
def reverseList(head): prev = None current = head while current: next_node = current.next current.next = prev prev = current current = next_node return prev递归解法：
def reverseList(head): if not head or not head.next: return head new_head = reverseList(head.next) head.next.next = head head.next = None return new_head两种解法的对比：
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 迭代 | O(n) | O(1) | 内存受限环境 |
| 递归 | O(n) | O(n) | 代码简洁优先 |
5. 工程实践中的选择策略
在实际开发中如何选择数据结构？考虑以下因素：
访问模式：
- 频繁随机访问 → 顺序表
- 大量插入删除 → 链表
内存考虑：
- 内存紧凑 → 顺序表（无指针开销）
- 动态增长 → 链表（无需预分配）
语言特性：
- Python中list已高度优化，优先使用
- 需要特殊结构时再自定义实现
常见误区：
- 过度优化：在数据量小时性能差异可以忽略
- 忽视语言内置实现：Python list已经融合了链表和数组的优点
- 不考虑线程安全：多线程环境需要额外同步机制
掌握这些底层实现原理，不仅能帮助你在技术面试中游刃有余，更能让你在实际开发中做出合理的设计决策。试着用这些知识去解决LeetCode上的"合并两个有序链表"(第21题)和"环形链表"(第141题)，体会不同数据结构的特点。
