简介《Java数据结构和算法.pdf》是一份面向Java开发者与算法初学者的知识点总结文档聚焦面试笔试和课程复习常见内容。文档从一维/多维数组的创建、初始化与边界检查讲起逐一介绍冒泡、选择、插入等简单排序并覆盖栈LIFO、队列FIFO、链表、递归、哈希表等基础结构后半部分深入快速排序、归并排序、堆排序等高级排序系统讲解二叉树、红黑树、堆和带权图包含最短路径与最小生成树算法思路核心概念均配有Java代码示例或效率分析。资源为单个PDF文件大小仅678KB轻量便携适合随时查阅复习。目前已有583人浏览学习对于希望快速建立Java数据结构和算法知识框架的读者来说是一份实用且简洁的参考资料。1. Java数据结构和算法别急着翻PDF先想清楚要解决什么问题很多同学的硬盘里都躺着一份“Java数据结构和算法.pdf”下载完就再没打开过。我以前也一样直到被一次面试问到“ArrayList扩容为什么是1.5倍”才意识到这份资料不是拿来“读”的而是拿来“查”和“练”的。它真正要解决的是三件事一是帮你把数组、链表、树、图这些数据结构在Java里落地二是把排序和字符串匹配这些算法写出可运行的代码三是让你在java面试题和蓝桥杯这类场景里能快速定位用哪个数据结构。适合刚学完Java语法、准备找开发岗或打比赛的人如果你已经能熟练手写快排那这份资料对你就是字典。2. 从数组到跳表把PDF里的概念变成可运行的Java类2.1 为什么选择“数组→链表→跳表”这条主线PDF里通常把数据结构分成线性表、树、图、散列几大块目录很长新手很容易从线性表开始就耗尽热情。我一般会换一条主线先看数据在内存里怎么放。数组是连续的一片内存读按下标O(1)但插入中间要搬移链表用指针把不连续的节点串起来插入O(1)但查找要遍历跳表则是在链表上叠加多层索引把查找从O(n)压到O(log n)。这条主线的好处是每个结构的出现都是为了解决前一个结构的痛点而不是一堆孤立的定义。这条主线也和Java类库对得上。ArrayList是动态数组LinkedList是双向链表ConcurrentSkipListMap底层就是跳表。java面试题里经常会问“什么时候用ArrayList什么时候用LinkedList”如果只背结论很容易说出“链表插入快”这种不完整的答案。真正的答案是插入发生在尾部且不需要扩容时ArrayList更快只有在已知位置频繁插入删除LinkedList才有优势。至于数据结构408统考它考二叉树更多但工作面试更偏爱这些“看起来简单、问起来有深度”的线性结构。所以我现在读PDF会跳过开篇的历史介绍直接从数组开始敲代码。2.2 一个能跑的最小动态数组类容量、扩容与边界检查“ArrayList是动态数组”在PDF里只值一行但你要是亲手实现一遍立刻会撞上“容量和大小”这对概念。下面是一个最小实现public class SimpleArrayList { private int[] data; private int size; public SimpleArrayList() { data new int[10]; size 0; } public void add(int value) { if (size data.length) { grow(); } data[size] value; } private void grow() { int newCapacity data.length (data.length 1); int[] newData new int[newCapacity]; System.arraycopy(data, 0, newData, 0, size); data newData; } public int get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index index , size size); } return data[index]; } public int size() { return size; } }这段代码的逻辑很直白size记录已放入的元素个数data.length是物理容量。add的时候先看size是否撞到容量上限满了就扩容。扩容倍数我写成data.length (data.length 1)也就是1.5倍和JDK的ArrayList保持一致。注意System.arraycopy只复制size个元素而不是整个data因为后面那些空位还没有意义。get方法必须先做边界检查这是很多PDF不会写但工程里必须有的细节。参数选择上有两点值得说。初始容量为什么是10这只是JDK默认值你完全可以根据业务改成64或1024太小会导致频繁扩容太大则浪费内存。扩容倍数为什么是1.5而不是2这是内存分配和拷贝代价的折中倍数太小扩容太频繁倍数太大单次拷贝浪费。1.5倍还有一个好处连续扩容的总拷贝次数是O(n)所以平均下来add是O(1)。如果面试官追问这就是摊还分析的鲜活例子。2.3 跳表的关键参数层数、概率因子与查找路径跳表在大部分PDF里只是几行概念但它是理解“以空间换时间”的绝佳样本。先看节点定义和查找import java.util.Random; class SkipListNode { int value; SkipListNode[] next; SkipListNode(int value, int level) { this.value value; this.next new SkipListNode[level]; } } public class SimpleSkipList { private static final int MAX_LEVEL 16; private static final double P 0.5; private final int level 1; private final SkipListNode head new SkipListNode(Integer.MIN_VALUE, MAX_LEVEL); private final Random random new Random(); public boolean search(int target) { SkipListNode cur head; for (int i level - 1; i 0; i--) { while (cur.next[i] ! null cur.next[i].value target) { cur cur.next[i]; } } cur cur.next[0]; return cur ! null cur.value target; } private int randomLevel() { int lvl 1; while (random.nextDouble() P lvl MAX_LEVEL) { lvl; } return lvl; } }这段代码的关键在于next[i]表示当前节点在第i层的后继。查找从最高层开始每层都向右找“最后一个小于target的节点”并停在那儿然后降到下一层继续。最后一层是完整链表所以一定会停在target的前一个位置再走一步就能判断是否存在。randomLevel模拟掷硬币P0.5表示每个节点有50%概率多一层。MAX_LEVEL16对绝大多数数据集足够跳表的高度期望约为log n。这里有两个参数直接影响性能P和MAX_LEVEL。P越大节点层数越高索引越密查找越快但每个节点的next数组越长内存越大。P0.5是经典取值内存约为节点的2倍。MAX_LEVEL设大了不会让查找更快只会让头节点的数组白白占空间设小了数据量大时顶层不够用。如果做生产实现还要在插入时维护每层的前驱节点这里不展开。JDK的ConcurrentSkipListMap就用了跳表这也是为什么面试里偶尔会考它的查找路径从最高层向右、向下最后落到第0层。2.4 从理论到代码的映射大O记号到底怎么用PDF里会给你一张复杂度表但很多人不会把它对应到代码。我自己的习惯是写完一个实现后在关键循环里放一个计数器用数据规模翻倍来感受增长率。比如动态数组连续add一亿次如果计数器只统计System.arraycopy复制的元素个数会发现总复制量大约是n的常数倍所以平均O(1)。跳表查找一个元素走的总层数大约是log n级所以O(log n)。如果你只是背表遇到“HashMap为什么是O(1)”就会答得泛但你能画出put的散列、碰撞、扩容链路才算真正会了。注意复杂度讨论的是增长率不是单次运行的毫秒数。你在一台机器上测出来的时间同时受JIT、GC和缓存影响别用它直接给两个数据结构下结论。复杂度不是用来算毫秒的而是用来做选型的。数据量小到几百顺序查找和跳表没有肉眼区别数据量到百万级O(n)和O(log n)的差距就出来。java面试题里经常给一个场景让你选数据结构我一般先问三个问题读多还是写多有没有序需不需要稳定迭代答案往往不是最优复杂度而是最符合场景的组合。比如一个读多写少的排行榜用数组加排序就够了没必要上跳表。3. 排序与字符串匹配KMP和暴力枚举的代码级对比3.1 排序先选型冒泡、快排、堆排各自的适用边界PDF里的排序章节一般从冒泡讲起但你在java面试题里手写排序最可能被要求的是快速排序。原因很简单Arrays.sort对基本类型用的是双轴快排对对象用的是TimSort你写一个标准快排就是在解释Arrays.sort的一部分行为。public static void quickSort(int[] arr, int left, int right) { if (left right) { return; } int pivot arr[left (right - left) / 2]; int i left; int j right; while (i j) { while (arr[i] pivot) { i; } while (arr[j] pivot) { j--; } if (i j) { int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; i; j--; } } quickSort(arr, left, j); quickSort(arr, i, right); }这段代码用的是双指针分区pivot取中间值避免对已经有序的数组退化。i和j从两端向中间走i找比pivot大的j找比pivot小的找到就交换。循环结束后数组被分成两段左边都不大于pivot右边都不小于pivot然后递归排序左右两段。参数left和right是闭区间调用时传0和arr.length-1。注意取中间值的写法是left (right - left) / 2直接写(left right) / 2在极端情况下可能溢出。那冒泡和堆排呢冒泡排序在元素接近有序时可以用但最坏O(n^2)只适合教学或复杂度题。堆排的最坏复杂度也是O(n log n)但它不稳定而且常数比快排大主要用在优先队列场景。所以工程上默认选快排如果你要稳定的排序选归并或TimSort。面试时如果被问到“为什么快排比堆排快”答案不是复杂度而是快排的局部性好缓存命中率高堆排的访问模式是跳跃的。这一点PDF里讲得不多但能体现你真在操作系统层面想过。3.2 KMP的核心next数组与匹配回退字符串匹配是暴力枚举最容易“看着会写一测就挂”的地方。暴力枚举的做法是主串从i开始模式串从0开始逐个比不匹配就i重来。最坏情况下主串“AAAAAB”找“AAAB”每次都要比到模式串末尾才失败复杂度O(n*m)。KMP算法的核心是让主串指针不回退失败时模式串回退到“已经匹配部分的前缀”这一步靠next数组完成。public static int[] buildNext(String pattern) { int m pattern.length(); int[] next new int[m]; next[0] 0; int j 0; for (int i 1; i m; i) { while (j 0 pattern.charAt(i) ! pattern.charAt(j)) { j next[j - 1]; } if (pattern.charAt(i) pattern.charAt(j)) { j; } next[i] j; } return next; } public static int kmpSearch(String text, String pattern) { int n text.length(); int m pattern.length(); if (m 0) { return 0; } int[] next buildNext(pattern); int j 0; for (int i 0; i n; i) { while (j 0 text.charAt(i) ! pattern.charAt(j)) { j next[j - 1]; } if (text.charAt(i) pattern.charAt(j)) { j; } if (j m) { return i - m 1; } } return -1; }buildNext里j表示“当前已经匹配的前缀长度”next[i]记录的是模式串前i1个字符的最长相等前后缀长度。比如模式串“ABABAC”next[3]2表示前缀“ABAB”的最长相等前后缀是“AB”。匹配时一旦text.charAt(i)不等于pattern.charAt(j)主串i不后退j直接回退到next[j-1]因为前面那部分已经确认匹配。这个回退就是所有KMP讲解里的“利用已匹配信息”。需要注意next数组有多个版本。有些教材让next整体减1有的用-1开头面试时先和面试官对齐定义不然两个人写的名字一样、含义不同容易翻车。我的习惯是用0版本简洁且不容易下标越界。KMP的复杂度是O(nm)空间O(m)。如果你只是想找一个子串Java里直接text.indexOf(pattern)就行但面试考KMP考的是你理解不理解“回退”的动机以及能不能处理边界。建议写完后用“ABABAC”和“ABABABABC”这种模式串手动跑一遍。3.3 暴力枚举与剪枝蓝桥杯和算法题里的应用很多人以为暴力枚举就是无脑for循环其实剪枝算法才是它真正的价值。蓝桥杯的填空题数据范围通常不大直接枚举所有可能反而比设计复杂算法更快。下面这个例子是“从数组里选若干个数使它们的和等于target求方案数”import java.util.Arrays; public class SubsetSum { public static int countSubsets(int[] nums, int target) { Arrays.sort(nums); return dfs(nums, 0, target); } private static int dfs(int[] nums, int index, int remain) { if (remain 0) { return 1; } if (index nums.length || nums[index] remain) { return 0; } int count 0; for (int i index; i nums.length; i) { if (nums[i] remain) { break; } count dfs(nums, i 1, remain - nums[i]); } return count; } }这里的暴力枚举体现在递归里每个位置都可以选或不选本质是枚举所有子集时间复杂度O(2^n)。剪枝有两处第一处nums[index] remain时直接返回0因为数组已排序当前位置已经超过剩余目标后面更大没必要看第二处循环里nums[i] remain直接break也是同样的道理。这两步不会改变结果但能砍掉大量无效分支。这个写法隐藏着一个坑数组里有重复数字时会数出重复方案。解决方法是排序后在for循环里跳过i index nums[i] nums[i-1]。我建议你亲手补上这句因为蓝桥杯和力扣的“组合总和”类题目都要处理去重。暴力枚举不是笨办法加上剪枝之后n20时非常好用如果n40就要换成动态规划或双向搜索不要迷信剪枝能拯救指数级复杂度。3.4 三种算法的复杂度边界对比表算法平均时间复杂度空间复杂度典型场景快速排序O(n log n)O(log n) 栈空间基本类型数组排序、topK问题的分区KMPO(nm)O(m)在主串中查找模式串要求主串不回溯暴力枚举剪枝最坏 O(2^n)O(n) 递归栈数据规模 ≤20 的搜索题、蓝桥杯填空这张表值得贴在书签里。注意快排的空间复杂度不是O(1)它需要递归栈平均O(log n)最坏O(n)。KMP的O(m)空间主要花在next数组上。暴力枚举最坏是指数级剪枝只是在平均条件下让常数变小真正的复杂度没有变化。面试答错“快排空间复杂度”的人非常多因为这不在大多数PDF的第一页表格里。4. 避坑数组扩容、泛型擦除与递归栈溢出的5个典型问题4.1 扩容后元素全丢size和capacity分不清现象照着PDF写一个动态数组add到第11个元素时抛IndexOutOfBoundsException或者扩容后get到的都是0。原因把size和capacity当成一回事。size是“已经放进去的元素的个数”capacity是“底层数组能放多少个”。解决add时先判断size data.length扩容时用新数组接收原数组前size个元素再把data指向新数组。很多人漏了data newData这一步导致扩容函数执行完原数组还是原来的长度也有人复制时复制整个data把未使用的空位也复制了这在基本类型数组上不会报错但在对象数组上会初始化一堆null浪费操作。我给的建议是把size和capacity分别打印出来每次add后看一眼。4.2 new T[] 直接编译失败泛型数组是黑匣子现象在泛型类里写T[] arr new T[16];编译器直接红波浪线。原因Java泛型采用类型擦除JVM在运行时不知道T具体是什么类型而数组是协变的运行时必须知道组件类型两者天然冲突。解决最常见做法是内部使用Object[]取元素时做强转。就像这样private Object[] elements new Object[16]; SuppressWarnings(unchecked) public T get(int index) { return (T) elements[index]; }为什么不用(T[]) new Object[16]也可以但转型时会有Unchecked警告而且运行时仍然是Object[]一旦你把它当具体类型数组传给别的方法可能会在调用处抛出ArrayStoreException。相比之下内部存Object[]、外部强转更干净。这个坑在《Java数据结构和算法.pdf》里经常被忽略但你想实现一个通用的ArrayList、HashMap就绕不开。另一个备选方案是给构造函数传入ClassT用java.lang.reflect.Array.newInstance(clazz, size)创建真正的T数组代价是反射开销和代码变长。4.3 递归写斐波那契n50 直接卡死或栈溢出现象用fib(n) fib(n-1) fib(n-2)写递归n50时程序半天不出结果甚至StackOverflowError。原因没有记忆化同一子问题被反复计算调用次数是O(2^n)。Java的递归栈默认深度也就几千层虽然fib(50)的深度其实只有50不会栈溢出但因为计算量指数级实际会长时间无响应如果改成深度更大的递归比如错误比率的二分才会栈溢出。解决加一个memo数组long[] memo new long[n 1]; Arrays.fill(memo, -1); public long fib(int n) { if (n 1) return n; if (memo[n] ! -1) return memo[n]; memo[n] fib(n - 1) fib(n - 2); return memo[n]; }这个做法的本质是把递归树剪成一条链每个子问题只算一次复杂度降到O(n)。更工程的做法是改迭代用两个变量滚动计算省下栈空间。这个坑想表达的不是“别用递归”而是“递归算法要先想清楚有没有重叠子问题”。如果面试题里让你求第100项斐波那契你直接说用迭代或矩阵快速幂会比递归加缓存显得更系统。4.4 比较器没写对sort结果和预期相反现象用Arrays.sort(arr, (a, b) - a - b)想升序结果在某些大数场景下顺序很奇怪或者用(a, b) - b - a排序发现结果还是升序。原因比较器约定是返回值小于0表示a排在b前面很多人刚好记反写成a - b其实是a小于b时返回负数升序正确但a - b会有整数溢出风险比如Integer.MAX_VALUE - (-1)直接变成负数。解决Arrays.sort(arrays, (a, b) - Integer.compare(a, b)); // 升序 Arrays.sort(arrays, (a, b) - Integer.compare(b, a)); // 降序用Integer.compare替代减法用Long.compare处理long。另一个坑是int[]基本类型数组不能直接用带比较器的Arrays.sort必须用Integer[]。很多PDF里的示例代码用的是int[]配比较器实际编译就会报错因为基本类型数组没有对象的compareTo。如果你在蓝桥杯里赶时间建议先把数组转成List或者直接用Stream排序但工程里还是显式比较器最可靠。4.5 看PDF全会关掉PDF全废现象对着书上的代码觉得自己理解了但一到面试现场手写连ArrayList扩容都写不全。原因识别和重建是两回事。看书时你的大脑在做模式匹配而写代码需要提取、组织、验证这条通路如果不刻意训练就是一路生疏。解决每学完一个数据结构做“三件套”关掉PDF在IDE里从空文件写最小实现写三五个边界测试至少包含空结构、单元素、满容量然后试着向不熟悉的人说明为什么这样设计。这三步做完一个知识点才真正落到你的技能树上。我见过很多同学收藏了十几份PDF却输给了只把ArrayList手写三遍的人原因不是智力而是输出次数。5. 拿“Java数据结构和算法”这份资料做面试复盘一个可复用的刻意练习清单总说PDF看不完不如把它当字典和练习册。我的习惯是把每一章的复杂度、核心代码、边界条件压缩成一张A4速查表每个数据结构占一行左边画结构示意中间写增删改查复杂度右边写Java类名和最小方法签名。面试前一天只看这张表遇到具体题再翻PDF对应章节。验证自己是否真的掌握给自己出三道题。第一道需要频繁在中间插入和删除选ArrayList还是LinkedList为什么不是“链表插入快”就完事第二道给一个字符串数组统计词频手写HashMap的put思路包括hash扰动、冲突转树、扩容的触发条件。第三道手写KMP的next数组并手动跑一遍模式串“ABABAC”。进阶技巧有两个很值钱。一是把PDF里的伪代码改成Java时优先用基本类型数组而不是包装类集合避免装箱和拆箱的隐藏成本能用迭代解决的问题就不用递归因为你不知道面试机器的默认栈有多大。二是每写完一个结构立刻写一个带断言的main方法构造空、单元素、满容量三类用例。这个习惯能让你在蓝桥杯这种“提交即判定”的环境里少很多遗憾。我自己当年就是只看书不重建结果面试官问ArrayList默认容量时我只记得“大约10”说不清到底什么时候扩容。后来改成每次只啃一章、写一个最小实现、跑三个边界用例才慢慢把资料变成自己的东西。这份《Java数据结构和算法.pdf》本身不会让你变强变强的是你把它合上之后在编辑器里敲出来的那几段代码。希望帮到你。本文还有配套的精品资源点击获取