算法刷题系列（五十八）：线性表——数组与链表如何选择

算法刷题系列（五十八）：线性表——数组与链表如何选择

旧笔记中的“线性表”记录了顺序存储和链式存储的区别。本篇将它整理成可用于做题的决策：若经常按下标访问，数组通常合适；若已有节点位置且需要局部重连，链表可能合适。两者都保存线性顺序，但操作成本不同。

一、线性表是逻辑关系，不是某一种容器

线性表是有限个元素组成的序列。除首尾外，每个元素有唯一前驱和后继。这个定义只描述逻辑次序，没有规定元素在内存中的位置。

常见实现：

• 顺序表/动态数组：元素放在一段连续的逻辑存储区，通过下标定位。
• 链表：每个节点保存数据和后继引用，节点之间通过引用连接。

因此，“逻辑上相邻”不等于“物理地址相邻”。

二、操作成本对比

操作	动态数组	单链表
按下标读取	O(1)	O(n)
查找值	O(n)	O(n)
末尾追加	摊还 O(1)	有尾指针时 O(1)
中间插入/删除	通常要移动后续元素，O(n)	先找到位置 O(n)，改引用 O(1)
额外节点空间	通常较少	每个节点需要保存引用

链表插入的 O(1) 常被误解：这是已经拿到前驱节点之后的链接修改成本；若还要按索引找到它，总成本仍是 O(n)。

三、Java：用节点表示单链表

public class SinglyLinkedList {
    private static final class Node {
        int value;
        Node next;

        Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    private Node head;

    public void addFirst(int value) {
        head = new Node(value, head);
    }

    public boolean removeFirstValue(int target) {
        Node dummy = new Node(0, head);
        Node previous = dummy;
        Node current = head;
        while (current != null) {
            if (current.value == target) {
                previous.next = current.next;
                head = dummy.next;
                return true;
            }
            previous = current;
            current = current.next;
        }
        head = dummy.next;
        return false;
    }
}

虚拟头节点统一了删除头节点和删除中间节点的链接逻辑。删除操作扫描至多一次，时间 O(n)，额外空间 O(1)。

四、Python：读写节点链接

class Node:
    def __init__(self, value: int, next_node: "Node | None" = None) -> None:
        self.value = value
        self.next = next_node

class SinglyLinkedList:
    def __init__(self) -> None:
        self.head: Node | None = None

    def add_first(self, value: int) -> None:
        self.head = Node(value, self.head)

    def remove_first_value(self, target: int) -> bool:
        dummy = Node(0, self.head)
        previous = dummy
        current = self.head
        while current is not None:
            if current.value == target:
                previous.next = current.next
                self.head = dummy.next
                return True
            previous, current = current, current.next
        self.head = dummy.next
        return False

linked = SinglyLinkedList()
for value in (3, 2, 3):
    linked.add_first(value)
assert linked.remove_first_value(3)
assert linked.head.value == 2
assert linked.remove_first_value(2)
assert linked.head.value == 3 and linked.head.next is None
assert not linked.remove_first_value(9)

在 Python 3.9 及更早版本运行这类前向引用注解时，可在代码顶部加 from __future__ import annotations。

五、存储方式还会影响什么？

• 顺序存储通常有更好的缓存局部性，遍历时连续读取。
• 链式存储便于通过节点引用做局部插入和重连，但会消耗指针空间并产生跳转访问。
• 数组容量不足时，动态数组可能分配更大内存并复制元素；摊还分析说明长期追加的平均成本仍可为常数级。
• 链表若没有额外索引，无法像数组一样直接跳到第 i 个节点。

六、常见误区

1. 认为链表删除总是 O(1)：按值或下标删除通常要先遍历。
2. 认为动态数组每次追加都是 O(n)：单次扩容可能线性，但摊还追加通常为 O(1)。
3. 丢失后继引用再重连：改指针前保存仍需访问的节点。
4. 循环链表终止条件仍写 current != null：环结构要使用回到起点等专门条件。
5. 选择结构只看插入：还要考虑查询、遍历、内存和数据规模。

与系列其他篇章的连接

本篇补全了数据结构总览中“线性结构”的实现视角。具体链表反转和节点重连见第十一篇；数组筛选和双指针见第十二、十四篇。

小结

数组与链表的区别是存储布局和操作成本，不是一个绝对优于另一个。按下标访问和顺序扫描优先考虑数组；需要已知节点位置的局部重连时再考虑链表。