数据结构知识点整理

数组和链表，数据是结构所有数据结构的起点。数组在内存里是知识一块连续的区域，像一排门牌号固定的点整房子，访问第i个元素，数据直接算地址就能找到，结构时间复杂度O(1)。知识可一旦要插入或删除，点整就得挪动后面所有元素，数据代价惨重。结构链表则相反，知识每个节点带着数据和指向下一个节点的点整指针，像一串散落的数据珠子，用线串起来。结构插入删除只需改指针，知识O(1)搞定，但想找第i个节点，只能从头遍历，O(n)。

栈和队列，其实就是两个被限制了操作位置的线性表。栈是后进先出，像一摞盘子，你只能从顶上拿或放。函数调用、括号匹配、撤销操作，全是它在背后撑着。队列是先进先出，像食堂打饭的队伍，先来先服务。消息队列、打印机任务调度，都是它的地盘。有意思的是，用两个栈能实现一个队列，用两个队列也能实现一个栈，这种互转的思维，面试里经常拿来考人。

树，最让人头疼也最让人上瘾。二叉树是基础，但真正难的是平衡——AVL树每次插入删除都要检查左右子树高度差，超过1就旋转，四种旋转情况（LL、RR、LR、RL）能记到怀疑人生。红黑树更狠，用颜色标记节点，牺牲一点平衡性换更少的旋转次数，Java的TreeMap、C++的std::map底层都是它。但说实话，日常写业务代码，你根本不会手写红黑树，能讲清楚它的调整过程就够了。倒是堆，这个完全二叉树的数组表示，优先队列的默认实现，top-k问题用它最顺手，建堆O(n)，每次取堆顶O(log n)。

图，把关系抽象成顶点和边。邻接矩阵直观但费内存，邻接表省空间但查边慢。遍历就两种：深度优先（DFS）像走迷宫，一条路走到黑再回头；广度优先（BFS）像水波扩散，一层层往外扫。最短路径里，Dijkstra处理非负权值，贪心思想，每次选距离最近的未访问节点；Bellman-Ford能处理负权，但慢；SPFA是队列优化的Bellman-Ford，比赛里常用，可遇到构造数据会退化。最小生成树，Prim从点出发，Kruskal按边排序，后者实现更简单，并查集一配上，代码短得让人感动。

哈希表，用空间换时间的极致。散列函数把键映射到数组下标，冲突了怎么办？链地址法拉个链表，开放地址法找下一个空位。Java 8以后的HashMap，当链表长度超过8就转红黑树，就是为了防恶意哈希碰撞。但哈希表有个致命弱点——无序，想按顺序遍历就废了。这时候就得靠跳表，给有序链表加多层索引，查找O(log n)，Redis的有序集合就是用它实现的。

排序算法是绕不开的基本功。快排平均O(n log n)，但最坏退化O(n²)，所以实际工程里用改进版（比如三数取中）。归并稳定但需要额外空间，外部排序就靠它。堆排序原地排，但不稳定。计数排序、基数排序、桶排序，都是利用数据特性，把复杂度压到O(n)，可限制条件多，不是所有场景都能用。我见过不少人背了十个排序算法，真到写代码时连快排的partition都写不利索——知道原理是一回事，手写出来是另一回事。

最后说一句，数据结构不是背定义。你写一个LRU缓存淘汰算法，得把哈希表和双向链表结合起来，每个节点既在哈希表里又在链表里，删除时O(1)找到节点，O(1)调整链表顺序。这种交叉应用的场景，才是真正考验你理解深度的地方。