用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. 工程实践中的选择策略

在实际开发中如何选择数据结构？考虑以下因素：

1. 访问模式 ：

   • 频繁随机访问 → 顺序表
   • 大量插入删除 → 链表

2. 内存考虑 ：

   • 内存紧凑 → 顺序表（无指针开销）
   • 动态增长 → 链表（无需预分配）

3. 语言特性 ：

   • Python中list已高度优化，优先使用
   • 需要特殊结构时再自定义实现

常见误区 ：

• 过度优化：在数据量小时性能差异可以忽略
• 忽视语言内置实现：Python list已经融合了链表和数组的优点
• 不考虑线程安全：多线程环境需要额外同步机制

掌握这些底层实现原理，不仅能帮助你在技术面试中游刃有余，更能让你在实际开发中做出合理的设计决策。试着用这些知识去解决LeetCode上的"合并两个有序链表"(第21题)和"环形链表"(第141题)，体会不同数据结构的特点。