算法与数据结构思维链

1. 数组 vs 链表:为什么有两种

起点为什么有的数据要连续存(数组),有的要分散存(链表)?

本质:数组连续存储 → 查找快(下标直接算地址)但插入删除慢(要移动后面所有元素);链表分散存储+指针串联 → 插入删除快(改指针)但查找慢(从头遍历)。各有优劣,因为解决不同需求。

🌊 顺藤摸瓜

① 数组

连续内存 → 下标查找 O(1)(地址=起始+下标×大小)→ 但插入/删除要移动后面所有 O(n)→ 读多写少用数组

连续存储查找 O(1)插入 O(n)

② 链表

分散存储+指针 → 插入/删除 O(1)(改指针就行)→ 但查找 O(n)(从头遍历)→ 频繁增删用链表

分散+指针插入 O(1)查找 O(n)

③ 衍生

数组+扩容 → ArrayList(动态数组,扩容拷贝);链表+双向 → LinkedList;数组分块+指针 → 跳表(链表上加速查找)

ArrayListLinkedList跳表

选型:读多写少用数组(查找快),频繁增删用链表(插入快)。Java ArrayList 查找多用数组,LinkedList 频繁增删用链表。

2. HashMap:为什么 O(1) 还要红黑树

起点HashMap 查找明明 O(1),为什么还要引入红黑树?

本质:HashMap 用哈希函数把 key 映射到数组下标,查找 O(1)。但哈希冲突(不同 key 算出同一下标)时,冲突的元素挂成链表,链表太长查找退化成 O(n)。红黑树是把长链表(O(n))变成平衡树(O(logn)),防退化。

🌊 顺藤摸瓜

① 哈希冲突

hash(key) % 数组长度 → 不同 key 可能算出同一下标 → 冲突 → 链地址法(挂链表)/ 开放地址法(找下一个空位)

哈希冲突链地址法开放地址法

② 链表退化

冲突多了链表变长 → 查找退化成 O(n) → JDK8 开始,链表超过 8 → 转红黑树(O(logn))→ 防恶意构造 key 攻击

链表退化 O(n)红黑树 O(logn)阈值 8

③ 扩容

元素多了负载因子 > 0.75 → 扩容(数组翻倍)+ rehash → 让元素分散,减少冲突 → 扩容代价大(全拷贝),所以要预估容量

负载因子 0.75扩容翻倍rehash

3. 为什么有这么多树

起点二叉树、BST、红黑树、B+树,为什么演化出这么多?

本质:树的演化都是为了"保持平衡,防止退化"。普通二叉树可能退化成链表(最差 O(n)),所以有了自平衡机制(红黑树/AVL),为了磁盘 IO 又有了 B+树(矮胖)。

🌊 顺藤摸瓜(树为什么越来越复杂)

① 二叉树

每个节点最多两个子 → 但插入顺序不同可能退化成链表(全左/全右)→ 最差 O(n)

② BST 二叉搜索树

左小右大 → 查找 O(logn) → 但依然可能退化(插入有序数据)→ 需要自平衡

③ 红黑树/AVL

自平衡:插入/删除时旋转保持左右大致平衡 → 保证 O(logn) → 红黑树(弱平衡,插入快,Java 用)/ AVL(强平衡,查找快)

自平衡红黑树(Java)AVL

④ B+树

二叉树数据多时树高(IO 多)→ B+树多路(矮胖)非叶子只存索引,叶子存数据+链表 → 3-4 层存千万级 → MySQL 用

多路矮胖叶子链表MySQL 索引

一句话:树的演化 = "防止退化成链表"。内存用红黑树(矮),磁盘用 B+树(矮胖+叶子链表)。

4. 排序:为什么有这么多算法

起点快排、归并、堆排,为什么不能用一个?

本质:没有"最好"的排序,只有"适合场景"的。时间复杂度、空间复杂度、稳定性、数据特征(基本有序/大数据/内存限制)决定了选哪个。

算法	平均	最差	空间	稳定	适合
快排	O(nlogn)	O(n²)	O(logn)	❌	内存排序(实际最快)
归并	O(nlogn)	O(nlogn)	O(n)	✅	大数据/外部排序/要稳定
堆排	O(nlogn)	O(nlogn)	O(1)	❌	空间受限/Top K
桶排	O(n)	O(n²)	O(n)	✅	范围已知且均匀

选型:内存排序用快排(实际最快),要稳定用归并,空间受限用堆排,大数据外部排序用归并(分块+合并)。

5. 算法思想:什么时候用什么

本质:算法题的本质是"找规律 + 优化"。先想暴力解(能做就行)→ 再优化(时间/空间)→ 最后看有没有套路可套。

🌊 顺藤摸瓜(看到题先想什么)

① 暴力

先想最笨的办法(双重循环、全枚举)→ 能做对就行 → 再看时间能不能优化

② 双指针

看到有序数组找两数/区间 → 双指针(头尾向中间)→ O(n) 代替 O(n²)

③ 哈希

看到找重复/计数/映射 → 哈希表 → 用空间换时间(O(n) 代替嵌套循环)

④ DP

看到最值 + 子问题重复 → 动态规划 → 状态转移方程 → 记忆化避免重复算

⑤ 滑动窗口

看到连续子数组/子串 → 滑动窗口(左右指针维护区间)→ O(n) 遍历一次

⑥ 回溯

看到所有组合/排列/ subsets → 回溯(DFS + 撤销选择)→ 树形遍历所有可能

心法:看到题先想暴力解 → 再识别特征(有序?重复?子问题?)→ 套对应套路。不要上来就想最优解。

总结

看到问题	本质	第一反应
查快还是插快	数组查快插慢,链表插快查慢	读多用数组,写多用链表
HashMap 为什么 O(1)	哈希映射到下标	冲突挂链表,长了转红黑树防退化
树为什么这么多	都是防退化成链表	内存红黑树,磁盘 B+树
排序用哪个	没有最好只有适合	快排(内存)/归并(稳定+外排)/堆排(省空间)
算法题怎么想	暴力→优化→套套路	先暴力再优化,识别特征套模板