【数据结构】数组 vs 链表：什么时候用哪个？

面试官：「数组和链表有什么区别？」

你：「数组是连续内存，链表是不连续的，用指针连起来。」

面试官：「嗯，然后呢？」

你：「……」

这个场景是不是很熟悉？

数组和链表是最基础的两种数据结构，基础到我们觉得「谁不知道啊」。但真要深入聊，很多人又说不清楚。

今天小明带你彻底搞懂这俩「老朋友」：它们到底有什么区别？什么时候用数组？什么时候用链表？为什么 Java 的 ArrayList 底层是数组而不是链表？

从一个真实问题说起

假设你在开发一个音乐播放器，需要管理用户的播放列表。

播放列表需要支持这些操作：

1. 按顺序播放（从头到尾遍历）
2. 随机播放（随机访问某首歌）
3. 添加新歌（可能在开头、中间或末尾）
4. 删除歌曲（可能删除任意位置）
5. 显示歌曲总数

你会用数组还是链表来存储播放列表？

先别急着回答，让我们一步步分析。

数组：住在连排别墅的邻居

数组的本质

数组是一段连续的内存空间，存储相同类型的元素。

你可以把数组想象成一排连体别墅：

• 每栋别墅大小相同（元素类型相同）
• 别墅紧挨着盖（内存连续）
• 每栋别墅有门牌号（索引，从 0 开始）

内存地址:  1000   1004   1008   1012   1016   1020
          ┌──────┬──────┬──────┬──────┬──────┬──────┐
数组:     │  10  │  20  │  30  │  40  │  50  │  60  │
          └──────┴──────┴──────┴──────┴──────┴──────┘
索引:        0      1      2      3      4      5

数组的超能力：随机访问

想访问索引为 3 的元素？

元素地址 = 起始地址 + 索引 × 元素大小
        = 1000 + 3 × 4
        = 1012

一次计算，直接定位，时间复杂度 O(1)。

这就像你去找朋友，知道他住在「阳光小区 15 号楼」，直接就能找到，不用从 1 号楼开始一栋一栋问。

// 随机访问：O(1)
const arr = [10, 20, 30, 40, 50, 60];
console.log(arr[3]); // 直接拿到 40，不需要遍历前面的元素

数组的软肋：插入和删除

但数组有个致命弱点——中间插入和删除元素很麻烦。

想在索引 2 的位置插入一个 25：

插入前: [10, 20, 30, 40, 50, 60]
                 ↑
              要插入 25

第1步: 把 30,40,50,60 全部往后挪一位
       [10, 20, __, 30, 40, 50, 60]

第2步: 在空出来的位置放入 25
       [10, 20, 25, 30, 40, 50, 60]

要插入一个元素，后面所有元素都得搬家。平均下来要移动 n/2 个元素，时间复杂度 O(n)。

删除同理，删掉一个元素后，后面的元素要往前补位。

// 插入操作：O(n)
function insertAt(arr, index, value) {
  // 从后往前，每个元素往后挪一位
  for (let i = arr.length; i > index; i--) {
    arr[i] = arr[i - 1];
  }
  arr[index] = value;
}

// 删除操作：O(n)
function removeAt(arr, index) {
  // 从删除位置开始，每个元素往前挪一位
  for (let i = index; i < arr.length - 1; i++) {
    arr[i] = arr[i + 1];
  }
  arr.length--;
}

小明冷笑话时间：

数组就像坐地铁。你上车后想挤到中间去？不好意思，所有人都得挪一挪。

链表：住在散落各处的邻居

链表的本质

链表是通过指针把一堆不连续的内存串起来。

每个链表节点包含两部分：

1. 数据域：存实际的值
2. 指针域：存下一个节点的地址

节点1              节点2              节点3
┌──────┬──────┐   ┌──────┬──────┐   ┌──────┬──────┐
│  10  │  ●───┼──▶│  20  │  ●───┼──▶│  30  │ null │
└──────┴──────┘   └──────┴──────┘   └──────┴──────┘
地址: 1000         地址: 2048         地址: 1520

注意看，三个节点的地址是 1000、2048、1520，完全不连续。它们靠指针（箭头）连在一起。

你可以把链表想象成寻宝游戏：

• 每个地点有一张纸条
• 纸条上写着下一个地点的位置
• 你必须按顺序一个一个找

链表的超能力：插入和删除

想在 10 和 30 之间插入 20？

插入前:
节点1              节点3
┌──────┬──────┐   ┌──────┬──────┐
│  10  │  ●───┼──▶│  30  │ null │
└──────┴──────┘   └──────┴──────┘

插入后:
节点1              节点2              节点3
┌──────┬──────┐   ┌──────┬──────┐   ┌──────┬──────┐
│  10  │  ●───┼──▶│  20  │  ●───┼──▶│  30  │ null │
└──────┴──────┘   └──────┴──────┘   └──────┴──────┘

只需要：

1. 创建新节点
2. 新节点指向原来的下一个节点
3. 前一个节点指向新节点

两三个指针的操作，时间复杂度 O(1)（假设已经找到了插入位置）。

// 链表节点定义
class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

// 在某个节点后插入新节点：O(1)
function insertAfter(node, value) {
  const newNode = new ListNode(value);
  newNode.next = node.next;  // 新节点指向原来的下一个
  node.next = newNode;       // 当前节点指向新节点
}

// 删除某个节点的下一个节点：O(1)
function removeAfter(node) {
  if (node.next) {
    node.next = node.next.next;  // 跳过下一个节点
  }
}

删除也一样简单，只需要把指针「跳过」要删除的节点即可。

链表的软肋：随机访问

链表最大的问题是不支持随机访问。

想访问第 3 个元素？不好意思，你得从头开始，一个一个往后找。

// 访问第 n 个元素：O(n)
function getAt(head, index) {
  let current = head;
  for (let i = 0; i < index && current; i++) {
    current = current.next;  // 只能一步一步走
  }
  return current ? current.val : undefined;
}

这就像玩寻宝游戏，你想直接去第 5 个地点？抱歉，你必须先去 1、2、3、4，因为只有到了第 4 个地点才知道第 5 个地点在哪。

数组 vs 链表：全面对比

时间复杂度对比

*数组尾部插入在不扩容的情况下是 O(1)，扩容时是 O(n) **单链表需要遍历到尾部；双链表可以 O(1)

空间复杂度对比

// 数组存储 4 个整数（假设每个整数 4 字节）
// 总内存：4 × 4 = 16 字节

// 链表存储 4 个整数（假设指针 8 字节）
// 每个节点：4（数据）+ 8（指针）= 12 字节
// 总内存：12 × 4 = 48 字节

链表每个节点都要额外存储一个指针，空间开销更大。

内存布局对比

数组（连续内存）：
┌────┬────┬────┬────┬────┐
│ A  │ B  │ C  │ D  │ E  │
└────┴────┴────┴────┴────┘
  ↑连续存放，CPU 缓存友好

链表（离散内存）：
    ┌───┐          ┌───┐
    │ A │          │ C │
    └───┘          └───┘
         ┌───┐          ┌───┐
         │ B │          │ D │
         └───┘          └───┘
  ↑分散存放，CPU 缓存不友好

CPU 缓存友好性是很容易被忽略的一点。

现代 CPU 访问内存时，不是一个字节一个字节读，而是一次读一个「缓存行」（通常 64 字节）。

数组是连续存储的，读第一个元素时，后面的元素可能已经被一起加载到缓存了。而链表节点分散在内存各处，每次访问可能都要重新从内存读取，速度会慢很多。

实际测试：遍历 100 万个元素，数组可能比链表快 10 倍以上。

真实场景：如何选择？

回到开头的播放列表问题。

场景分析

*动态数组摊还复杂度 **需要先 O(n) 找到位置 ***如果维护 size 变量

结论

对于播放列表这个场景，用数组（动态数组）更合适。

原因：

1. 随机播放需要随机访问，数组 O(1)，链表 O(n)
2. 顺序播放时，数组的缓存友好性带来更好的性能
3. 添加歌曲通常在末尾，数组也是 O(1)
4. 删除操作虽然数组是 O(n)，但这个操作不频繁

这也是为什么大多数编程语言的「列表」类型（如 Python 的 list、Java 的 ArrayList、JavaScript 的 Array）底层都用数组实现。

什么时候用链表？

链表适合以下场景：

1. 频繁在头部插入/删除

// 实现一个栈（LIFO）
// 用链表：push 和 pop 都是 O(1)
class Stack {
  constructor() {
    this.head = null;
  }
  
  push(val) {
    const node = new ListNode(val);
    node.next = this.head;
    this.head = node;  // O(1)
  }
  
  pop() {
    if (!this.head) return undefined;
    const val = this.head.val;
    this.head = this.head.next;  // O(1)
    return val;
  }
}

2. 频繁在中间插入/删除，且已知位置

// 文本编辑器的撤销历史
// 每次编辑在当前位置插入一个操作
// 链表可以 O(1) 插入

// LRU 缓存
// 需要频繁移动元素到头部
// 链表 + 哈希表的组合非常适合

3. 不知道数据量大小，不想处理扩容

数组需要预分配空间，空间不够要扩容（分配新数组 + 复制数据）。链表可以随用随分配。

4. 需要合并或分割

// 合并两个有序链表：O(n)
// 只需要改指针，不需要移动数据

// 如果用数组合并，需要开辟新数组，复制所有数据

进阶：链表的变种

双向链表

每个节点有两个指针：指向前一个和后一个。

       ┌──────────────┐       ┌──────────────┐
       │              │       │              │
   ┌───┴───┐      ┌───┴───┐      ┌─────────┐
   │ prev  │      │ prev  │      │  prev   │
   │  10   │◀────▶│  20   │◀────▶│   30    │
   │ next  │      │ next  │      │  next   │
   └───────┘      └───────┘      └─────────┘

优点：

• 可以从尾部开始遍历
• 删除任意节点是 O(1)（单链表需要知道前一个节点）

缺点：

• 每个节点多一个指针，更费内存
• 插入删除时要维护两个指针，更容易出错

循环链表

尾节点的 next 指向头节点，形成一个环。

   ┌───────────────────────────────┐
   │                               │
   ▼                               │
┌─────┐    ┌─────┐    ┌─────┐    │
│ 10  │───▶│ 20  │───▶│ 30  │────┘
└─────┘    └─────┘    └─────┘

适用场景：

• 轮询调度（Round-Robin）
• 约瑟夫环问题
• 循环播放列表

跳表（Skip List）

在链表基础上加多层索引，支持 O(log n) 的查找。

第3层:  1 ─────────────────────────▶ 9
        │                           │
第2层:  1 ──────────▶ 5 ────────────▶ 9
        │            │               │
第1层:  1 ───▶ 3 ───▶ 5 ───▶ 7 ────▶ 9
        │     │     │     │         │
第0层:  1 ─ 2 ─ 3 ─ 4 ─ 5 ─ 6 ─ 7 ─ 8 ─ 9

Redis 的有序集合（Sorted Set）就是用跳表实现的。

代码实战：实现一个播放列表

让我们用 JavaScript 实现一个简单的播放列表，分别用数组和链表，看看有什么区别。

数组版本

class PlaylistArray {
  constructor() {
    this.songs = [];
    this.currentIndex = 0;
  }

  // 添加歌曲到末尾：O(1) 摊还
  add(song) {
    this.songs.push(song);
  }

  // 删除指定位置的歌曲：O(n)
  remove(index) {
    if (index >= 0 && index < this.songs.length) {
      this.songs.splice(index, 1);
      // 调整当前播放位置
      if (index < this.currentIndex) {
        this.currentIndex--;
      }
    }
  }

  // 随机播放：O(1)
  playRandom() {
    const randomIndex = Math.floor(Math.random() * this.songs.length);
    this.currentIndex = randomIndex;
    return this.songs[randomIndex];
  }

  // 下一首：O(1)
  next() {
    this.currentIndex = (this.currentIndex + 1) % this.songs.length;
    return this.songs[this.currentIndex];
  }

  // 上一首：O(1)
  prev() {
    this.currentIndex = (this.currentIndex - 1 + this.songs.length) % this.songs.length;
    return this.songs[this.currentIndex];
  }

  // 获取当前歌曲：O(1)
  current() {
    return this.songs[this.currentIndex];
  }

  // 歌曲总数：O(1)
  get length() {
    return this.songs.length;
  }
}

链表版本（双向循环链表）

class SongNode {
  constructor(song) {
    this.song = song;
    this.prev = null;
    this.next = null;
  }
}

class PlaylistLinkedList {
  constructor() {
    this.head = null;
    this.current = null;
    this.size = 0;
  }

  // 添加歌曲到末尾：O(1)
  add(song) {
    const newNode = new SongNode(song);
    
    if (!this.head) {
      // 第一首歌
      newNode.next = newNode;
      newNode.prev = newNode;
      this.head = newNode;
      this.current = newNode;
    } else {
      // 插入到末尾（head 的前面）
      const tail = this.head.prev;
      newNode.next = this.head;
      newNode.prev = tail;
      tail.next = newNode;
      this.head.prev = newNode;
    }
    this.size++;
  }

  // 删除当前节点：O(1)
  removeCurrent() {
    if (!this.current) return;

    if (this.size === 1) {
      this.head = null;
      this.current = null;
    } else {
      const toRemove = this.current;
      toRemove.prev.next = toRemove.next;
      toRemove.next.prev = toRemove.prev;
      
      if (toRemove === this.head) {
        this.head = toRemove.next;
      }
      this.current = toRemove.next;
    }
    this.size--;
  }

  // 随机播放：O(n) —— 这是链表的弱点
  playRandom() {
    const randomIndex = Math.floor(Math.random() * this.size);
    let node = this.head;
    for (let i = 0; i < randomIndex; i++) {
      node = node.next;
    }
    this.current = node;
    return node.song;
  }

  // 下一首：O(1)
  next() {
    if (this.current) {
      this.current = this.current.next;
      return this.current.song;
    }
    return null;
  }

  // 上一首：O(1)
  prev() {
    if (this.current) {
      this.current = this.current.prev;
      return this.current.song;
    }
    return null;
  }

  // 获取当前歌曲：O(1)
  currentSong() {
    return this.current ? this.current.song : null;
  }

  // 歌曲总数：O(1)
  get length() {
    return this.size;
  }
}

对比

如果随机播放是主要功能，数组版本更好。 如果频繁删除当前歌曲，链表版本更好。

面试高频问题

Q1：数组和链表的区别？

标准答案：

Q2：什么时候用数组？什么时候用链表？

答：

• 读多写少，需要随机访问 → 数组
• 写多读少，频繁插入删除 → 链表
• 不确定的话，优先用数组（更通用，性能更好）

Q3：为什么 Java 的 ArrayList 用数组而不是链表？

答：

1. 大多数场景读操作比写操作多
2. 数组的缓存友好性带来更好的实际性能
3. 尾部插入是 O(1)，覆盖了大部分插入场景
4. 内存更紧凑，空间利用率高

Q4：反转链表怎么做？

这是链表最经典的面试题：

function reverseList(head) {
  let prev = null;
  let curr = head;
  
  while (curr) {
    const next = curr.next;  // 保存下一个
    curr.next = prev;        // 反转指向
    prev = curr;             // 移动 prev
    curr = next;             // 移动 curr
  }
  
  return prev;
}

总结

今天我们深入对比了数组和链表：

1. 数组：连续内存，随机访问 O(1)，插入删除 O(n)，缓存友好
2. 链表：离散内存，顺序访问 O(n)，插入删除 O(1)，缓存不友好
3. 选择原则：读多写少用数组，写多读少用链表，不确定就用数组
4. 实际应用：大多数场景数组更合适，链表在特定场景（LRU、栈实现）有优势

记住一句话：

数组是「住在一起的邻居」，找人方便；链表是「散落各地的朋友」，串门方便。

下次面试官问你数组和链表的区别，不要只说「连续/不连续」了，把今天学的都告诉他，让他刮目相看。

小明冷笑话收尾：

问：数组和链表谁更受欢迎？ 答：数组，因为它有「下标」（index），而链表只能一个一个「追」（next）。

在感情里也一样，直接说出门牌号比说「我住在你隔壁的隔壁的隔壁」有效率多了。

「数据结构不难，难的是知道什么时候用哪个。」—— 小明