简介面向 Java 学习者的数据结构和算法知识点总结 PDF 文档覆盖数组与简单排序、栈与队列、链表、递归、哈希表、高级排序、二叉树、红黑树、堆、带权图等核心主题。文档从一维/多维数组的基本用法讲起逐步深入到冒泡、选择、插入等排序的代码实现与效率分析同时阐明栈的 LIFO、队列的 FIFO、哈希查找、红黑树自平衡等关键机制。高级排序部分对归并、快速、堆排序的分治思想做了梳理带权图部分还涉及最短路径、最小生成树等典型算法思路适合正在系统学习 Java 核心编程或准备技术面试的开发者。资源为单个 PDF 文件压缩后仅 678KB内容精炼便于电脑端与移动端随时阅读。目前已有 583 人学习浏览可作为数据结构和算法复习、考前速查与知识梳理的实用参考。1. Java数据结构和算法PDF为什么你存了三年还是不会写不知道你有没有这种经历网盘里躺着一份《Java数据结构和算法.pdf》封面翻过七八次第一章数组与链表反复看了三遍但真到面试官让你手写一个LRU缓存时脑子里只剩下HashMap的put和get。这个场景太常见了。数据结构与算法对Java工程师来说不是选修课它是笔试手撕代码、LeetCode刷题、甚至排查线上HashMap死循环问题的地基。这份PDF能不能帮到你取决于你怎么读当小说读读三遍也白搭当源码对着写一遍就能上手。下面按我带新人时验证过的路子把这份资料拆成框架、算法、面试、排坑、验证五步讲清楚哪些是重点、哪些参数必须记、哪些坑绕不开。2. 先立框架Java视角下的数据结构选型与复杂度认知2.1 ArrayList与LinkedList之争复杂度没错用起来全是坑任何一本数据结构书的第一章都会告诉你数组支持随机访问平均复杂度O(1)链表插入删除快平均复杂度O(1)。这个结论没错但在Java里照搬就翻车。ArrayList底层是Object[]扩容时按oldCapacity (oldCapacity 1)计算新容量也就是1.5倍LinkedList是双向链表每个节点除了数据还要保存前后两个指针64位JVM下单个节点额外几十字节。这两个差异会直接反映在真实场景里。第一个坑是遍历。很多人拿到LinkedList习惯写for (int i 0; i list.size(); i) list.get(i)这是灾难get(i)是O(n)整体变成O(n²)。正确做法是用迭代器或增强for。第二个坑是头部插入到底值不值。LinkedList的addFirst确实是O(1)但如果你只需要在两端读写ArrayDeque循环数组实现通常更快因为它没有节点分配和指针维护的开销。判断依据很简单你的数据是按下标读多写少还是纯队列场景前者无脑ArrayList后者先试ArrayDeque。我的另一个经验是看数据规模。单机内存里几十万条数据的尾部追加ArrayList和LinkedList的差距几乎可以忽略真正拉开差距的是频繁的中间插入和随机访问。所以面试官问什么时候用LinkedList标准回答是头尾插入频繁、无随机访问需求但如果你补一句生产里我优先考虑ArrayDeque和ArrayListLinkedList很少用反而显得有实战判断。2.2 HashMap的hash扰动、树化与扩容三个必须背下来的数字哈希表章节在《数据结构与算法分析Java语言描述》这类PDF里讲的是散列、冲突、负载因子但落在Java面试题上考的就是HashMap里的几个关键参数默认容量16负载因子0.75树化阈值8退化阈值6最小树化容量64。这几个数字不能死背要能解释推导过程。负载因子0.75是时间与空间的折中太大比如2能省内存但冲突严重太小比如0.5浪费空间。树化阈值为什么是8因为负载因子0.75时哈希桶中链表长度服从泊松分布长度达到8的概率在千万分之几属于统计意义上几乎不会发生的极端情况。这里有个容易忽略的前提即使链表长度到了8HashMap也不会立刻转红黑树只有当桶的数量大于等于64时才走treeifyBin否则优先扩容。原因很简单桶太少时扩容一次就能把链表稀释没必要引入红黑树。这套流程在数据结构408的考研题里也常考。从put到扩容完整链路是先对key做hash扰动h ^ (h 16)再和(n - 1)做与运算定位桶桶为空直接放桶不为空且是链表就尾插存在同key则覆盖链表长度到8尝试树化size超过threshold就扩容。扩容时节点要么留在原位要么移动到oldIndex oldCap。如果你读PDF时能顺手在空白处画一张put流程图比抱着书反复背效率高得多。2.3 手写最小实现把栈、队列、链表反转各过一遍读数据结构文档最容易踩的坑是只看不写。我给自己定的底线是每看完一个结构先把PDF合上在白板上写出最小实现。写过才算懂尤其下面这两个高频基础题。单链表反转迭代法三指针是刷题平台出现频率最高的题目之一// 单链表反转pre、curr、next 三个指针依次后移 public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; // 先保存后继否则断链后找不回来 curr.next prev; // 当前节点掉头指向前驱 prev curr; // 前驱后移 curr next; // 当前节点后移 } return prev; }核心逻辑就一句话断链之前先保存next。我第一次写时忘了保存next循环走两轮链表就断了返回的一直是null。你只要记住这三行的固定顺序是保存、反转、移动就不容易出错。第二个是循环队列用数组实现核心是靠取模移动head和tailclass CircularQueue { private int[] data; private int head, tail, size; private int capacity; public CircularQueue(int k) { this.capacity k; this.data new int[k]; this.head 0; this.tail 0; this.size 0; } // 入队tail 指向下一个空位移动时对 capacity 取模 public boolean enQueue(int value) { if (isFull()) { return false; } data[tail] value; tail (tail 1) % capacity; // 关键回绕到数组头部 size; return true; } public boolean deQueue() { if (isEmpty()) { return false; } head (head 1) % capacity; size--; return true; } public boolean isFull() { return size capacity; } public boolean isEmpty() { return size 0; } }写循环队列最容易错的是用head tail判断空和满问题是空和满两个状态下head和tail都相等必须用size字段区分。这是个典型的边界陷阱。加上一个用数组实现的栈一个top指针加push/pop线性表、栈、队列的最小实现就齐了这正好对应PDF里前三章的核心内容。3. 算法篇排序、暴力枚举与KMP的Java实现套路3.1 排序别只背模板快排的partition与堆排的siftDown面试对排序的考察很少让你完整写冒泡但要能说清每个排序的复杂度、稳定性和适用场景。常见的坑是记得快排平均O(nlogn)但不知道最坏O(n²)发生在什么时候。最坏情况发生在每次partition都选到最大或最小元素比如近乎有序的数组配固定取最后一个元素做pivot。解法有两个方向随机选pivot或者三数取中。我建议直接掌握三路快排它在处理大量重复元素时能把退化风险压下去蓝桥杯、LeetCode和java面试题里都经常出现// 三路快排把数组分成 pivot、pivot、pivot 三段 private static void quickSort3(int[] a, int lo, int hi) { if (lo hi) { return; } int pivot a[lo]; int lt lo; // lt 指向小于区间的右边界 int i lo 1; int gt hi; // gt 指向大于区间的左边界 while (i gt) { if (a[i] pivot) { swap(a, lt, i); } else if (a[i] pivot) { swap(a, i, gt--); } else { i; } } // 相等区间 [lt, gt] 已就位递归处理左右两段 quickSort3(a, lo, lt - 1); quickSort3(a, gt 1, hi); }这段代码里lt和gt是两个边界指针小于pivot的元素换到左边大于pivot的换到右边相等的留在中间。普通快排把相等元素也丢进左右区间重复多时递归深度变大三路快排把相等段隔离均分效果更稳定对大量重复元素的实测收益非常明显。参数lo、hi是闭区间边界递归时传入子区间千万别写成lo和hi不变不然无限递归。堆排序的关键是向下调整siftDown而不是向上调整。建堆从最后一个非叶子节点(n / 2 - 1)开始依次siftDown排序阶段把堆顶和末尾交换堆大小减一再siftDown。笔试里完整堆排序容易写超时我一般先写siftDown再写堆顶弹出结构清晰不易错。另外记住三个高频结论堆排序不稳定归并排序稳定快排不稳定。这些散落在《数据结构与算法分析Java语言描述》相关章节里的结论往往是笔试选择题的送分点但很多人在代码上卡太久反而没时间检查答案。注意别把比较排序下界O(nlogn)等同于快排一定最实用。工程里Arrays.sort对基本类型用双轴快排对对象类型用TimSort前者不稳定、后者稳定两者都不是教材里的经典快排实现。3.2 暴力枚举不等于无脑循环剪枝是蓝桥杯真题的救命招暴力枚举是新手最容易忽略、比赛和笔试里最常用到保底的思路。它的适用场景是数据量小n小于20左右、状态空间可穷举比如全排列、组合选数、子集和。直接写三层循环是暴力枚举写DFS加剪枝也是暴力枚举区别在于后者在数据量翻倍时不至于全挂。一道经典的蓝桥杯数字类题目是从n个数里选k个使和最大。朴素写法枚举C(n,k)种组合剪枝写法用DFS// 从 n 个数里选 k 个使和最大候选不足时剪枝 public class CombinationMax { private int[] nums; private int n, k; private int maxSum Integer.MIN_VALUE; public int solve(int[] nums, int k) { this.nums nums; this.n nums.length; this.k k; dfs(0, 0, 0); return maxSum; } private void dfs(int start, int depth, int sum) { if (depth k) { // 选满了更新答案 maxSum Math.max(maxSum, sum); return; } // 剪枝核心剩余数字不够凑满 k 个直接结束这条分支 if (n - start k - depth) { return; } for (int i start; i n; i) { dfs(i 1, depth 1, sum nums[i]); } } }最重要的剪枝条件是if (n - start k - depth) return;含义是当前选了depth个还需要k - depth个而从start到末尾只剩n - start个候选候选数不够就必然无解。参数的意义也要说清楚start保证组合不重复depth记录已选个数sum维护中间和。这套模板可以无缝改到给定和找组合子集划分这类题目。暴力枚举不丢人别总想一步写出最优解。比赛和面试里先用暴力跑通、再用剪枝优化是性价比最高的路径。很多二分答案、状态压缩DP的题本质也是暴力枚举状态加剪枝去重所以3.2这一节值得多花时间吃透。3.3 KMP算法next数组推导与Java落地别再死背KMP是字符串匹配里必须会手撕的算法也是热搜词里kmp算法的核心。重点不在匹配逻辑而在next数组怎么算。先明确next[i]的含义在模式串pattern里以i结尾的子串中最长相等前缀后缀的长度减一有的教材不减一取决于写法我这里采用不含当前字符的标准版本。匹配时如果text[i] ! pattern[j]主串指针i不动j跳到next[j]这样text的指针永远不倒回整体复杂度是O(n m)。Java完整实现// 构建 next 数组next[j] 表示 pattern[0..j-1] 的最长相等前后缀长度 private static int[] buildNext(String p) { int m p.length(); int[] next new int[m]; next[0] -1; // 首个位置前面没有字符标记为 -1 int j 0; int k -1; while (j m - 1) { if (k -1 || p.charAt(j) p.charAt(k)) { j; k; next[j] k; } else { k next[k]; // 前后缀匹配失败回退 } } return next; } // KMP 匹配返回第一次出现的位置找不到返回 -1 public static int kmp(String text, String pattern) { if (pattern null || pattern.isEmpty()) { return 0; } int[] next buildNext(pattern); int i 0; int j 0; while (i text.length() j pattern.length()) { if (j -1 || text.charAt(i) pattern.charAt(j)) { i; // 主串指针只前进不回退 j; } else { j next[j]; // 模式串回退到最长相同前缀的末尾 } } return j pattern.length() ? i - j : -1; }容易错的地方有两个。一是buildNext里回退写k next[k]很多人记成k--那就退化成暴力扫描复杂度回到O(n*m)二是next[0]初始化为-1主串匹配循环里必须有j -1的分支否则数组越界。调试时最直接的方法是打印next数组和手推的前后缀表对照。KMP这套代码建议单独存成笔记期末复习前和面试前各默写一次每次写错的位置基本都一样多写两遍就稳了。4. 把PDF变成面试能力高频考点、刷题路线与手撕策略4.1 HashMap、二叉树遍历、字符串匹配Java开发工程师面试题的出题逻辑刷Java开发工程师面试题刷多了会发现算法部分的题目范围极其集中哈希表相关HashMap原理、LRU缓存、二叉树相关递归遍历、迭代遍历、最近公共祖先、字符串相关KMP、滑动窗口、回文串。出题人考的不是你会不会背API而是你能不能把业务问题映射到数据结构上。比如判断两个字符串是否互为变形词最简单的映射是用HashMap统计字符频次再遍历另一个时逐个递减减到负数就返回false。这题没法背它考验的就是看到字符串想到哈希表的映射能力。再比如二叉树层序遍历考点在队列根节点入队循环外记录当前层节点数size再弹出size个节点并把它们的左右孩子入队。这个模板比递归难写但面试几乎必考因为层序天然对应广度优先搜索思想。还有一类是基于现有数据结构做扩展典型是LRU缓存。标准解法是LinkedHashMap继承后重写removeEldestEntry构造参数accessOrder传true表示按访问序排序。面试官如果说不让用现成的就自己拼HashMap加双向链表get到节点移到链表头put新节点到头超出容量时移除链表尾。这套思路能讲清楚说明你对哈希表保证O(1)查找、链表保证顺序和O(1)删除的理解真正到位了。4.2 结合数据结构408与考研大纲一套不过时的自检清单考研数据结构408的覆盖面很完整线性表、栈、队列、树、图、查找、排序。如果你手里这份PDF是《数据结构与算法分析Java语言描述》类的内容章节正好对得上。我建议把PDF当基础教材先读一遍再拿408大纲当自检清单逐项打勾。好处是大纲是别人替你划好的重点比自己凭感觉挑章节靠谱。几个必须能合上书画出来的点二叉树前序中序后序的递归与非递归遍历非递归用栈模拟图的DFS和BFS模板要能写出来并知道邻接矩阵和邻接表两种存储下的复杂度差异查找里的二分查找注意mid low (high - low) / 2防溢出排序全家桶的复杂度和稳定性表。这里给你一张我常用的自检表知识点掌握标准检查方式二叉树遍历递归和非递归都能写能讲清前中后序差异关书白板手写图的DFS/BFS会用邻接表写模板能说出两个复杂度默写一遍二分查找会写防溢出的mid写法能处理边界手写并跑测试排序全家桶复杂度、稳定性表能默背口述对照先填目前等级定位差距按树→图→查找→排序的顺序补而不是重新从头翻书。数据结构是螺旋上升的学科你刷题遇到最近公共祖先时再回头翻树的章节比从零照PDF把树看完再去刷题效率高得多。4.3 手撕代码的时间控制先定边界再写主体面试手撕算法题时时间分配比写对更重要。常见做法是先花一分钟确认三件事输入是什么类型数组、链表、字符串、是否为null或空、是否有重复值和溢出风险。这三个不确定因素是一半以上现场翻车的起点。我习惯先写方法签名和边界处理再写主体逻辑。以数组反转某个区间为例很多人上来就写swap忽略start end或start 0的非法输入先写边界再写核心出错概率低一大截。还有一个细节循环里如果反复出现list.size()这样的表达式用局部变量缓存既清晰又避免LinkedList的get(i)陷阱。时间上建议给自己限10到15分钟。如果前5分钟思路都不成形立刻换一个更暴力的方案打底先跑通再优化。面试官更看重你能否在约束下简化问题并闭环而不是交一个完美但超时的解法。这个习惯要从平时刷题就练起来否则到了现场面试官问这题和上一题什么区别时你还在纠结第一题的条件判断。5. 避坑指南照着PDF自学Java数据结构最容易翻车的5个瞬间自学数据结构的翻车现场我带过的工程师基本都经历过。下面5个瞬间是从实际踩坑里总结的每条按现象、原因、解决三段写方便你对号入座。5.1 现象书看懂了合上就写不出来这是自学数据结构的头号玄学问题文字能看懂代码能理解做课后题时大脑空白。原因是读书时眼睛跟着代码走只记住了它做了什么没建立为什么这么写的因果链。解决的办法是主动回忆每读完一小节先把PDF合上在白板上画出这个结构的主要字段和方法签名再自己补实现。补不出来就回看那一页然后第二天再默写一次。连续两天重复这个结构基本就是你的了。千万别在书上画满荧光笔就觉得自己会了那是假性掌握。5.2 现象递归看得很爽一跑大数据量就栈溢出递归代码短、可读性好但Java递归深度受线程栈大小限制默认栈容量通常在1MB上下递归层数过多必然StackOverflowError。二叉树如果退化成链表递归深度等于节点数几万节点的树直接崩。原因有两个一是递归写法没考虑最坏深度二是没养成递归转迭代的思维习惯。解决方法是遇到深度不确定的遍历优先用迭代二叉树前序迭代就是while循环加一个Stack先压右孩子再压左孩子代码稍长但稳定性和性能都好。真要在生产代码里写递归先估算最坏深度不要赌测试数据温和。5.3 现象HashMap参数背得滚瓜烂熟换个问法就发懵HashMap初始容量是几能答16但面试官追问负载因子改成0.1会怎样就卡住。这是死背参数、不理解权衡的典型。负载因子影响的是扩容阈值threshold capacity * loadFactor。改成0.1意味着容量到阈值距离缩短扩容更频繁内存浪费严重但冲突少、读写更稳改成2则反之。理解了这条公式这类变形题怎么问都不怕。看源码时顺手把threshold、size、capacity三个变量的联动关系画出来比盯着数字背效率高十倍。5.4 现象LeetCode用Java提交算法逻辑对但超时复杂度是O(n)却超时多半是Java语言层面的开销在拖后腿自动装箱、String拼接、集合反复扩容。比如统计小写字母频次用HashMapCharacter, Integer是方便但每个字符都要装箱换成int[26]就快一个数量级。循环里字符串拼接用会不断创建新对象必须用StringBuilder。ArrayList如果大概知道容量构造时直接传initialCapacity避免中间多次搬移。这些不是《Java数据结构和算法.pdf》里的内容但却是Java基础里必须掌握的配套能力刷题前最好过一遍。5.5 现象调用Arrays.sort却不知道底层用的什么排序很多人笔试里写Arrays.sort(a)就说是快速排序其实是个坑。Java的Arrays.sort对基本类型数组用的是双轴快排对对象数组用的是TimSort一种稳定的归并结合插入排序。这直接影响稳定性这道送分题的回答。解决方法是看一次JDK源码里DualPivotQuicksort和TimSort的注释记住结论对象数组默认稳定基本类型数组不稳定。另一个连带坑是Comparator实现不满足自反、对称、传递的契约时会抛IllegalArgumentException报Comparison method violates its general contract这在排序自定义对象时特别容易遇到排查时先检查compare方法有没有在相等时返回0。6. 进阶验证用三道LeetCode题检验这本PDF有没有白看验证标准不是我看完了而是三道题不看答案20分钟内能不能写出来。第一道是反转链表对应的是线性表章节的指针操作第二道是数组中第K个最大元素对应堆排序或快排partition章节这题写不出来的话排序只能算背过不算掌握第三道是LRU缓存对应HashMap加链表两章的组合应用能做出来才说明你读懂了哈希表保证O(1)查找、链表保证顺序这句话。三道题从单结构到组合结构刚好把PDF里最核心的线性表、排序、哈希串起来。写完别急着看题解先对照PDF相关章节自己改一遍反转链表有没有漏掉空链表第K大用的是大根堆还是小根堆K从1开始还是从0开始LRU的removeEldestEntry判断条件是size() capacity还是等于。这些细节比多刷十道题更能暴露理解漏洞。改完再跑几个边界用例链表为null、K等于数组长度、缓存容量为1这三个用例能拦住80%的粗心错误。多年前我带项目的时候自己也经历过一次现场翻车总以为树和图理解了就行结果面试让手写中序迭代遍历从栈模拟开始推推了三分钟没推顺最后用递归交了差。回来之后我给自己立了个规矩——PDF每章的最小实现全部过手不看答案敲一遍敲不出来隔天再敲敲到顺手为止。从那以后笔试手撕再没犯过怵。这条路子在我带过的几个人身上都验证过希望今天这套五步加三题的方法也能帮到你。本文还有配套的精品资源点击获取