线性数据结构：数组、链表、栈、队列与跳表

本文覆盖五种核心线性数据结构：数组、链表、栈、队列和跳表。掌握它们的内存模型、操作复杂度和典型应用场景，是理解更复杂数据结构的基础。

目录

章节	说明
数组	连续内存、随机访问、动态扩容
链表	单/双/循环链表，与数组的对比
栈	LIFO 结构，括号匹配、函数调用栈
队列	FIFO 结构，循环队列、阻塞队列
跳表	链表 + 多级索引，O(logn) 查询

数组

数组（Array） 是一种线性表数据结构，用一组连续的内存空间存储相同类型的数据。

随机访问原理

数组的核心优势来自其内存连续性——CPU 可以通过一次加法直接计算任意元素的地址：

$$a[i]_address = base_address + i \times data_type_size$$

下标从 0 开始的根本原因：偏移量即下标，减少一次减法运算，提升寻址效率。若从 1 开始，公式变为 $base + (i-1) \times size$，多一次减法。

操作复杂度

操作	时间复杂度	说明
随机访问 a[i]	O(1)	寻址公式直接计算
末尾插入	O(1)	无需搬移
任意位置插入	O(n)	需搬移后续元素保持连续性
删除	O(n)	需搬移保持连续性
查找（无序）	O(n)	顺序遍历

优化技巧：对无序数组做插入时，可将第 k 位元素移到末尾，再将新元素放到第 k 位，时间复杂度降为 O(1)（快排分区思想）。

动态扩容（ArrayList）

• 底层依赖数组，空间不足时申请 1.5 倍新空间，并拷贝数据
• 扩容操作均摊时间复杂度仍为 O(1)（偶尔 O(n) 的扩容分摊到每次操作）
• 创建时若能预估大小，建议提前指定容量，避免频繁扩容

数组 vs 容器（ArrayList）

场景	推荐	原因
存储基本类型（int/long），关注性能	数组	避免装箱拆箱的额外开销
多维数组，直观表达	数组	int[][] 比 List<List<Integer>> 更清晰
大小未知，需动态扩容	ArrayList	自动管理容量
业务开发，不关注底层	ArrayList	提供 contains/sort 等工具方法

链表

链表通过指针将零散的内存块串联，不需要连续内存空间。这使得插入/删除天然高效，但牺牲了随机访问能力。

三种链表结构对比

单链表：每个节点有 next 指针，头节点记录基地址，尾节点指向 NULL。结构最简单，适合顺序遍历场景。

双向链表：每个节点有 next 和 prev 两个指针，支持 O(1) 时间找到前驱节点。Java LinkedHashMap 底层即使用双向链表。

循环链表：尾节点的 next 指向头节点，适合处理环形结构问题（如约瑟夫问题）。

操作复杂度

操作	单链表	双向链表	说明
头部插入/删除	O(1)	O(1)	直接操作头节点
已知节点前插入	O(n)	O(1)	单链表需先找前驱
已知节点删除	O(n)	O(1)	双向链表直接访问 prev
随机访问第 k 个	O(n)	O(n)	无法跳跃，只能遍历
按值查找	O(n)	O(n)	同上

空间换时间：双向链表多存一个 prev 指针（额外 8 字节/节点），但在删除/插入特定节点时效率更高。这是 Java LinkedHashMap 使用双向链表的原因——它需要频繁地将节点移到链表头部（LRU 语义）。

链表 vs 数组

维度	数组	链表
内存布局	连续，对 CPU 缓存友好	零散，缓存不友好
大小	固定（需预分配）	动态，天然支持扩容
随机访问	O(1)	O(n)
插入/删除（已知位置）	O(n)	O(1)
额外开销	无	每个节点需存指针（8 字节）

LRU 缓存实现

LRU（Least Recently Used）缓存要求：命中时 O(1)，淘汰最久未用时 O(1)。

单纯用链表只能做到 O(n)——每次访问需遍历找到该节点。解法：哈希表 + 双向链表。

操作	实现方式	复杂度
命中缓存	哈希表 O(1) 定位节点 → 移至链表头部	O(1)
未命中且缓存未满	直接插入链表头部，哈希表记录	O(1)
未命中且缓存已满	删除链表尾节点（哈希表同步删除），插入头部	O(1)

// LRU 核心结构（Java 内置 LinkedHashMap 已实现此逻辑）
class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(), tail = new Node(); // 虚拟头尾节点

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        moveToHead(node); // 命中：移到头部
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = value;
            moveToHead(node);
        } else {
            Node node = new Node(key, value);
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                Node removed = removeTail(); // 淘汰最久未用
                map.remove(removed.key);
            }
        }
    }
}

栈

栈（Stack） 是操作受限的线性表，只允许在一端插入和删除，满足后进先出（LIFO）。

为什么需要栈？ 栈的限制本身就是价值——它强制"后进先出"的访问顺序，天然契合函数调用、括号匹配、表达式求值等场景。

基础实现（数组顺序栈）

public class ArrayStack {
    private String[] items;
    private int count; // 栈中元素个数
    private int n;     // 栈的容量

    public ArrayStack(int n) {
        this.items = new String[n];
        this.n = n;
        this.count = 0;
    }

    // 入栈：O(1)
    public boolean push(String item) {
        if (count == n) return false; // 栈满，拒绝入栈
        items[count++] = item;
        return true;
    }

    // 出栈：O(1)
    public String pop() {
        if (count == 0) return null; // 栈空，返回 null
        return items[--count];
    }
}

• 入栈/出栈时间复杂度：O(1)
• 支持动态扩容的栈：底层依赖动态数组，入栈均摊时间复杂度为 O(1)

典型应用

括号匹配：遍历字符串，遇左括号入栈，遇右括号出栈匹配；最终栈为空则合法。

函数调用栈：每进入一个函数，将临时变量作为栈帧入栈；函数返回时出栈。这是操作系统为每个线程分配独立内存空间的原因——栈帧天然隔离了局部变量。

表达式求值：使用两个栈（操作数栈 + 运算符栈），按运算符优先级决定是否立即计算。

浏览器前进/后退：用两个栈 X 和 Y，访问新页面压入 X；后退时从 X 弹出压入 Y；前进时从 Y 弹出压入 X。

队列

队列（Queue） 是操作受限的线性表，支持先进先出（FIFO），一端入队（enqueue）、另一端出队（dequeue）。

顺序队列（数组实现）

public class ArrayQueue {
    private String[] items;
    private int n;
    private int head = 0; // 队头指针
    private int tail = 0; // 队尾指针

    public ArrayQueue(int capacity) {
        items = new String[capacity];
        n = capacity;
    }

    public boolean enqueue(String item) {
        if (tail == n) {
            if (head == 0) return false; // 真正满了
            // 数据搬移：将 [head, tail) 整体前移
            for (int i = head; i < tail; ++i) items[i - head] = items[i];
            tail -= head;
            head = 0;
        }
        items[tail++] = item;
        return true;
    }

    public String dequeue() {
        if (head == tail) return null; // 队空
        return items[head++];
    }
}

顺序队列的问题：随着入队/出队，head 和 tail 不断右移，最终 tail == n 时触发数据搬移，均摊复杂度 O(1)，但不优雅。循环队列彻底解决这个问题。

循环队列

将数组首尾相连，tail 到达末尾后自动回绕到 0，完全避免数据搬移。

public class CircularQueue {
    private String[] items;
    private int n, head = 0, tail = 0;

    public CircularQueue(int capacity) {
        items = new String[capacity];
        n = capacity;
    }

    public boolean enqueue(String item) {
        if ((tail + 1) % n == head) return false; // 队满（牺牲一个位置区分队满/队空）
        items[tail] = item;
        tail = (tail + 1) % n;
        return true;
    }

    public String dequeue() {
        if (head == tail) return null; // 队空
        String ret = items[head];
        head = (head + 1) % n;
        return ret;
    }
}

状态	判断条件	说明
队空	head == tail	两指针重合
队满	(tail + 1) % n == head	牺牲一个槽位避免与队空混淆

为什么要牺牲一个槽位？ 若不牺牲，队满时 head == tail，与队空条件相同，无法区分。

阻塞队列与并发队列

阻塞队列：队列为空时出队阻塞，队列已满时入队阻塞。天然实现生产者-消费者模型，无需手动写等待/唤醒逻辑。

并发队列：线程安全的队列。最简单方式是在 enqueue/dequeue 加锁，但并发度低。基于数组循环队列 + CAS 原子操作可实现高效无锁并发队列（如 Disruptor）。

操作	时间复杂度
入队	O(1)
出队	O(1)
查看队头	O(1)

跳表

跳表（Skip List） 是对有序链表加多级索引的动态数据结构，可支持 O(logn) 的插入、删除、查找。

核心思想

对链表每隔两个节点抽一个节点建立上层索引，形成多级索引结构：

第2级索引：  1 ─────────────> 7 ─────────────> 13
第1级索引：  1 ──────> 4 ──> 7 ──> 10 ─────> 13
原始链表：   1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13

查找时从最高级索引开始，逐层下降，每层最多遍历 3 个节点。

为什么能达到 O(logn)？ 每向上一层索引，节点数减半（类似二分查找）。有 n 个节点时，索引层数约为 $\log_2 n$，每层遍历 O(1) 个节点，总时间 $O(\log n)$。

空间复杂度：额外索引节点约为 $n/2 + n/4 + \cdots = n$，即 O(n)。

复杂度对比

维度	跳表	红黑树
查找	O(logn)	O(logn)
插入	O(logn)	O(logn)
删除	O(logn)	O(logn)
区间查找	O(logn) + 顺序遍历，高效	较复杂
空间复杂度	O(n)（索引节点约 n 个）	O(n)
实现难度	相对简单	复杂（旋转、变色）

Redis 为什么用跳表而不用红黑树？

1. 区间查找高效：跳表定位区间起点后可直接顺序遍历原始链表；红黑树的中序遍历实现相对复杂
2. 实现更简单：跳表代码可读性好，不易出错，便于维护
3. 灵活性：可通过调整索引策略平衡效率与内存消耗

索引动态更新

插入新节点时，通过随机函数决定将该节点插入哪几级索引（第1级到第k级）。从概率上保证索引与数据规模的平衡，避免退化为单链表。这是跳表"以概率换确定性"的核心设计：无需像红黑树那样做复杂的旋转平衡。

参考资料

• 《数据结构与算法之美》— 05~09、17 章节