内存里的两兄弟 —— 数组与链表

数组和链表就像住酒店和住青旅——一个讲究整整齐齐排排坐，一个随遇而安哪有空位住哪里。理解它们的区别，是后续所有数据结构的基础。

📋 开篇自测：你已经知道多少？

Python的列表（list）底层是数组还是链表？它为什么能做到”随意添加元素”？

为什么从数组中间删除一个元素特别慢，而从链表中间删除却很快？

如果你需要频繁地在第一个位置插入数据，应该选数组还是链表？

一、从内存说起——计算机是怎么存东西的

要理解数组和链表的区别，得先聊聊计算机的内存是什么样的。

你可以把计算机内存想象成一家巨大的储物柜公司。这家公司有几十亿个小格子（每个格子大约1字节），每个格子有一个唯一的编号（内存地址）。当你的程序需要存储数据时，就要向这家公司”租格子”。

关键在于，你怎么租，决定了后续操作的效率。这就引出了两种截然不同的策略：

数组的策略： “我要连续的10个格子！必须挨在一起，从100号到109号。”
链表的策略： “随便给我10个空格子就行，不用挨着，但每个格子里我会记下一个格子的编号。”

这两种策略各有利弊，而它们的利弊直接决定了不同操作的效率。

二、数组——整齐划一的连续空间

什么是数组

数组是一段连续的内存空间，用来存储一组相同类型的数据。

想象一排电影院的座位：座位号是连续的（第1号到第N号），每个座位大小相同，你可以通过座位号直接找到任何一个座位——不需要从第一排开始一个个数。

# Python中，列表（list）底层就是用数组实现的
seats = ["张三", "李四", "王五", "赵六", "孙七"]
#  索引：  0       1       2       3       4

数组的核心优势：随机访问

数组最强大的能力是随机访问——给定索引，立刻就能找到对应的元素。

这是怎么做到的？因为数组在内存中是连续的，所以：

元素地址 = 首元素地址 + 索引 × 每个元素的大小

就像你要找电影院第50排的座位，不需要从第1排走过去。你知道每排之间的距离，直接算出第50排的位置就行了。

# 随机访问：O(1)时间
numbers = [10, 20, 30, 40, 50]
print(numbers[3])  # 瞬间得到40，不需要遍历前面的元素

数组的弱点：插入和删除

正因为数组要保持连续，当你需要在中间插入或删除一个元素时，麻烦就来了。

插入操作：

假设你有一排5个人坐在长椅上（位置0-4），现在要让一个新朋友坐在位置2。怎么办？位置2、3、4上的人都得往后挪一个位子。

def array_insert(arr, index, value):
    """模拟数组中间插入的过程"""
    arr.append(None)  # 先在末尾加一个空位
    # 从后往前，每个元素往后挪一位
    for i in range(len(arr) - 1, index, -1):
        arr[i] = arr[i - 1]
    arr[index] = value
    return arr

# 例子
data = [10, 20, 30, 40, 50]
print(array_insert(data, 2, 25))  # [10, 20, 25, 30, 40, 50]

平均需要移动n/2个元素，时间复杂度：O(n)。

删除操作：

同理，删除中间的一个人后，后面的人都得往前挪一位来填补空缺。

def array_delete(arr, index):
    """模拟数组中间删除的过程"""
    for i in range(index, len(arr) - 1):
        arr[i] = arr[i + 1]
    arr.pop()  # 去掉末尾多余的位置
    return arr

data = [10, 20, 25, 30, 40, 50]
print(array_delete(data, 2))  # [10, 20, 30, 40, 50]

时间复杂度同样是 O(n)。

🤔 想一想 如果你不在乎数组中元素的顺序，删除操作有没有更快的方法？（提示：把最后一个元素搬到被删除的位置）

三、链表——灵活自由的离散空间

什么是链表

链表是一组散落在内存各处的节点，每个节点除了存储数据本身，还存储着下一个节点的地址（指针/引用）。

如果说数组是一排固定座位的电影院，那链表就像一个寻宝游戏——每到一个地点，你会得到下一个地点的线索，顺着线索一路走下去。

class ListNode:
    """链表节点"""
    def __init__(self, value):
        self.value = value
        self.next = None  # 指向下一个节点的"线索"

# 创建链表：10 -> 20 -> 30 -> 40 -> 50
node1 = ListNode(10)
node2 = ListNode(20)
node3 = ListNode(30)
node4 = ListNode(40)
node5 = ListNode(50)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

链表的核心优势：插入和删除

链表不需要连续的内存空间，所以插入和删除时不需要挪动其他元素。

插入操作： 就像一个手拉手的队伍里要加入一个新人——只需要断开某处的手，让新人左右各拉一个人的手就行了。

def insert_after(node, new_value):
    """在某个节点后面插入新节点"""
    new_node = ListNode(new_value)
    new_node.next = node.next  # 新节点指向原来的下一个
    node.next = new_node       # 前一个节点指向新节点

# 在20后面插入25：10 -> 20 -> 25 -> 30 -> 40 -> 50
insert_after(node2, 25)

只修改了两个指针，不管链表有多长，时间复杂度都是 O(1)。

删除操作： 队伍中有人要离开——左右两个人直接拉手就行。

def delete_after(node):
    """删除某个节点后面的节点"""
    if node.next:
        node.next = node.next.next  # 跳过要删除的节点

# 删除25（node2后面的节点）：10 -> 20 -> 30 -> 40 -> 50
delete_after(node2)

同样只修改一个指针，时间复杂度 O(1)。

链表的弱点：无法随机访问

链表最大的劣势是没法直接跳到第n个元素。你只知道第一个节点在哪里，要找第5个节点，就得从第一个开始，顺着指针一个个走过去。

def get_by_index(head, index):
    """通过索引获取链表中的元素"""
    current = head
    for _ in range(index):
        if current is None:
            return None
        current = current.next
    return current.value if current else None

# 要找第4个元素（索引3），必须走过前面3个节点
result = get_by_index(node1, 3)  # 得到40，但走了3步

时间复杂度：O(n)。

四、链表的进化版本

基础的链表（单链表）只能从前往后走，有时候不太方便。于是人们设计了几种变体。

双向链表——前后都能走

每个节点不仅记住下一个节点，还记住上一个节点。就像队伍里每个人都记住了左边和右边的人是谁。

class DoublyListNode:
    def __init__(self, value):
        self.value = value
        self.prev = None  # 指向前一个节点
        self.next = None  # 指向后一个节点

# 构建双向链表
def build_doubly_linked(values):
    if not values:
        return None
    head = DoublyListNode(values[0])
    current = head
    for val in values[1:]:
        new_node = DoublyListNode(val)
        new_node.prev = current
        current.next = new_node
        current = new_node
    return head

head = build_doubly_linked([10, 20, 30, 40, 50])

双向链表的好处：

可以从尾部往前遍历
删除某个节点时不需要知道它的前驱节点（因为节点自己就记着前驱）

代价是每个节点多存储一个指针，占用更多内存。

循环链表——首尾相连

最后一个节点的next指向第一个节点，形成一个环。适合处理”循环”场景，比如约瑟夫环问题、循环播放列表等。

def build_circular_linked(values):
    """构建循环链表"""
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        new_node = ListNode(val)
        current.next = new_node
        current = new_node
    current.next = head  # 尾部指向头部，形成环
    return head

五、数组 vs 链表——全面对比

操作	数组	链表
随机访问（按索引取值）	O(1)	O(n)
头部插入	O(n)	O(1)
尾部插入	O(1)*	O(1)**
中间插入	O(n)	O(1)***
头部删除	O(n)	O(1)
中间删除	O(n)	O(1)***
内存使用	紧凑（无额外开销）	较大（每个节点多存指针）
缓存友好性	好（连续内存）	差（内存分散）

*数组尾部插入均摊O(1)，因为偶尔需要扩容。 **如果维护了尾指针。 ***前提是已经定位到了插入/删除位置。如果还需要先查找，那查找本身是O(n)。

什么时候用数组，什么时候用链表？

选数组的场景：

频繁地按索引读取数据（比如排行榜，经常要查”第几名是谁”）
数据量大致固定，不需要频繁增删
需要对数据进行排序、二分查找等操作

选链表的场景：

频繁地在头部或中间插入、删除数据
不确定数据总量，需要灵活伸缩
需要实现某些特定数据结构（如LRU缓存、多项式表示）

⚠️ 常见误区

误区1：“Python的list就是链表” —— 不是！Python的list底层是动态数组。它通过预分配额外空间的方式，让尾部添加操作的均摊时间复杂度达到O(1)。但在头部或中间插入仍然是O(n)。

误区2：“链表的插入删除都是O(1)” —— 这个说法有前提：你已经拿到了要操作的节点的引用。如果你需要先”找到”那个节点，查找过程本身就是O(n)。

误区3：“数组比链表好”或”链表比数组好” —— 没有绝对的好坏，只有适不适合。选择数据结构就像选交通工具——城区短途用自行车，长途用飞机，没有哪个”更好”。

六、动手实践——实现你自己的链表

理论讲完了，让我们动手实现一个功能完整的链表类：

class LinkedList:
    """单链表的完整实现"""

    def __init__(self):
        self.head = None
        self.size = 0

    def is_empty(self):
        return self.size == 0

    def prepend(self, value):
        """在头部插入 —— O(1)"""
        new_node = ListNode(value)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

    def append(self, value):
        """在尾部插入 —— O(n)，因为需要走到末尾"""
        new_node = ListNode(value)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
        self.size += 1

    def get(self, index):
        """按索引获取元素 —— O(n)"""
        if index < 0 or index >= self.size:
            raise IndexError("索引越界")
        current = self.head
        for _ in range(index):
            current = current.next
        return current.value

    def remove(self, value):
        """删除第一个匹配的元素 —— O(n)"""
        if self.head is None:
            return False
        if self.head.value == value:
            self.head = self.head.next
            self.size -= 1
            return True
        current = self.head
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                self.size -= 1
                return True
            current = current.next
        return False

    def display(self):
        """打印链表"""
        elements = []
        current = self.head
        while current:
            elements.append(str(current.value))
            current = current.next
        return " -> ".join(elements)

# 试试看
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.prepend(5)
print(ll.display())   # 5 -> 10 -> 20 -> 30
ll.remove(20)
print(ll.display())   # 5 -> 10 -> 30
print(ll.get(1))      # 10

🤔 想一想 上面的append方法每次都要遍历到链表末尾才能添加元素，时间复杂度是O(n)。你能想办法把它优化成O(1)吗？（提示：增加一个tail属性）

📝 掌握度自测

概念题： 数组在内存中是什么样子的？为什么这种存储方式让随机访问变成了O(1)？
分析题： 如果一个应用需要每秒处理10000次”在列表头部插入新数据”的请求，用Python的list和用链表，性能差距大约有多大？
编码题： 请写一个函数，反转一个单链表。也就是把 1 -> 2 -> 3 -> 4 变成 4 -> 3 -> 2 -> 1。
设计题： 如果你要设计一个浏览器的”前进/后退”功能，你会用什么数据结构？为什么？
综合题： 给定一个链表，如何判断它是否有环？（提示：想想龟兔赛跑的故事——快指针和慢指针）

💡 自我评估

全部答对：数组与链表已经是你的老朋友了，进入下一章吧。

答对3-4题：基础扎实，编码题和综合题可以多练习几遍。

答对1-2题：回头把”数组 vs 链表”的对比表格再看一遍，用纸笔画出每步操作的内存变化。

全部答错：别灰心！建议你打开Python，把文中的每一段代码都亲手敲一遍、跑一遍。

数组和链表是”自由”的——你可以在任意位置做增删查改。但有时候，刻意限制可用的操作反而能带来更大的力量。下一章我们来认识栈和队列——两种”限制即力量”的数据结构。