从零理解数据结构：数组 vs 链表的内在逻辑

2025年03月24日

刚学编程时，你是否也纠结过这些问题：
❓ 为什么Python的list既能快速查数据又怕频繁插入？
❓ Redis的列表底层居然用链表实现？
❓ LeetCode刷题时总被要求选最优数据结构？

今天我们用三个生活场景+动画图解+手撕代码，彻底搞懂这对经典CP：数组(Array) 与 链表(LinkedList) 。

一、生活场景中的数据结构

1. 储物柜系统（数组）

想象超市的储物柜系统：

每个柜子连续编号（0,1,2…）
凭柜号可直接找到物品（O(1)访问）
想要插入新柜子？必须重建整排柜子！

这就是数组的特性：

内存空间连续
随机访问极快
插入/删除成本高

2. 绿皮火车（链表）

回忆老式火车的车厢连接方式：

每节车厢自带下一节车厢的钥匙
想要加挂车厢？只需修改相邻车厢的钥匙
但找第10节车厢必须从头开始数

这正是链表的本质：

通过指针连接离散内存
插入/删除效率高
随机访问需要遍历

二、内存布局的底层差异

1. 数组的内存分配（静态 vs 动态）

# 静态数组（C语言风格）
int arr[5] = {1,2,3,4,5}; 

# 动态数组（Python列表实际是动态数组）
python_list = []  # 初始容量可能是4
python_list.append(1)  # 当容量不足时触发扩容（复制到新地址！）

🖥️ 动态数组扩容过程：
旧数组：[1,2,3,4] → 插入5 → 新数组：[1,2,3,4,5, _, _, _]（容量翻倍）

2. 链表的节点跳转

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

# 创建三个节点并连接
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node1.next = node2
node2.next = node3

💡 内存示意图：

1	[Node1\|data=A\|next] → [Node2\|data=B\|next] → [Node3\|data=C\|next]→None

三、时间复杂度对比（附性能实测）

操作	数组	链表
随机访问	O(1)	O(n)
头部插入	O(n)	O(1)
尾部插入	O(1)*	O(n)
中间插入	O(n)	O(1)查找+O(1)插入

*注：动态数组的尾部插入摊还分析后仍视为O(1)

实测场景：在100万个元素的数据结构头部插入数据

import time

# 数组测试（Python list）
start = time.time()
lst = [0]*1_000_000
lst.insert(0, 1)  # 耗时约0.1秒
print("Array:", time.time()-start)

# 链表测试（需提前构造链表）
# 此处省略构造代码，实测时间约0.0001秒

四、不同编程语言的实现差异

1. Python的”伪装者”列表

你以为的Python列表：

1	lst = [1,2,3]

实际上的动态数组：

存储元素指针的连续空间
自动扩容机制（增长因子约1.125）
插入性能陷阱：lst.insert(0, x)比append(x)慢1000倍！

2. Java的双向链表

LinkedList类实现双向链表：

// 每个节点包含前后指针
class Node<E> {
    E item;
    Node<E> prev;
    Node<E> next;
}

3. Redis的quicklist

结合数组与链表的优势：

宏观上是链表
每个节点是ziplist（压缩数组）
平衡内存效率与操作性能

五、实际开发中的选择策略

优先使用数组的场景 ✅

🔹 需要频繁随机访问（如二进制搜索）
🔹 数据量固定或变化小（如缓存窗口）
🔹 内存资源紧张（链表需要额外指针空间）

优先使用链表的场景 ✅

🔹 频繁在头部/中部插入删除（如撤销操作栈）
🔹 数据总量不可预知（如实时日志记录）
🔹 需要实现先进先出队列（双向链表）

▍ 经典案例

文本编辑器：用链表实现每行文本（支持快速插入）
LRU缓存：哈希表+双向链表组合
区块链：通过哈希指针连接的超级链表

六、手写链表实现（Python版）

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

    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = self.Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 测试用例
if __name__ == "__main__":
    ll = LinkedList()
    ll.append("A")
    ll.append("B")
    ll.append("C")
    ll.print_list()  # 输出：A -> B -> C -> None

讨论题

💬 你在项目中遇到过哪些因为选错数据结构导致的性能问题？欢迎在评论区分享经历！

扩展阅读：

一言

Archive

Recent Posts