前端核心数据结构与算法
一、 核心数据结构 (Core Data Structures)
数据结构是组织、管理和存储数据的方式，是算法得以实现的基础。
| 数据结构 (Data Structure) | 概念定义 (Concept) | 核心操作与复杂度 (Operations & Complexity) | 典型应用 (Applications) |
|---|---|---|---|
| 数组 (Array) | 一种线性表数据结构，用一组连续的内存空间来存储一组具有相同类型的数据。 | - 读取/修改 (Read/Update): O(1) - 插入/删除 (Insert/Delete): O(n) | 作为其他数据结构的基础、存储列表数据、函数参数 ...args。 |
| 链表 (Linked List) | 一种线性表数据结构，通过"指针"将一组零散的内存空间串联起来。 | - 读取/修改 (Read/Update): O(n) - 插入/删除 (Insert/Delete): O(1) (已知节点) | React Fiber 链表、LRU 缓存、JS 原型链。 |
| 栈 & 队列 (Stack & Queue) | 两种受限的线性数据结构。栈是后进先出 (LIFO)，队列是先进先出 (FIFO)。 | - 所有操作 (All Operations): O(1) | 栈: 函数调用栈、括号匹配、撤销操作。 队列: JS 事件循环 (Event Loop)、BFS 算法、任务调度。 |
| 哈希表 (Hash Table) | 通过哈希函数将键 (Key) 映射到桶 (Bucket) 中的位置，以实现快速查找。JS 中的 Map 和 Set 都是其实现。 | - 增/删/查/改 (CRUD): 平均 O(1)，最坏 O(n) | 缓存、键值对存储 (Map)、去重 (Set)、React Hooks 依赖数组。 |
| 树 (Tree) | 由 n (n>0) 个有限节点组成一个具有层次关系的集合，每个节点有零个或多个子节点。 | - 遍历 (Traversal): O(n) - 查找/增/删 (BST): 平均 O(log n) | DOM 树、AST (抽象语法树)、级联选择器、路由系统。 |
| 图 (Graph) | 由"顶点"(Vertex) 和"边"(Edge) 组成的数据结构，用于表示对象之间的复杂关系。 | - 存储: 邻接矩阵 O(V^2) 空间, 邻接表 O(V+E) 空间 | 社交网络、依赖关系图 (Webpack)、地铁线路图、路径规划。 |
| 堆 (Heap) | 一种特殊的完全二叉树。分为大顶堆（父节点 > 子节点）和小顶堆（父节点 < 子节点）。 | - 插入 (Insert): O(log n) - 取最值 (Get Max/Min): O(1) - 删除最值 (Delete Max/Min): O(log n) | 优先队列、Top-K 问题、Dijkstra 算法、堆排序。 |
| Trie / 前缀树 | 一种高效存储和检索字符串集合的多叉树结构，通过共享前缀来节省空间。 | - 插入/查找 (Insert/Search): O(L) (L 为字符串长度) | 搜索框自动补全、拼写检查、IP 路由。 |
二、 核心算法思想 (Core Algorithm Paradigms)
算法是解决特定问题的步骤和指令集合，是程序的灵魂。
| 算法名称 (Algorithm) | 概念定义 (Concept) | 工作原理 (How it Works) | 时间复杂度 (Time) | 空间复杂度 (Space) | 典型应用 (Applications) |
|---|---|---|---|---|---|
| 二分查找 (Binary Search) | 一种在有序数组中查找某一特定元素的搜索算法。 | 不断将搜索区间对半分割，每次排除一半的元素，直到找到目标或区间为空。 | O(log n) | O(1) | 搜索、Git bisect、寻找特定版本。 |
| 分治 (Divide & Conquer) | 将大问题递归地分解成若干个同结构、更小的子问题，再将子问题的解合并，得到原问题的解。 | 分解 (Divide) -> 解决 (Conquer) -> 合并 (Combine)。递归是其主要实现方式。 | O(n log n) (常见) | O(log n) 或 O(n) | 归并/快速排序、React Fiber 任务分解。 |
| 动态规划 (DP) | 通过将原问题分解为相互重叠的子问题，并存储子问题的解，来避免重复计算，从而求解复杂问题。 | 寻找最优子结构，定义状态转移方程，自底向上递推求解。 | 通常 O(n^2) 或更高 | 通常 O(n) 或 O(n^2) | VDOM Diff (最小编辑距离)、背包问题、最长递增子序列。 |
| 贪心 (Greedy) | 在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优。 | 做出局部最优选择，并期望该选择能导向全局最优。不能保证得到最优解。 | 取决于具体问题 | O(1) 或 O(n) | 区间选点、哈夫曼编码、Dijkstra 算法。 |
| 回溯 (Backtracking) | 一种通过探索所有可能的候选解来找出所有解的算法。若发现候选解不满足，则"回溯"到上一步，尝试其他选择。 | 基于 DFS 策略，通过决策树进行深度探索，并辅以"剪枝"操作优化。 | 指数级 O(k^n) | O(n) (递归深度) | 全排列、组合、N 皇后、解数独、迷宫问题。 |
| 双指针 (Two Pointers) | 在序列上使用两个指针，通过同向或对向移动来遍历和处理数据，以降低时间复杂度。 | 两指针根据特定条件移动，协同完成任务，常用于有序数组或链表。 | 通常 O(n) | O(1) | 有序数组求和、链表反转/环检测、字符串反转。 |
| 滑动窗口 (Sliding Window) | 在序列上维护一个大小可变的连续区间（窗口），通过移动窗口的左右边界来高效解决子数组/子串问题。 | 维护一个窗口，根据窗口内的状态决定是扩大窗口（右指针移动）还是缩小窗口（左指针移动）。 | 通常 O(n) | O(k) (k为窗口大小) | 寻找最小/最长覆盖子串、无重复字符的最长子串。 |
| DFS (深度优先搜索) | 沿着图或树的深度遍历，尽可能深地搜索，当节点v的所有边都已被探寻，则回溯到发现v的节点。 | 通过递归或栈实现，沿着一条路径走到黑，再回头。 | O(V+E) (图) / O(n) (树) | O(H) (H为深度) | DOM 遍历、拓扑排序、寻找连通分量、回溯算法基础。 |
| BFS (广度优先搜索) | 从根节点开始，沿着图或树的宽度遍历，先访问所有邻近节点，再逐层向外扩展。 | 通过队列实现，按层级、由近及远地探索。 | O(V+E) (图) / O(n) (树) | O(W) (W为宽度) | 无权图最短路径、层序遍历、寻找社交网络中的好友。 |
| KMP 字符串匹配 | 一种高效的字符串匹配算法，利用已匹配部分的信息，避免在失配时主串指针的回溯。 | 核心是构建 next 数组，记录模式串中每个前缀的"最长公共前后缀"，用于指导失配后的跳转。 | O(m+n) | O(m) (m为模式串长) | 文本编辑器查找、代码高亮、敏感词过滤。 |
| Diff 算法 | 高效对比两棵树（如 VDOM）的差异，计算出从旧树到新树的最小更新操作集。 | React: 双端比较优化。 Vue: 最长递增子序列优化。均是启发式算法，非严格最优解。 | O(n) (启发式) | O(n) | React/Vue 等框架的视图更新。 |
| LRU 缓存 | 最近最少使用 (Least Recently Used) 缓存淘汰策略。当缓存满时，优先淘汰最久未被访问的数据。 | 通常使用哈希表 + 双向链表实现。哈希表 O(1) 定位，链表 O(1) 移动。 | O(1) | O(k) (k为容量) | 缓存 API 响应、图片资源、路由组件。 |
| 防抖 & 节流 | 两种用于控制高频事件执行频率的函数。防抖是延迟执行，节流是固定间隔执行。 | 防抖: 在事件触发 n 秒后才执行，若 n 秒内再次触发，则重新计时。 节流: 规定时间内只能触发一次。 | O(1) | O(1) | scroll/resize 事件、输入联想、按钮防重复点击。 |