数据结构学习笔记

2026年4月28日 | 加载中...

为什么学数据结构

写代码能跑 ≠ 代码写得好。数据结构选对了，性能可能差十倍、百倍。面试也会考，但更重要的是日常开发中做技术决策时不抓瞎。

数组 (Array)

最基础的结构，连续内存存储，下标随机访问 O(1)。

const arr = [1, 2, 3];
arr.push(4);     // O(1) 均摊
arr.unshift(0);  // O(n) 要移动所有元素
arr[2];          // O(1) 随机访问

适合： 读多写少、已知大小、需要随机访问的场景。

链表 (Linked List)

每个节点存值 + 指向下个节点的引用，不连续存储。

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

const list = new Node(1, new Node(2, new Node(3)));

操作	数组	链表
随机访问	O(1)	O(n)
头部插入	O(n)	O(1)
尾部插入	O(1) 均摊	O(1)（有尾指针时）
中间插入	O(n)	O(1)（已知位置时）

适合： 频繁插入删除、不需要随机访问的场景。LRU 缓存、浏览器前进后退都用它。

栈 (Stack)

后进先出（LIFO），就两件事：压入和弹出。

const stack = [];
stack.push(1);
stack.push(2);
stack.pop(); // 2

应用场景：

函数调用栈（递归的本质）
括号匹配
撤销/重做功能
浏览器历史记录

队列 (Queue)

先进先出（FIFO），一头进一头出。

// JS 没有原生队列，数组模拟即可
const queue = [];
queue.push(1); // 入队
queue.push(2);
queue.shift(); // 出队 → 1

应用场景：

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

进阶：优先队列（Priority Queue），出队顺序按优先级而非先进先出。JS 里可用最小堆实现，或直接用排序数组（数据量小时够用）。

哈希表 (Hash Table)

键值对存储，通过哈希函数直接定位，平均 O(1) 读写。

const map = new Map();
map.set('name', 'resigned');
map.get('name'); // O(1)

const obj = { name: 'resigned' };
obj['name']; // 也是哈希表的思路

核心问题：哈希冲突。 常见解法：

拉链法：冲突的位置挂链表（Java HashMap 的做法）
开放寻址法：冲突了就找下一个空位

注意： 最坏情况退化到 O(n)（所有 key 都冲突时），但概率极低。

树 (Tree)

二叉搜索树（BST）

左子树 < 根 < 右子树，中序遍历得到有序序列。

查找/插入/删除：平均 O(log n)，最坏 O(n)（退化为链表）

平衡二叉树

为了防止退化，引入自平衡机制（AVL 树、红黑树）。红黑树是 Java TreeMap、C++ std::map 的底层实现。

堆（Heap）

特殊的完全二叉树，分为最大堆和最小堆。

// 最小堆 — JavaScript 没有原生堆，手写或用库
// 用途：优先队列、Top K 问题、堆排序

关键操作：

插入：O(log n)
取极值：O(log n)
查看极值：O(1)

图 (Graph)

由节点（顶点）和边组成，比树更通用（允许环、多对多关系）。

两种存储方式：

// 邻接矩阵 — 适合稠密图
const matrix = [
  [0, 1, 1],
  [1, 0, 0],
  [1, 0, 0],
];

// 邻接表 — 适合稀疏图，更常用
const graph = {
  A: ['B', 'C'],
  B: ['A'],
  C: ['A'],
};

两种遍历：

BFS（广度优先）：用队列，适合找最短路径
DFS（深度优先）：用栈/递归，适合连通性检测、拓扑排序

应用： 社交网络、导航路线、依赖管理（npm install 的依赖树就是个 DAG）。

复杂度速查

数据结构	访问	查找	插入	删除
数组	O(1)	O(n)	O(n)	O(n)
链表	O(n)	O(n)	O(1)	O(1)
栈	O(n)	O(n)	O(1)	O(1)
队列	O(n)	O(n)	O(1)	O(1)
哈希表	—	O(1)	O(1)	O(1)
BST	O(log n)	O(log n)	O(log n)	O(log n)
堆	O(n)	O(n)	O(log n)	O(log n)

学习建议

不要背代码，理解原理更重要。面试时能说出思路比默写实现有价值。
自己手写一遍经典结构（链表、BST、哈希表），写一次比看十遍管用。
刷题时归类：看到「最短路径」→ BFS，「括号匹配」→ 栈，「Top K」→ 堆。建立条件反射。
日常开发中有意识地选型：需要快速查找？Map。需要有序？排序数组或 BST。需要频繁首尾操作？Deque。

学数据结构不是为了面试，是为了在写代码的时候脑子里有更多选择。