数据结构 五承接上文数组与ArrayList的底层实现本文系统讲解线性表的另一核心结构——链表。链表通过指针连接分散的内存节点彻底解决了数组插入删除需要移动大量数据的问题是算法面试的高频考察点。本文将从底层原理、完整代码实现、经典面试题三个维度逐层拆解单向链表的增删改查与快慢指针核心算法覆盖从入门到面试的全量知识点。一、链表基础概念1. 链表的本质与核心特点数组是连续内存存储的线性结构优势是随机访问快但插入删除需要移动大量数据效率低而链表是离散内存存储的线性结构节点在内存中零散分布靠指针域连接成链彻底规避了数据移动的开销。链表的每个节点由两部分组成数据域存储当前节点的真实数据指针域存储下一个节点的内存地址靠地址把所有节点串联起来正因为靠指针连接链表不需要连续的内存空间可以动态利用零散内存但也失去了下标随机访问的能力查找必须从头节点逐个向后遍历。2. 链表的分类1单向链表最基础的链表结构每个节点只保存下一个节点的地址只能从头到尾单向遍历是所有链表的基础。本文的核心讲解与代码实现都围绕单向链表展开。2双向链表在单向链表基础上每个节点额外保存上一个节点的地址既可以向后遍历也可以向前遍历。操作更灵活但每个节点多了一块指针内存开销Java 原生的LinkedList底层就是双向链表。核心规律掌握了单向链表的增删改查双向链表只需额外处理前驱指针即可逻辑完全对称。3. 链表与数组的核心特性对比特性数组ArrayList单向链表内存分布连续的整块内存节点离散分布靠指针连接随机访问O(1)按下标直接定位O(n)必须从头遍历头部/中间插入删除O(n)需要移动大量后续元素O(1)只需修改指针前提是已找到前驱节点尾部插入均摊O(1)扩容时为O(n)O(n)需要先遍历找到尾节点带尾指针优化后为O(1)空间开销固定容量存在闲置空间浪费每个节点需额外存储指针单位数据开销更高缓存友好性连续内存CPU缓存命中率高内存分散缓存不友好适用场景频繁随机访问、尾部增删多频繁在头部/中间插入删除、随机访问少二、单向链表节点类的定义链表的基本单元是节点首先需要定义一个节点类Node封装数据域与指针域。1. Node 节点类代码/** * 单向链表的节点类 */publicclassNode{// 数据域存储节点的值intvalue;// 指针域存储下一个节点的引用地址Nodenext;/** * 带参构造方法创建节点时直接赋值 * param value 节点存储的数值 */publicNode(intvalue){this.valuevalue;this.nextnull;// 新节点默认没有后继节点}}2. 节点的内存结构每个Node对象在堆内存中开辟独立空间包含value数据和next引用栈内存中存储节点变量保存堆中节点对象的地址堆内存中存储节点的真实数据next字段保存下一个节点的堆地址当一个节点没有任何引用指向它时会被Java垃圾回收器自动回收3. 手动构建链表示例publicclassTest{publicstaticvoidmain(String[]args){// 手动创建三个节点Nodenode1newNode(5);Nodenode2newNode(7);Nodenode3newNode(4);// 通过next指针串联节点node1.nextnode2;node2.nextnode3;// 此时链表结构5 - 7 - 4 - null}}手动构建只能用于理解原理实际开发中不会逐个手动创建节点而是封装成链表类通过方法自动管理节点的增删改查。三、自定义单向链表的完整实现下面从零实现一个完整的单向链表类MyLinkedList封装头节点、链表长度与所有增删改查方法完全对齐底层原理。1. 链表类的基础结构/** * 自定义单向链表 */publicclassMyLinkedList{// 头节点引用指向链表的第一个节点privateNodehead;// 记录链表有效节点个数可选避免每次获取长度都遍历privateintsize;/** * 无参构造初始化空链表 */publicMyLinkedList(){this.headnull;this.size0;}// 获取链表长度publicintsize(){returnsize;}// 判断链表是否为空publicbooleanisEmpty(){returnsize0;}}head是链表的入口所有操作都必须从头节点开始向后遍历size成员变量可以避免每次获取长度都全量遍历属于工程化优化2. 尾插法尾部添加节点尾插法是最常用的插入方式新节点永远添加到链表的最后一个位置。执行步骤创建新节点封装要插入的数据如果链表为空head为null直接让head指向新节点如果链表非空定义游标从头节点开始遍历直到找到最后一个节点next为null的节点将最后一个节点的next指向新节点链表长度size加1代码实现/** * 尾插法在链表尾部添加节点 * param value 要插入的数值 */publicvoidaddLast(intvalue){NodenewNodenewNode(value);// 空链表新节点直接作为头节点if(headnull){headnewNode;size;return;}// 非空链表遍历找到最后一个节点Nodecurhead;while(cur.next!null){curcur.next;// 游标后移}// 尾节点的next指向新节点cur.nextnewNode;size;}优化点如果增加一个last尾指针尾部插入可以直接O(1)完成不需要遍历这就是双向链表的优化思路。3. 头插法头部添加节点头插法新节点永远插入到链表的最前面成为新的头节点。执行步骤创建新节点新节点的next指向原来的头节点head引用重新指向新节点长度加1代码实现/** * 头插法在链表头部添加节点 * param value 要插入的数值 */publicvoidaddFirst(intvalue){NodenewNodenewNode(value);// 关键顺序先让新节点连上原链表再改头指针newNode.nexthead;headnewNode;size;}核心坑点必须先让新节点指向原头节点再修改head引用。如果先改head原链表的所有节点都会失去引用直接丢失。头插法可以用来实现链表倒序按正序插入的节点用头插法添加后会自动变成逆序。4. 指定位置插入节点在指定下标位置插入新节点下标从0开始。执行步骤参数合法性校验下标不能小于0不能大于size等于size时等价于尾插下标为0直接调用头插法下标为size直接调用尾插法中间位置插入定义游标遍历到插入位置的前一个节点前驱节点pre新节点的next指向pre原来的后继节点pre的next指向新节点长度加1代码实现/** * 在指定下标位置插入节点 * param index 插入位置下标从0开始 * param value 要插入的数值 */publicvoidadd(intindex,intvalue){// 下标合法性校验if(index0||indexsize){thrownewIndexOutOfBoundsException(插入下标越界);}// 头部插入if(index0){addFirst(value);return;}// 尾部插入if(indexsize){addLast(value);return;}// 中间插入找到前驱节点index-1的位置Nodeprehead;for(inti0;iindex-1;i){prepre.next;}NodenewNodenewNode(value);// 先连后面再改前面避免断链newNode.nextpre.next;pre.nextnewNode;size;}核心逻辑链表插入永远要先找前驱节点只能通过前驱节点的next指针完成插入操作。插入顺序必须「先连后继再改前驱」否则会丢失后续节点的引用。5. 有序链表插入扩展如果要维护一个升序的链表不需要手动指定下标自动找到合适位置插入。代码实现/** * 有序插入按升序自动找到合适位置插入 * param value 要插入的数值 */publicvoidaddSorted(intvalue){NodenewNodenewNode(value);// 空链表 或 比头节点还小头插if(headnull||valuehead.value){newNode.nexthead;headnewNode;size;return;}// 找到第一个比value大的节点的前驱Nodeprehead;while(pre.next!nullpre.next.valuevalue){prepre.next;}// 插入到pre后面newNode.nextpre.next;pre.nextnewNode;size;}6. 查找操作链表查找必须从头节点开始遍历分为按下标查找和按值查找。1按下标查找节点/** * 根据下标获取节点 * param index 下标 * return 对应节点的值 */publicintget(intindex){checkIndex(index);Nodecurhead;for(inti0;iindex;i){curcur.next;}returncur.value;}// 下标合法性校验privatevoidcheckIndex(intindex){if(index0||indexsize){thrownewIndexOutOfBoundsException(下标越界);}}2按值查找是否存在/** * 查找值是否存在于链表中 * param value 目标值 * return 是否存在 */publicbooleancontains(intvalue){Nodecurhead;while(cur!null){if(cur.valuevalue){returntrue;}curcur.next;}returnfalse;}7. 修改操作按下标修改节点值/** * 修改指定下标的节点值 * param index 下标 * param newValue 新值 * return 修改前的旧值 */publicintset(intindex,intnewValue){checkIndex(index);Nodecurhead;for(inti0;iindex;i){curcur.next;}intoldValuecur.value;cur.valuenewValue;returnoldValue;}8. 删除操作链表删除的核心让被删除节点失去所有引用只需修改前驱节点的next指针跳过被删节点即可被删节点会被垃圾回收自动清理不需要手动释放内存。1删除指定下标的节点执行步骤下标合法性校验下标范围 0 ~ size-1删除头节点直接让head head.next删除中间/尾节点找到被删节点的前驱节点prepre.next pre.next.next跳过被删节点长度减1返回被删的值代码实现/** * 删除指定下标的节点 * param index 要删除的下标 * return 被删除节点的值 */publicintremove(intindex){checkIndex(index);// 删除头节点if(index0){intoldValuehead.value;headhead.next;size--;returnoldValue;}// 找到前驱节点Nodeprehead;for(inti0;iindex-1;i){prepre.next;}NodedelNodepre.next;// 被删除的节点pre.nextdelNode.next;// 前驱直接指向后继跳过被删节点size--;returndelNode.value;}2删除第一个匹配值的节点/** * 删除第一个值为value的节点 * param value 要删除的值 * return 是否删除成功 */publicbooleanremoveByValue(intvalue){if(headnull){returnfalse;}// 头节点就是目标值if(head.valuevalue){headhead.next;size--;returntrue;}// 找目标节点的前驱Nodeprehead;while(pre.next!null){if(pre.next.valuevalue){pre.nextpre.next.next;size--;returntrue;}prepre.next;}returnfalse;}9. 优化方案虚拟头节点上面的删除、插入都需要单独处理头节点的情况代码有冗余。虚拟头节点哨兵节点可以统一所有位置的操作逻辑在真实头节点前面加一个不存数据的假节点作为永久的头节点所有插入、删除都不需要单独处理头节点逻辑完全统一虚拟头节点版本的删除示例publicclassMyLinkedListWithDummy{privateNodedummyHead;// 虚拟头节点privateintsize;publicMyLinkedListWithDummy(){dummyHeadnewNode(0);// 虚拟节点值无意义size0;}// 删除指定下标无需单独处理头节点publicintremove(intindex){if(index0||indexsize){thrownewIndexOutOfBoundsException();}NodepredummyHead;for(inti0;iindex;i){prepre.next;}Nodedelpre.next;pre.nextdel.next;size--;returndel.value;}}虚拟头节点是链表算法题的常用技巧能大幅简化边界处理避免空指针异常。10. 遍历与toString方法重写toString遍历链表拼接成可读字符串OverridepublicStringtoString(){if(headnull){return[];}StringBuildersbnewStringBuilder([);Nodecurhead;while(cur!null){sb.append(cur.value);if(cur.next!null){sb.append( - );}curcur.next;}sb.append(]);returnsb.toString();}11. 完整测试示例publicstaticvoidmain(String[]args){MyLinkedListlistnewMyLinkedList();// 尾插测试list.addLast(5);list.addLast(7);list.addLast(4);System.out.println(尾插后list);// [5 - 7 - 4]// 头插测试list.addFirst(3);System.out.println(头插后list);// [3 - 5 - 7 - 4]// 指定位置插入list.add(2,100);System.out.println(下标2插入100list);// [3 - 5 - 100 - 7 - 4]// 查找测试System.out.println(下标3的值list.get(3));// 7System.out.println(是否包含100list.contains(100));// true// 删除测试list.remove(2);System.out.println(删除下标2list);// [3 - 5 - 7 - 4]// 长度System.out.println(链表长度list.size());// 4}四、链表经典面试题快慢指针专题快慢指针是链表最高频的算法技巧通过两个移动速度不同的指针在仅遍历一次的前提下完成多类问题是面试必考点。1. 查找链表的中间节点题目描述给定一个头节点只遍历一次找到链表的中间节点。如果是偶数个节点返回中间两个的任意一个即可。解题思路定义两个指针fast快指针和slow慢指针同时从头节点出发slow每次走 1 步fast每次走 2 步当fast走到链表末尾时slow走过的路程刚好是fast的一半正好指向中间节点。边界处理快指针走两步的前提fast本身不为空且fast.next也不为空否则会出现空指针异常。代码实现/** * 查找链表中间节点 * param head 链表头节点 * return 中间节点 */publicNodefindMiddleNode(Nodehead){if(headnull){returnnull;}Nodefasthead;Nodeslowhead;// 快指针没走到末尾就继续while(fast!nullfast.next!null){slowslow.next;// 慢指针走1步fastfast.next.next;// 快指针走2步}returnslow;}原理说明奇数个节点fast走到最后一个节点时停止slow正好在正中间偶数个节点fast走到null时停止slow指向中间两个节点的后一个2. 查找链表的倒数第K个节点题目描述只遍历一次链表找到倒数第k个节点。解题思路依然使用快慢指针让两个指针保持固定的k步距离快指针fast先走 k 步快慢指针以相同速度同时向后移动当fast走到链表末尾为null时slow正好指向倒数第k个节点代码实现/** * 查找倒数第k个节点 * param head 头节点 * param k 倒数第k个 * return 目标节点 */publicNodefindLastKth(Nodehead,intk){if(headnull||k0){returnnull;}Nodefasthead;Nodeslowhead;// 快指针先走k步for(inti0;ik;i){if(fastnull){returnnull;// k大于链表长度非法}fastfast.next;}// 同步移动while(fast!null){slowslow.next;fastfast.next;}returnslow;}3. 判断链表是否有环题目描述判断一个链表中是否存在环形结构某个节点的next指向了链表中之前的节点形成闭环。解题思路经典的「龟兔赛跑」算法依然用快慢指针slow每次走1步fast每次走2步如果链表无环fast会先走到终点null永远不会和slow相遇如果链表有环两个指针进入环后相当于追击问题fast每次比slow多走1步一定会追上slow二者相遇则证明有环为什么一定会相遇可以用追击问题理解slow进入环时fast已经在环里了二者初始距离为xfast每次比slow多走1步每走一轮距离就缩短1最多走x轮fast一定会追上slow二者指向同一节点代码实现/** * 判断链表是否有环 * param head 头节点 * return 是否有环 */publicbooleanhasCycle(Nodehead){if(headnull||head.nextnull){returnfalse;}Nodefasthead;Nodeslowhead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;// 两个指针相遇说明有环if(slowfast){returntrue;}}// fast走到了终点说明无环returnfalse;}扩展考点如果要找环形链表的入环节点在相遇后让一个指针回到头节点两个指针都以步长1同时移动再次相遇的位置就是入环点这是力扣142题的经典结论。五、链表核心特性总结1. 时间复杂度汇总操作时间复杂度说明头部插入/删除O(1)直接修改头指针尾部插入/删除O(n)需要遍历找到尾节点带尾指针优化后为O(1)中间插入/删除O(n)主要耗时在查找前驱节点修改指针本身是O(1)按下标查找O(n)必须从头遍历按值查找O(n)必须从头遍历2. 核心优缺点优势插入删除操作灵活不需要移动数据动态扩容不需要预先分配内存不会有空间浪费劣势无法随机访问查找效率低每个节点需要额外存储指针内存开销更大缓存不友好性能弱于数组3. 工程应用场景频繁在头部、中间位置进行插入删除的场景数据量不确定、动态增长的线性数据实现栈、队列、哈希表、LRU缓存等高级数据结构的底层载体