一、 数据结构
数据结构是计算机存储、组织数据的方式。选择合适的数据结构可以有效提升程序的效率和性能。
1. 基础数据结构
1）数组
① 核心：在内存中连续存储，通过索引直接访问元素，效率高（O(1)）。
② JS中的达成：Array 类型。需要掌握其内置方法的时间复杂度（如 push/pop 是 O(1)， shift/unshift 是 O(n)）。
③ 应用场景：存储一系列有序的数据，如列表、矩阵。
2）栈
① 核心：后进先出（LIFO）的有序集合。只允许在栈顶进行添加（压栈）和移除（弹栈）处理。
② JS实现：可以用数组（push, pop）轻松模拟。
③ 应用场景：函数调用栈、撤销管理、括号匹配、表达式求值。
3）队列
① 核心：先进先出（FIFO）的有序集合。在尾部添加（入队），在头部移除（出队）。
② JS构建：可以用数组（push, shift）模拟，但 shift 性能不佳；或使用对象。
③ 变种：
• 双端队列：两端都可以添加和移除。
• 优先队列：元素按优先级出队，通常用堆实现。
4）链表
① 核心：元素（节点）在内存中不必连续，借助指针（在JS中是引用）连接在一起。
② 与数组对比：插入和删除操作（已知节点位置时）效率高（O(1)），但随机访问效率低（O(n)）。
③ 类型：
• 单向链表：节点包括数据和指向下一个节点的引用。
• 双向链表：节点还含有指向前一个节点的引用，可以双向遍历。
• 循环链表：尾节点指向头节点，形成环。
④ 应用场景：历史记录、轮播图、LRU缓存。
2. 非线性数据结构（集合与字典）
1）集合
① 核心：由无序且唯一（不重复）的元素组成。
② JS实现：Set 对象。
③ 应用场景：去重、判断元素是否存在。
2）字典 / 哈希表
① 核心：以键值对（[key, value]）形式存储数据。通过哈希函数将键映射到特定的位置，从而实现高效的查找、插入和删除（理想情况下O(1)）。
② JS实现：Object 或 Map（Map 的键可以是任何类型，且有序）。
③ 关键问题：哈希冲突（不同键映射到同一位置）及解决方案（如链地址法、线性探查）。
④ 应用场景：快速查找、缓存、实现对象。
3. 树形结构
1）树的基本概念：根节点、父节点、子节点、叶节点、深度、高度。
2）二叉树：每个节点最多有两个子节点（左子节点和右子节点）。
3）二叉搜索树
① 核心：左子树上所有节点的值小于根节点，右子树上所有节点的值大于根节点。中序遍历BST可以得到一个有序序列。
② 操作：查找、插入、删除。其管理效率与树的高度直接相关，平均复杂度为 O(log n)，最坏情况（退化成链表）为 O(n)。
4）自平衡二叉搜索树
① 核心：为了解决BST退化成链表的问题，在插入和删除时通过旋转执行保持树的平衡。
② AVL树：严格的平衡，任何节点的左右子树高度差不超过1。
③ 红黑树：一种近似平衡的BST，通过着色规则来保证效率，旋转次数比AVL树少，实践中（如 Map, Set 的实现）使用更多。
5）堆
① 核心：一种特殊的完全二叉树。所有父节点的值都大于等于（最大堆）或小于等于（最小堆）其子节点的值。
② JS实现通过：能够用数组模拟。
③ 应用场景：优先队列、堆排序。
4. 图
1）核心：由顶点（Vertex）和边（Edge）组成的非线性数据结构。
2）基本概念：
① 有向图 / 无向图
② 加权图 / 无权图
③ 环
3）表示方式：
① 邻接矩阵：二维数组，直观但可能浪费空间。
② 邻接表：为每个顶点维护一个列表，记录其相邻顶点，更节省空间。
4）图的遍历：
① 广度优先搜索：应用队列，按层次遍历。常用于寻找最短路径（无权图）。
② 深度优先搜索：运用栈（或递归），沿着路径深入到不能再深入为止。常用于拓扑排序、检测环、寻找连通分量。
二、 算法与算法思想
1. 排序算法
1）初级排序（易于理解但效率不高，O(n²)）：
① 冒泡排序：重复比较相邻元素。
② 选择排序：每次找最小（大）元素放到前面。
③ 插入排序：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置插入。
2）高级排序（效率高，O(n log n)）：
① 归并排序：分治法。将数组递归地分成两半，分别排序，然后合并。稳定排序。
② 快速排序：分治法。选择一个基准元素，将数组分成比基准小和大的两部分，递归排序。通常是最快的通用排序算法。
3）其他重要排序：
计数排序 / 桶排序：非比较排序，在特定条件下（数据范围有限）可达 O(n) 复杂度。
2. 搜索算法
1）顺序搜索：逐个遍历，O(n)。
2）二分搜索：针对已排序的数组，每次比较后都将搜索范围减半，O(log n)。是高效的查找算法。
3. 算法设计与思想
1）分治法：将一个大困难分解成若干个相似的小问题，递归解决小问题，再合并结果。例如：归并排序、快速排序。
2）动态规划：通过把原疑问分解为相对方便的子问题的方式，来求解复杂困难。它会保存子问题的解，避免重复计算。
① 核心特征：最优子结构、重叠子问题。
② 经典问题：斐波那契数列、背包问题、最长公共子序列。
3）贪心算法：在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的。
① 与动态规划对比：贪心不回溯，不保证全局最优，但通常高效。
② 经典问题：硬币找零（特定面额）、霍夫曼编码。
三、 核心概念与技巧
1. 复杂度分析（大O表示法）
1）这是全书的基石。用于描述算法的效率，包括时间复杂度（随数据规模增长，执行时间的增长趋势）和空间复杂度（随数据规模增长，占用存储空间的增长趋势）。
2）必须掌握常见复杂度：O(1), O(log n), O(n), O(n log n), O(n²), O(2^n) 等。
2. 递归
1）函数调用自身。是建立分治法和树/图遍历的自然方式。
2）核心：基线条件（递归终止条件）和递归条件。
3）缺点：可能存在栈溢出风险和重复计算问题。
3. JavaScript 特定技巧
1）使用 Array, Object, Map, Set 等内置对象来实现高级数据结构。
2）理解引用类型和值类型的区别，这在操作链表、树、图时至关重要。
学习路径建议
1）打好基础：先从数组、栈、队列开始，理解它们的基本操作和复杂度。
2）掌握核心：重点攻克链表、哈希表 和 二叉搜索树，它们是理解更复杂结构的基础。
3）深入树与图：学习各种树的结构和图的基本遍历方法（BFS/DFS）。
4）实践算法：在学习数据结构的同时，练习排序和搜索算法，并理解其背后的分治、动态规划等思想。
5）勤于动手：亲自用JavaScript实现这些数据结构和算法，并在 LeetCode 等平台上用它们解决问题，这是巩固知识的最佳途径。