用Python实战解析线性表：从顺序表到链表的深度实现

数据结构是计算机科学的基石，而线性表作为最基本的数据结构之一，几乎出现在所有程序员的日常工作中。但很多初学者在学习线性表时，往往陷入纯理论的死记硬背，无法真正理解其内在逻辑和应用场景。本文将带你用Python从零开始实现顺序表和链表，通过代码实践来深入理解这两种经典数据结构的差异和适用场景。

1. 线性表基础与Python环境准备

线性表是由n个数据元素组成的有限序列，其中每个元素都有确定的位置。线性表有两种主要的物理存储结构：顺序存储（顺序表）和链式存储（链表）。理解这两种结构的差异对于选择合适的数据结构解决实际问题至关重要。

在开始编码前，我们需要确保Python环境已就绪。推荐使用Python 3.6+版本，并安装必要的工具：

# 检查Python版本
python --version

# 可选：创建虚拟环境
python -m venv linear_env
source linear_env/bin/activate  # Linux/Mac
linear_env\Scripts\activate     # Windows

顺序表和链表的核心区别在于内存分配方式：

• 顺序表 ：元素在内存中连续存储，通过索引直接访问
• 链表 ：元素在内存中分散存储，通过指针连接各个节点

这种底层差异导致了它们在各种操作上的性能特点完全不同。下面我们将分别实现这两种结构，并通过具体操作来体会它们的差异。

2. Python实现顺序表及其核心操作

顺序表在Python中最直接的类比就是列表(list)，但为了深入理解其原理，我们将从头实现一个简化版的顺序表。顺序表的最大特点是物理存储连续，这使得随机访问非常高效。

2.1 顺序表的基本结构

我们先定义一个SequenceTable类来表示顺序表：

class SequenceTable:
    def __init__(self, capacity=10):
        self.capacity = capacity  # 初始容量
        self.size = 0             # 当前元素数量
        self.array = [None] * capacity  # 底层存储数组

    def __str__(self):
        return str(self.array[:self.size])

这个基础实现包含了顺序表的三个核心属性：

• capacity ：表的最大容量
• size ：当前存储的元素数量
• array ：实际存储元素的数组

2.2 顺序表的核心操作实现

插入操作 是顺序表最需要关注的操作之一，因为它的性能特点直接影响使用场景：

def insert(self, index, element):
    if index < 0 or index > self.size:
        raise IndexError("Index out of range")
    
    # 如果数组已满，先扩容
    if self.size == self.capacity:
        self._resize()
    
    # 将index及之后的元素后移一位
    for i in range(self.size, index, -1):
        self.array[i] = self.array[i-1]
    
    self.array[index] = element
    self.size += 1

def _resize(self):
    self.capacity *= 2
    new_array = [None] * self.capacity
    for i in range(self.size):
        new_array[i] = self.array[i]
    self.array = new_array

插入操作的时间复杂度分析：

• 最好情况：在表尾插入，O(1)
• 最坏情况：在表头插入，O(n)
• 平均情况：O(n)

删除操作 的实现也体现了顺序表的特点：

def delete(self, index):
    if index < 0 or index >= self.size:
        raise IndexError("Index out of range")
    
    # 将index之后的元素前移一位
    for i in range(index, self.size-1):
        self.array[i] = self.array[i+1]
    
    self.size -= 1
    return self.array[index]

删除操作的时间复杂度与插入类似，都取决于需要移动的元素数量。

查找操作 是顺序表的优势所在：

def get(self, index):
    if index < 0 or index >= self.size:
        raise IndexError("Index out of range")
    return self.array[index]

def search(self, element):
    for i in range(self.size):
        if self.array[i] == element:
            return i
    return -1

顺序表的随机访问时间复杂度为O(1)，这是它最大的优势。但查找特定元素仍需O(n)时间，除非表是有序的可以使用二分查找。

2.3 顺序表的优缺点总结

通过实现我们可以总结顺序表的特点：

优点 ：

• 随机访问速度快（O(1)）
• 存储密度高，不需要额外空间存储指针
• 缓存友好，连续内存访问效率高

缺点 ：

• 插入/删除操作可能需要移动大量元素
• 需要预先分配连续内存空间，可能造成浪费或不足
• 扩容时需要复制全部元素，代价较高

顺序表适合元素数量相对固定、查询操作远多于插入删除的场景，比如存储学生成绩表、商品库存等。

3. Python实现单链表及其核心操作

链表通过指针将分散的内存块连接起来，每个节点包含数据和指向下一个节点的指针。这种结构使得插入和删除操作更加高效，但牺牲了随机访问的能力。

3.1 单链表的基本结构

我们先定义链表节点和链表类：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    
    def __str__(self):
        current = self.head
        elements = []
        while current:
            elements.append(str(current.data))
            current = current.next
        return "->".join(elements)

链表只需要记录头节点，通过节点的next指针可以遍历整个链表。与顺序表不同，链表不需要预先分配固定大小的内存空间。

3.2 单链表的核心操作实现

插入操作 是链表的强项，特别是在表头插入：

def insert_at_head(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node
    self.size += 1

def insert_at_position(self, position, data):
    if position < 0 or position > self.size:
        raise IndexError("Position out of range")
    
    if position == 0:
        self.insert_at_head(data)
        return
    
    new_node = Node(data)
    current = self.head
    for _ in range(position - 1):
        current = current.next
    
    new_node.next = current.next
    current.next = new_node
    self.size += 1

链表插入的时间复杂度：

• 表头插入：O(1)
• 指定位置插入：平均O(n)（需要先找到插入位置）

删除操作 同样体现了链表的优势：

def delete_at_head(self):
    if not self.head:
        raise Exception("List is empty")
    
    data = self.head.data
    self.head = self.head.next
    self.size -= 1
    return data

def delete_at_position(self, position):
    if position < 0 or position >= self.size:
        raise IndexError("Position out of range")
    
    if position == 0:
        return self.delete_at_head()
    
    current = self.head
    for _ in range(position - 1):
        current = current.next
    
    data = current.next.data
    current.next = current.next.next
    self.size -= 1
    return data

删除操作的时间复杂度与插入类似，表头删除是O(1)，其他位置需要先找到删除位置。

查找操作 是链表的弱项：

def get(self, position):
    if position < 0 or position >= self.size:
        raise IndexError("Position out of range")
    
    current = self.head
    for _ in range(position):
        current = current.next
    return current.data

def search(self, data):
    current = self.head
    position = 0
    while current:
        if current.data == data:
            return position
        current = current.next
        position += 1
    return -1

链表的查找必须从头开始遍历，时间复杂度为O(n)。没有随机访问能力是链表的主要缺点。

3.3 链表的变体：双向链表和循环链表

除了基本的单链表，还有两种常见的变体：

双向链表 ：每个节点既有next指针也有prev指针，可以双向遍历

class DoublyNode:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

循环链表 ：尾节点的next指向头节点，形成环形结构

class CircularLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
    
    def insert_at_head(self, data):
        new_node = Node(data)
        if not self.head:
            new_node.next = new_node  # 指向自己
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head
        self.head = new_node
        self.size += 1

这些变体在特定场景下可以提供更好的性能或更方便的操作。

3.4 链表的优缺点总结

优点 ：

• 插入/删除操作高效，特别是表头操作O(1)
• 不需要预先分配固定大小，动态扩展灵活
• 内存利用率高，按需分配

缺点 ：

• 不能随机访问，查找效率低O(n)
• 需要额外空间存储指针
• 缓存不友好，内存访问不连续

链表适合频繁插入删除、元素数量变化大的场景，如实现队列、图邻接表等。

4. 顺序表与链表的性能对比与实战应用

理解了两种结构的实现后，我们需要在实际问题中选择合适的结构。下面通过几个典型场景来分析它们的表现。

4.1 时间复杂度对比

操作	顺序表	链表
随机访问(按索引)	O(1)	O(n)
头部插入	O(n)	O(1)
尾部插入	O(1)	O(n)*
中间插入	O(n)	O(n)
头部删除	O(n)	O(1)
尾部删除	O(1)	O(n)*
中间删除	O(n)	O(n)
查找元素	O(n)	O(n)

*注：如果链表维护尾指针，尾部操作可优化为O(1)

4.2 实际应用场景选择

选择顺序表的情况 ：

• 需要频繁随机访问元素
• 元素数量相对稳定，变化不大
• 内存空间有限，需要高存储密度
• 示例：学生成绩管理系统、商品库存系统

选择链表的情况 ：

• 需要频繁在头部插入/删除
• 元素数量变化大，难以预估
• 内存碎片较多，难以分配大块连续空间
• 示例：浏览器历史记录、撤销操作栈、消息队列

4.3 综合实战：LRU缓存实现

LRU（Least Recently Used）缓存淘汰算法是链表和哈希表结合的经典应用。我们使用双向链表和哈希表实现一个O(1)时间复杂度的LRU缓存：

class LRUCacheNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.head = LRUCacheNode(0, 0)
        self.tail = LRUCacheNode(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
    
    def _add_node(self, node):
        # 总是添加到头部
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node):
        prev = node.prev
        next_node = node.next
        prev.next = next_node
        next_node.prev = prev
    
    def _move_to_head(self, node):
        self._remove_node(node)
        self._add_node(node)
    
    def _pop_tail(self):
        res = self.tail.prev
        self._remove_node(res)
        return res
    
    def get(self, key):
        node = self.cache.get(key)
        if not node:
            return -1
        self._move_to_head(node)
        return node.value
    
    def put(self, key, value):
        node = self.cache.get(key)
        if not node:
            new_node = LRUCacheNode(key, value)
            self.cache[key] = new_node
            self._add_node(new_node)
            self.size += 1
            if self.size > self.capacity:
                tail = self._pop_tail()
                del self.cache[tail.key]
                self.size -= 1
        else:
            node.value = value
            self._move_to_head(node)

这个实现中：

• 哈希表提供O(1)的键值查找
• 双向链表维护访问顺序，最近访问的放在头部
• 当缓存满时，从尾部淘汰最久未使用的项

这种组合数据结构的设计充分利用了哈希表和链表的优势，是数据结构综合应用的典范。