数据结构 五

数据结构 五

承接上文数组与ArrayList的底层实现，本文系统讲解线性表的另一核心结构——链表。链表通过指针连接分散的内存节点，彻底解决了数组插入删除需要移动大量数据的问题，是算法面试的高频考察点。本文将从底层原理、完整代码实现、经典面试题三个维度，逐层拆解单向链表的增删改查与快慢指针核心算法，覆盖从入门到面试的全量知识点。

一、链表基础概念

1. 链表的本质与核心特点

数组是连续内存存储的线性结构，优势是随机访问快，但插入删除需要移动大量数据，效率低；而链表是离散内存存储的线性结构，节点在内存中零散分布，靠指针域连接成链，彻底规避了数据移动的开销。

链表的每个节点由两部分组成：

• 数据域：存储当前节点的真实数据
• 指针域：存储下一个节点的内存地址，靠地址把所有节点串联起来

正因为靠指针连接，链表不需要连续的内存空间，可以动态利用零散内存，但也失去了下标随机访问的能力，查找必须从头节点逐个向后遍历。

2. 链表的分类

（1）单向链表

最基础的链表结构，每个节点只保存下一个节点的地址，只能从头到尾单向遍历，是所有链表的基础。本文的核心讲解与代码实现都围绕单向链表展开。

（2）双向链表

在单向链表基础上，每个节点额外保存上一个节点的地址，既可以向后遍历，也可以向前遍历。操作更灵活，但每个节点多了一块指针内存开销，Java 原生的LinkedList底层就是双向链表。

核心规律：掌握了单向链表的增删改查，双向链表只需额外处理前驱指针即可，逻辑完全对称。

3. 链表与数组的核心特性对比

二、单向链表节点类的定义

链表的基本单元是节点，首先需要定义一个节点类Node，封装数据域与指针域。

1. Node 节点类代码

/** * 单向链表的节点类 */publicclassNode{// 数据域：存储节点的值intvalue;// 指针域：存储下一个节点的引用（地址）Nodenext;/** * 带参构造方法：创建节点时直接赋值 * @param value 节点存储的数值 */publicNode(intvalue){this.value=value;this.next=null;// 新节点默认没有后继节点}}

2. 节点的内存结构

每个Node对象在堆内存中开辟独立空间，包含value数据和next引用：

• 栈内存中存储节点变量，保存堆中节点对象的地址
• 堆内存中存储节点的真实数据，next字段保存下一个节点的堆地址
• 当一个节点没有任何引用指向它时，会被Java垃圾回收器自动回收

3. 手动构建链表示例

publicclassTest{publicstaticvoidmain(String[]args){// 手动创建三个节点Nodenode1=newNode(5);Nodenode2=newNode(7);Nodenode3=newNode(4);// 通过next指针串联节点node1.next=node2;node2.next=node3;// 此时链表结构：5 -> 7 -> 4 -> null}}

手动构建只能用于理解原理，实际开发中不会逐个手动创建节点，而是封装成链表类，通过方法自动管理节点的增删改查。

三、自定义单向链表的完整实现

下面从零实现一个完整的单向链表类MyLinkedList，封装头节点、链表长度与所有增删改查方法，完全对齐底层原理。

1. 链表类的基础结构

/** * 自定义单向链表 */publicclassMyLinkedList{// 头节点引用：指向链表的第一个节点privateNodehead;// 记录链表有效节点个数（可选，避免每次获取长度都遍历）privateintsize;/** * 无参构造：初始化空链表 */publicMyLinkedList(){this.head=null;this.size=0;}// 获取链表长度publicintsize(){returnsize;}// 判断链表是否为空publicbooleanisEmpty(){returnsize==0;}}

• head是链表的入口，所有操作都必须从头节点开始向后遍历
• size成员变量可以避免每次获取长度都全量遍历，属于工程化优化

2. 尾插法：尾部添加节点

尾插法是最常用的插入方式：新节点永远添加到链表的最后一个位置。

执行步骤

1. 创建新节点，封装要插入的数据
2. 如果链表为空（head为null），直接让head指向新节点
3. 如果链表非空，定义游标从头节点开始遍历，直到找到最后一个节点（next为null的节点）
4. 将最后一个节点的next指向新节点
5. 链表长度size加1

代码实现

/** * 尾插法：在链表尾部添加节点 * @param value 要插入的数值 */publicvoidaddLast(intvalue){NodenewNode=newNode(value);// 空链表：新节点直接作为头节点if(head==null){head=newNode;size++;return;}// 非空链表：遍历找到最后一个节点Nodecur=head;while(cur.next!=null){cur=cur.next;// 游标后移}// 尾节点的next指向新节点cur.next=newNode;size++;}

优化点：如果增加一个last尾指针，尾部插入可以直接O(1)完成，不需要遍历，这就是双向链表的优化思路。

3. 头插法：头部添加节点

头插法：新节点永远插入到链表的最前面，成为新的头节点。

执行步骤

1. 创建新节点
2. 新节点的next指向原来的头节点
3. head引用重新指向新节点
4. 长度加1

代码实现

/** * 头插法：在链表头部添加节点 * @param value 要插入的数值 */publicvoidaddFirst(intvalue){NodenewNode=newNode(value);// 关键顺序：先让新节点连上原链表，再改头指针newNode.next=head;head=newNode;size++;}

核心坑点：必须先让新节点指向原头节点，再修改head引用。如果先改head，原链表的所有节点都会失去引用，直接丢失。
头插法可以用来实现链表倒序：按正序插入的节点，用头插法添加后会自动变成逆序。

4. 指定位置插入节点

在指定下标位置插入新节点，下标从0开始。

执行步骤

1. 参数合法性校验：下标不能小于0，不能大于size（等于size时等价于尾插）
2. 下标为0：直接调用头插法
3. 下标为size：直接调用尾插法
4. 中间位置插入：
   • 定义游标遍历到插入位置的前一个节点（前驱节点pre）
   • 新节点的next指向pre原来的后继节点
   • pre的next指向新节点
5. 长度加1

代码实现

/** * 在指定下标位置插入节点 * @param index 插入位置（下标从0开始） * @param value 要插入的数值 */publicvoidadd(intindex,intvalue){// 下标合法性校验if(index<0||index>size){thrownewIndexOutOfBoundsException("插入下标越界");}// 头部插入if(index==0){addFirst(value);return;}// 尾部插入if(index==size){addLast(value);return;}// 中间插入：找到前驱节点（index-1的位置）Nodepre=head;for(inti=0;i<index-1;i++){pre=pre.next;}NodenewNode=newNode(value);// 先连后面，再改前面，避免断链newNode.next=pre.next;pre.next=newNode;size++;}

核心逻辑：链表插入永远要先找前驱节点，只能通过前驱节点的next指针完成插入操作。插入顺序必须「先连后继，再改前驱」，否则会丢失后续节点的引用。

5. 有序链表插入（扩展）

如果要维护一个升序的链表，不需要手动指定下标，自动找到合适位置插入。

代码实现

/** * 有序插入：按升序自动找到合适位置插入 * @param value 要插入的数值 */publicvoidaddSorted(intvalue){NodenewNode=newNode(value);// 空链表 或 比头节点还小：头插if(head==null||value<=head.value){newNode.next=head;head=newNode;size++;return;}// 找到第一个比value大的节点的前驱Nodepre=head;while(pre.next!=null&&pre.next.value<value){pre=pre.next;}// 插入到pre后面newNode.next=pre.next;pre.next=newNode;size++;}

6. 查找操作

链表查找必须从头节点开始遍历，分为按下标查找和按值查找。

（1）按下标查找节点

/** * 根据下标获取节点 * @param index 下标 * @return 对应节点的值 */publicintget(intindex){checkIndex(index);Nodecur=head;for(inti=0;i<index;i++){cur=cur.next;}returncur.value;}// 下标合法性校验privatevoidcheckIndex(intindex){if(index<0||index>=size){thrownewIndexOutOfBoundsException("下标越界");}}

（2）按值查找是否存在

/** * 查找值是否存在于链表中 * @param value 目标值 * @return 是否存在 */publicbooleancontains(intvalue){Nodecur=head;while(cur!=null){if(cur.value==value){returntrue;}cur=cur.next;}returnfalse;}

7. 修改操作

按下标修改节点值

/** * 修改指定下标的节点值 * @param index 下标 * @param newValue 新值 * @return 修改前的旧值 */publicintset(intindex,intnewValue){checkIndex(index);Nodecur=head;for(inti=0;i<index;i++){cur=cur.next;}intoldValue=cur.value;cur.value=newValue;returnoldValue;}

8. 删除操作

链表删除的核心：让被删除节点失去所有引用，只需修改前驱节点的next指针，跳过被删节点即可，被删节点会被垃圾回收自动清理，不需要手动释放内存。

（1）删除指定下标的节点

执行步骤

1. 下标合法性校验：下标范围 0 ~ size-1
2. 删除头节点：直接让head = head.next
3. 删除中间/尾节点：
   • 找到被删节点的前驱节点pre
   • pre.next = pre.next.next（跳过被删节点）
4. 长度减1，返回被删的值

代码实现

/** * 删除指定下标的节点 * @param index 要删除的下标 * @return 被删除节点的值 */publicintremove(intindex){checkIndex(index);// 删除头节点if(index==0){intoldValue=head.value;head=head.next;size--;returnoldValue;}// 找到前驱节点Nodepre=head;for(inti=0;i<index-1;i++){pre=pre.next;}NodedelNode=pre.next;// 被删除的节点pre.next=delNode.next;// 前驱直接指向后继，跳过被删节点size--;returndelNode.value;}

（2）删除第一个匹配值的节点

/** * 删除第一个值为value的节点 * @param value 要删除的值 * @return 是否删除成功 */publicbooleanremoveByValue(intvalue){if(head==null){returnfalse;}// 头节点就是目标值if(head.value==value){head=head.next;size--;returntrue;}// 找目标节点的前驱Nodepre=head;while(pre.next!=null){if(pre.next.value==value){pre.next=pre.next.next;size--;returntrue;}pre=pre.next;}returnfalse;}

9. 优化方案：虚拟头节点

上面的删除、插入都需要单独处理头节点的情况，代码有冗余。虚拟头节点（哨兵节点）可以统一所有位置的操作逻辑：

• 在真实头节点前面加一个不存数据的假节点，作为永久的头节点
• 所有插入、删除都不需要单独处理头节点，逻辑完全统一

虚拟头节点版本的删除示例

publicclassMyLinkedListWithDummy{privateNodedummyHead;// 虚拟头节点privateintsize;publicMyLinkedListWithDummy(){dummyHead=newNode(0);// 虚拟节点值无意义size=0;}// 删除指定下标，无需单独处理头节点publicintremove(intindex){if(index<0||index>=size){thrownewIndexOutOfBoundsException();}Nodepre=dummyHead;for(inti=0;i<index;i++){pre=pre.next;}Nodedel=pre.next;pre.next=del.next;size--;returndel.value;}}

虚拟头节点是链表算法题的常用技巧，能大幅简化边界处理，避免空指针异常。

10. 遍历与toString方法

重写toString，遍历链表拼接成可读字符串：

@OverridepublicStringtoString(){if(head==null){return"[]";}StringBuildersb=newStringBuilder("[");Nodecur=head;while(cur!=null){sb.append(cur.value);if(cur.next!=null){sb.append(" -> ");}cur=cur.next;}sb.append("]");returnsb.toString();}

11. 完整测试示例

publicstaticvoidmain(String[]args){MyLinkedListlist=newMyLinkedList();// 尾插测试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插入100："+list);// [3 -> 5 -> 100 -> 7 -> 4]// 查找测试System.out.println("下标3的值："+list.get(3));// 7System.out.println("是否包含100："+list.contains(100));// true// 删除测试list.remove(2);System.out.println("删除下标2："+list);// [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(head==null){returnnull;}Nodefast=head;Nodeslow=head;// 快指针没走到末尾就继续while(fast!=null&&fast.next!=null){slow=slow.next;// 慢指针走1步fast=fast.next.next;// 快指针走2步}returnslow;}

原理说明

• 奇数个节点：fast走到最后一个节点时停止，slow正好在正中间
• 偶数个节点：fast走到null时停止，slow指向中间两个节点的后一个

2. 查找链表的倒数第K个节点

题目描述

只遍历一次链表，找到倒数第k个节点。

解题思路

依然使用快慢指针，让两个指针保持固定的k步距离：

1. 快指针fast先走 k 步
2. 快慢指针以相同速度同时向后移动
3. 当fast走到链表末尾（为null）时，slow正好指向倒数第k个节点

代码实现

/** * 查找倒数第k个节点 * @param head 头节点 * @param k 倒数第k个 * @return 目标节点 */publicNodefindLastKth(Nodehead,intk){if(head==null||k<=0){returnnull;}Nodefast=head;Nodeslow=head;// 快指针先走k步for(inti=0;i<k;i++){if(fast==null){returnnull;// k大于链表长度，非法}fast=fast.next;}// 同步移动while(fast!=null){slow=slow.next;fast=fast.next;}returnslow;}

3. 判断链表是否有环

题目描述

判断一个链表中是否存在环形结构（某个节点的next指向了链表中之前的节点，形成闭环）。

解题思路

经典的「龟兔赛跑」算法，依然用快慢指针：

• slow每次走1步，fast每次走2步
• 如果链表无环，fast会先走到终点（null），永远不会和slow相遇
• 如果链表有环，两个指针进入环后，相当于追击问题：fast每次比slow多走1步，一定会追上slow，二者相遇则证明有环

为什么一定会相遇？

可以用追击问题理解：

• slow进入环时，fast已经在环里了，二者初始距离为x
• fast每次比slow多走1步，每走一轮距离就缩短1
• 最多走x轮，fast一定会追上slow，二者指向同一节点

代码实现

/** * 判断链表是否有环 * @param head 头节点 * @return 是否有环 */publicbooleanhasCycle(Nodehead){if(head==null||head.next==null){returnfalse;}Nodefast=head;Nodeslow=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;// 两个指针相遇，说明有环if(slow==fast){returntrue;}}// fast走到了终点，说明无环returnfalse;}

扩展考点：如果要找环形链表的入环节点，在相遇后让一个指针回到头节点，两个指针都以步长1同时移动，再次相遇的位置就是入环点，这是力扣142题的经典结论。

五、链表核心特性总结

1. 时间复杂度汇总

2. 核心优缺点

• 优势：插入删除操作灵活，不需要移动数据；动态扩容，不需要预先分配内存，不会有空间浪费
• 劣势：无法随机访问，查找效率低；每个节点需要额外存储指针，内存开销更大；缓存不友好，性能弱于数组

3. 工程应用场景

• 频繁在头部、中间位置进行插入删除的场景
• 数据量不确定、动态增长的线性数据
• 实现栈、队列、哈希表、LRU缓存等高级数据结构的底层载体