数据结构入门：数组、链表、栈、队列、哈希表

为什么要懂数据结构？

很多新手疑问：

"我用 array.push() 不就行了，为什么还要懂什么链表、哈希表？"

答案是：当数据量从 100 增加到 100 万时，选错数据结构会让你的程序从 1 毫秒变成 10 秒。 这不是夸张，是数学。

下面我们用最直白的比喻，把 5 个核心数据结构讲清楚。

1. 数组（Array）—— 一排连号的储物柜

[ 'a', 'b', 'c', 'd', 'e' ]
   0    1    2    3    4

特点：

• 元素连续存放在一段内存里
• 每个元素都有一个"门牌号"（索引）
• 通过索引可以直接跳到任何位置

操作	时间复杂度	解释
访问 arr[i]	O(1)	直接知道地址
末尾添加 push	O(1)	加到最后
中间插入 / 删除	O(n)	后面所有元素要"挪位置"
查找元素	O(n)	需要遍历

适用场景：当你"经常按下标访问，不经常中间插入删除"。

const arr = [10, 20, 30, 40];
arr[2];        // 30  —— O(1) 极快
arr.push(50);  // O(1)
arr.unshift(0);// O(n) ⚠️ 注意：在头部插入要挪所有元素！

2. 链表（Linked List）—— 一串牵着手的人

[1 | →] -> [2 | →] -> [3 | →] -> null

每个节点存"自己的值 + 下一个节点的引用"。

特点：

• 不连续存放
• 想找第 5 个，必须从第 1 个一路走到第 5 个
• 但是插入 / 删除超快，只要把"手"拉到新人身上

操作	时间复杂度
访问第 i 个	O(n)
头部插入 / 删除	O(1)
已知节点处的插入 / 删除	O(1)

适用场景：频繁在中间插入 / 删除，且不需要随机访问。

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// 1 -> 2 -> 3
const a = new Node(1);
a.next = new Node(2);
a.next.next = new Node(3);

3. 栈（Stack）—— 像一摞盘子

后进先出（LIFO：Last In First Out）

push -->  ┌───┐
          │ 3 │  <- top
          │ 2 │
          │ 1 │
          └───┘  <-- pop 也从这里出

const stack = [];
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop();      // 3  ← 最后放的最先取出

真实场景：

• 浏览器后退按钮（最后访问的页面最先回去）
• 编辑器的撤销功能
• 函数调用栈（这就是为什么递归过深会"栈溢出"）

4. 队列（Queue）—— 像排队买奶茶

先进先出（FIFO：First In First Out）

入队 -->  [ 1 | 2 | 3 | 4 ]  --> 出队

const queue = [];
queue.push(1);     // 入队
queue.push(2);
queue.shift();     // 1  ← 最先入的最先出

⚠️ JS 用数组模拟队列时，shift() 是 O(n)。在性能敏感场景请用专门的队列实现（比如双端队列）。

真实场景：

• 消息队列（Kafka、RabbitMQ）
• 任务调度
• BFS（广度优先搜索）

5. 哈希表（Hash Table）—— 一本目录表

学会哈希表，你就掌握了 80% 的"加速秘籍"。

哈希表通过一个"哈希函数"把键转换为数组下标，让你能以 O(1) 完成查找。

// JS 的 Map 就是哈希表
const phonebook = new Map();
phonebook.set("Tom", "13800001111");
phonebook.set("Jerry", "13800002222");

phonebook.get("Tom");        // "13800001111"  ← O(1)！
phonebook.has("Jerry");      // true
phonebook.delete("Tom");

操作	时间复杂度
查找 / 添加 / 删除	平均 O(1)
最坏情况	O(n)（极端哈希冲突）

经典案例：用哈希表把 O(n²) 变 O(n)

题目：给一个数组和一个目标和，找出和为目标值的两个数。

// ❌ 暴力解：O(n²)
function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
}

// ✅ 哈希表：O(n)
function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
}

数据从 1 万到 100 万时，前者从"等几秒"变成"等几小时"，后者依然是"瞬间"。

一张速查表

数据结构	强项	弱项	典型用途
数组	随机访问	中间插入/删除	列表、缓冲区
链表	任意位置插入/删除	随机访问	待办列表、LRU
栈	后进先出	不能直接访问中间	撤销、回退、递归
队列	先进先出	同上	消息、调度
哈希表	O(1) 查找	不维护顺序	缓存、去重、计数

怎么选？

每次遇到新问题，问自己 3 个问题：

1. 要按下标访问吗？ → 选数组
2. 要根据"键"快速查找吗？ → 选哈希表
3. 关心顺序还是不关心？
   • 后进先出 → 栈
   • 先进先出 → 队列
   • 频繁中间插入 → 链表

接下来该学什么？

学完这五个，你已经能写出"快十倍"的代码了。下一步推荐：

• 树（Tree）：尤其是二叉搜索树和堆
• 图（Graph）：路径搜索、网络分析
• 排序与查找：快排、二分查找
• 动态规划：解决"看似要穷举"的问题

「为之于未有，治之于未乱。」 ——选对数据结构，是解决问题的"未有"之时。