数据结构基础深度解析

一句话概括

数据结构本质是”数据怎么存、怎么取”。前端天天在用，但多数人停留在”会调 API”的层面——直到面试被问到”为什么 Array.shift 很慢”“LRU 怎么实现”“链表怎么判环”才卡壳。

本文聚焦四种最常被考、也最实用的基础结构：栈（LIFO）、队列（FIFO）、链表（非连续）、哈希表（键值映射）。把它们的操作复杂度和典型场景吃透，你就能在”这个需求该用什么结构”的问题上做对选择，而不是永远一把梭 Array。

核心知识点

1. 栈（Stack）：后进先出

栈只允许在一端（栈顶）进出，核心操作 push / pop / peek 都是 O(1)。它解决的是”后进的先处理”——函数调用栈、浏览器前进后退、撤销操作全是它的影子。

class Stack {
  #items = [];
  push(x) { this.#items.push(x); return this.size; } // O(1)
  pop() { if (this.isEmpty()) throw new Error('栈空'); return this.#items.pop(); } // O(1)
  peek() { return this.#items[this.#items.length - 1] ?? null; } // O(1)
  get size() { return this.#items.length; }
  isEmpty() { return this.#items.length === 0; }
}

// 经典应用：括号匹配（编译器解析代码的底层逻辑）
function isBalanced(s) {
  const stack = new Stack();
  const pair = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if ('([{'.includes(ch)) stack.push(ch);
    else if (pair[ch] !== stack.pop()) return false; // 右括号对不上栈顶左括号
  }
  return stack.isEmpty();
}
console.log(isBalanced('({[]})')); // true

2. 队列（Queue）：先进先出

队列在一端入队、另一端出队。朴素用数组 push + shift 实现出队是 O(n)（因为后面元素要整体前移），这是面试常考的性能坑。

// ❌ 用 shift 出队：每次都要搬移后续元素，O(n)
function badDequeue(arr) { return arr.shift(); }

// ✅ 循环数组（头尾指针）把出队降到 O(1)
class Queue {
  #buf = new Array(8);
  #head = 0; #tail = 0; #size = 0;
  enqueue(x) {
    this.#buf[this.#tail] = x;
    this.#tail = (this.#tail + 1) % this.#buf.length;
    if (++this.#size === this.#buf.length) this.#resize();
  }
  dequeue() {
    if (this.isEmpty()) throw new Error('队列空');
    const x = this.#buf[this.#head];
    this.#head = (this.#head + 1) % this.#buf.length;
    this.#size--;
    return x;
  }
  #resize() {
    const next = new Array(this.#buf.length * 2);
    for (let i = 0; i < this.#size; i++)
      next[i] = this.#buf[(this.#head + i) % this.#buf.length];
    this.#buf = next; this.#head = 0; this.#tail = this.#size;
  }
  isEmpty() { return this.#size === 0; }
}

队列是 BFS、事件循环任务队列、请求排队的底层结构。

3. 链表（Linked List）：非连续存储

链表每个节点存数据和指向下一个节点的指针，所以插入 / 删除是 O(1)，随机访问是 O(n)——和数组正好相反。

class ListNode {
  constructor(val, next = null) { this.val = val; this.next = next; }
}

// 反转链表（面试最高频）：三指针，一次遍历，O(n) 时间 O(1) 空间
function reverse(head) {
  let prev = null, cur = head;
  while (cur) { const next = cur.next; cur.next = prev; prev = cur; cur = next; }
  return prev;
}

// 快慢指针判环（Floyd）：快指针走两步、慢指针走一步，相遇即有环
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next; fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

对比记忆（这是面试必背的一张表）：

操作	数组	链表
头部插入 / 删除	O(n)	O(1)
尾部插入	O(1)	O(1)
按下标访问	O(1)	O(n)
中间插入（已知前驱）	O(n)	O(1)

4. 哈希表（Hash Table）：键值映射

哈希表用哈希函数把 key 映射成数组下标，平均 get / set / delete 都是 O(1)。冲突时常见两种策略：链地址法（同桶挂链表，JS 的 Map / Object 即用此法）和开放地址法（线性探测找下一个空位）。

class HashTable {
  #buckets = Array.from({ length: 8 }, () => []);
  #size = 0;
  #hash(key) {
    let h = 0;
    for (const ch of String(key)) h = (h * 31 + ch.charCodeAt(0)) >>> 0;
    return h % this.#buckets.length;
  }
  set(key, val) {
    const b = this.#buckets[this.#hash(key)];
    const entry = b.find(e => e.key === key);
    if (entry) entry.val = val;
    else { b.push({ key, val }); this.#size++; }
  }
  get(key) {
    const e = this.#buckets[this.#hash(key)].find(e => e.key === key);
    return e ? e.val : undefined;
  }
}

LRU 缓存是哈希表 + 双向链表的经典组合（Vue keep-alive 内部就是它）：哈希表 O(1) 定位节点，双向链表 O(1) 把节点移到”最近使用”头部、淘汰最久未用的尾部。

class LRUCache {
  #capacity; #map = new Map(); // Map 本身保持插入顺序，天然适合 LRU
  constructor(capacity) { this.#capacity = capacity; }
  get(key) {
    if (!this.#map.has(key)) return -1;
    const val = this.#map.get(key);
    this.#map.delete(key); this.#map.set(key, val); // 访问后移到末尾
    return val;
  }
  put(key, val) {
    if (this.#map.has(key)) this.#map.delete(key);
    this.#map.set(key, val);
    if (this.#map.size > this.#capacity) {
      this.#map.delete(this.#map.keys().next().value); // 删最久未用（队首）
    }
  }
}

其实你每天都在用

• 浏览器的前进 / 后退：导航历史就是栈，后退 = 出栈，前进 = 把页面再压回栈
• 事件循环的任务队列：微任务、宏任务本质是队列，先注册先执行（FIFO）
• Vue / React 虚拟 DOM diff：Fiber 用链表实现可中断的”深度优先 + 兄弟”遍历
• 对象的属性读取：obj.x 底层就是哈希表查表，O(1) 取属性
• keep-alive 缓存组件：按访问时间淘汰最久没用的，就是 LRU（哈希表 + 双向链表）
• Array.shift / unshift：在数组头部增删，底层要搬移后面所有元素 → 隐含的 O(n) 性能坑

常见误解（FAQ）

❌ 误区一：”数组能当栈也能当队列，为什么还要单独学？”

能，但在”头部频繁增删”时数组会暴露 O(n) 的 shift / unshift 成本。队列该用循环数组或链表，让出队也保持 O(1)。分不清这点，你写的”队列”在大数据量下会悄悄变慢。

❌ 误区二：”哈希表查找永远 O(1)”

平均是 O(1)，但哈希函数设计差、或负载因子过高时，大量 key 挤进同一个桶，退化成链表的 O(n)。JS 的 Map 用随机化哈希种子防”哈希碰撞 DoS”，但你自定义的哈希函数未必防得住。

❌ 误区三：”链表比数组好，因为增删快”

链表是用 O(n) 的随机访问换 O(1) 的插入删除。如果你需要频繁”按下标取第 k 个”，链表反而更慢。选结构看访问模式，不是看哪个”更高级”。

❌ 误区四：”反转链表要开新数组存值”

不需要。三指针原地反转，O(n) 时间 O(1) 空间。面试写反转还去 new Array 拷贝的，基本会被追问”能不能 O(1) 空间”。

一句话总结

数据结构不是背出来的，而是”在正确的场景选对容器”的直觉——栈管先后、队列管公平、链表管灵活增删、哈希表管极速查找，理解了它们的复杂度边界，你写出的代码才既跑得对、也跑得快。