你好我是林森lsjs我的Github 地址sqyCoder (Qiyang) · GitHub以博文记录成长用心打磨代码与思维目录一、引入单链表二、链表的三种分类形态2.1 单向链表 vs 双向链表2.2 是否带有 dummy 傀儡头结点不带头结点无傀儡结点带傀儡dummy/头结点链表2.3 带环链表 vs 不带环链表循环链表三、手搓单链表第一步写节点类 LinkedNode链表最小零件第二步链表容器 MyLinkedList 的外壳第三步size()计算链表一共有多少个有效节点第四步addFirst(int value) 头插在链表最前面加节点第五步addLast(int value)尾插放到链表末尾第六步add(int index, int value)在指定下标插入节点第七步get(int index) 根据下标拿数据第八步set(int index, int value) 修改下标位置的值第九步remove(int index)按下标删除节点第十步removeByValue(int value) 删除第一个等于 value 的节点第十一步removeAllValue(int value) 删除全部等于 value 的节点第十二步辅助方法 contains、indexOf、clear、toString核心要点一、引入单链表二、链表的三种分类形态2.1 单向链表 vs 双向链表单向链表每个结点只保存下一个结点的地址只能向后遍历无法直接找到前一个结点。双向链表每个结点有两份引用一份存上一个结点地址一份存下一个结点地址既可以向前走也可以向后遍历。2.2 是否带有 dummy 傀儡头结点不带头结点无傀儡结点head指针直接指向第一个存有效数据的结点。缺点做增删操作的时候如果操作的是链表第一个结点需要单独写特殊逻辑处理head头指针代码会多出分支判断。带傀儡dummy/头结点链表head指向一个专门的傀儡结点这个结点的数据区域不存放有效业务数据傀儡结点的next才指向真正第一个有效元素。作用不管链表是空链表还是操作第一个真实结点头指针永远不动所有增删逻辑写法统一不用写特殊分支简化代码逻辑。面试别名带表头结点英文叫 dummy node。2.3 带环链表 vs 不带环链表循环链表普通不带环链表末尾结点的next引用指向null遍历遇到null就代表链表结束。带环循环链表尾结点不再指向null而是指向链表中间某一个结点链表形成环路。注意带环链表大多出现在笔试面试题目日常开发实际项目很少遇到。链表做题先分清三件事单向还是双向有没有 dummy 傀儡头结点是否带环。不同形态代码写法会有明显区别。三、手搓单链表先记住最根本单链表是一堆节点串起来。每个节点存两样数据val下一个节点的地址next。整个链表只保存头节点head。有了head依靠cur cur.next一步一步向后走访问全部节点。重要概念前驱节点要操作第index位置必须拿到它前面那一个节点单链表不能往回走没有办法直接跳到index。头节点没有前驱。第一步写节点类 LinkedNode链表最小零件java class LinkedNode { // public链表类里面要直接访问这两个成员方便写代码 public int val; // next 保存下一个节点对象如果是最后一个节点 next null代表后面没有节点了 public LinkedNode next; // 构造方法新建节点的时候必须传入数据 val public LinkedNode(int val) { // this.val 是对象自己的 val右边 val 是传入的参数 this.val val; // 刚创建节点还没有连接任何别的节点next 默认等于 null this.next null; } }逐行理解public int val用来存放我们要存的整数数据。public LinkedNode nextnext的类型是LinkedNode代表它可以保存另一个节点的引用相当于一根绳子拴住下一个节点。最后一个节点没有下家所以next null。构造函数每当执行new LinkedNode(10)就造出一个存10的节点next自动设置成null。第二步链表容器 MyLinkedList 的外壳public class MyLinkedList { // head头节点链表入口。private不让外部代码随便乱改 head。 // 链表为空的时候head null代表一个节点都没有 private LinkedNode head null; public LinkedNode getHead() { return head; } // 所有的方法全部写在这个大括号 {} 内部不能写到外面 }重点链表对象本身不存数据只存head。全部节点靠head顺着next找到。如果head变成null整个链表全部丢失。第三步size()计算链表一共有多少个有效节点public int size() { // 情况1head 是 null链表里面一个节点都没有直接返回长度 0 if (head null) { return 0; } // cur遍历用的指针变量一开始让 cur 等于 head从第一个节点开始走 LinkedNode cur head; int size 0; // while 循环条件 cur ! null只要 cur 不是 null就说明当前 cur 指向一个真实存在的节点 while (cur ! null) { size size 1; // 计数 1统计节点数量 cur cur.next; // 核心语句指针向后移动一步cur 去指向下一个节点 } return size; }逐句拆解LinkedNode cur headcur就是我们的手指一开始手指指向第一个节点head。while(cur ! null)只要手指还指着节点就继续循环。cur cur.next手指挪到下一个节点。这一句是链表遍历灵魂。区分两个循环条件while(cur ! null)遍历每一个节点可以读到最后一个节点。while(cur.next ! null)循环停止的时候cur停在最后一个节点。第四步addFirst(int value) 头插在链表最前面加节点public void addFirst(int value) { // 1. 创建新节点保存传入的数据 LinkedNode newNode new LinkedNode(value); // 2. 判断链表是不是空链表head null if (head null) { // 链表为空新节点直接作为头节点 head newNode; return; // 方法直接结束后面代码不再执行 } // 链表不为空 newNode.next head; // 新节点的 next指向原来链表的第一个节点 head head newNode; // 把 head 更新成新节点现在新节点变成链表第一个节点 }⚠️千万不能写反顺序错误写法javahead newNode; newNode.next head;先把head赋值成newNode再newNode.next head结果新节点自己指向自己链表直接全部丢失死循环。口诀头插新节点先接老链表再更新 head。第五步addLast(int value)尾插放到链表末尾public void addLast(int value) { // 新建节点 LinkedNode newNode new LinkedNode(value); // 空链表特殊处理 if (head null) { head newNode; return; } // 定义 cur 指针从头开始找到最后一个节点 LinkedNode cur head; // 循环条件 cur.next ! null只要当前节点的下一个不是 null说明还不是尾巴继续向后走 while (cur.next ! null) { cur cur.next; } // 退出 while 的时候cur 一定是最后一个节点cur.next 是 null cur.next newNode; // 把最后节点的 next 指向新节点新节点接上链表尾巴 }重点找尾巴用while(cur.next ! null)循环结束cur就是尾节点。第六步add(int index, int value)在指定下标插入节点下标规则链表下标从 0 开始。允许的index范围0 ≤ index ≤ size()。index 0插到最前面index size插到链表最后中间的index插到第index位置。public void add(int index, int value) { int size this.size(); // 第一步判断下标非法。index 小于 0或者 index 大于 size抛异常 if (index 0 || index size) { throw new IndexOutOfBoundsException(下标越界! index index); } // 情况1插最前面直接调用已经写好的 addFirst if (index 0) { addFirst(value); return; } // 情况2插到链表末尾直接调用 addLast if (index size) { addLast(value); return; } // 剩下就是插链表中间。核心逻辑要插入到 index 位置要先找到 index-1 位置的节点前驱 prev LinkedNode prev head; // 循环执行 index-1 次prev 走到 index-1 的位置 for (int i 0; i index - 1; i) { prev prev.next; } // 循环结束 prev 就是前驱节点 LinkedNode newNode new LinkedNode(value); newNode.next prev.next; // 第一步新节点先把后面的链表接住 prev.next newNode; // 第二步前驱节点指向新节点完成链接 }中间插入铁律口诀找前驱先连后再连前。顺序不能颠倒。如果反过来先写prev.next newNodeprev.next原来保存的后面链表直接丢掉断链第七步get(int index) 根据下标拿数据public int get(int index) { // get 不能允许 index 等于 size下标最大是 size-1 if (index 0 || index size()) { throw new IndexOutOfBoundsException(); } int i 0; // i 记录当前 cur 指向的下标 LinkedNode cur head; // cur 逐个向后遍历 while (cur ! null) { if (i index) { return cur.val; // 找到了直接返回节点存储的数据 } i; // 下标计数增加 cur cur.next; // 指针向后移动 } // 前面已经做越界判断理论上代码不会跑到这里 return 0; }链表没有数组那样arr[index]直接访问必须从头一步一步走到目标下标时间复杂度O(n)。第八步set(int index, int value) 修改下标位置的值public void set(int index, int value) { if (index 0 || index size()) { throw new IndexOutOfBoundsException(); } int i 0; LinkedNode cur head; while (cur ! null) { if (i index) { cur.val value; // 不改动 next 指针只修改节点里面存的数据 return; } i; cur cur.next; } }注意set只是修改节点内部val节点在链表中的位置完全不动。第九步remove(int index)按下标删除节点删除核心找到要删除节点的前驱prevprev.next prev.next.next直接跳过待删节点。Java 没有指针释放节点没有引用指向自动被垃圾回收。public void remove(int index) { if (index 0 || index size()) { throw new IndexOutOfBoundsException(下标越界! index index); } // 特殊删除头节点 index0。头节点没有前驱 if (index 0) { head head.next; // head 直接跳到第二个节点原来第一个节点被丢弃 return; } // 找前驱 index-1 LinkedNode prev head; for (int i 0; i index - 1; i) { prev prev.next; } LinkedNode toDelete prev.next; // toDelete 就是要删掉的节点 prev.next toDelete.next; // prev 直接接 toDelete 的下家toDelete 从链表脱离 }删除头节点必须单独处理它没有前驱节点。第十步removeByValue(int value) 删除第一个等于 value 的节点public void removeByValue(int value) { // 空链表直接返回什么都不做 if (head null) { return; } // 如果头节点就是要删的节点单独处理 if (head.val value) { head head.next; return; } LinkedNode prev head; // 循环条件 prev.next ! null我们要看 prev 的下一个节点的值 while (prev.next ! null) { if (prev.next.val value) { break; // 找到了要删的节点跳出循环 } prev prev.next; // 没有找到prev 向后移动 } // 退出循环两种情况1.break 找到了2.prev.next null 遍历完没找到 if (prev.next null) { return; // 链表全部遍历完没有目标值直接结束 } LinkedNode toDelete prev.next; prev.next toDelete.next; }这个循环不是看prev自己是看prev.next因为我们要拿到待删节点的前驱。第十一步removeAllValue(int value) 删除全部等于 value 的节点双指针模式prev保存前一个节点cur扫描当前节点。public void removeAllValue(int value) { if (head null) { return; } LinkedNode prev head; LinkedNode cur head.next; // cur 从第二个节点开始扫描 while (cur ! null) { if (cur.val value) { // cur 节点需要删除prev 不动cur 跳到下一个 prev.next cur.next; cur cur.next; } else { // 不用删除prev、cur 两个指针一起向后挪 prev cur; cur cur.next; } } // 循环只处理 head 后面的节点最后单独判断头节点是不是要删除 if (head.val value) { head head.next; } }第十二步辅助方法 contains、indexOf、clear、toString// 判断链表是否包含这个数值 public boolean contains(int value) { // for 循环遍历链表cur 从 head 出发cur cur.next 向后移动 for (LinkedNode cur head; cur ! null; cur cur.next) { if (cur.val value) { return true; } } return false; } // 查找 value 第一次出现的下标找不到返回 -1 public int indexOf(int value) { int index 0; for (LinkedNode cur head; cur ! null; cur cur.next) { if (cur.val value) { return index; } index; } return -1; } // 清空链表 public void clear() { head null; // head 置空所有节点没有引用JVM 自动回收内存 } // 重写 toString输出格式 [1,2,3,4] Override public String toString() { StringBuilder stringBuilder new StringBuilder(); stringBuilder.append([); LinkedNode cur head; while (cur ! null) { stringBuilder.append(cur.val); // 不是最后一个节点追加逗号 if (cur.next ! null) { stringBuilder.append(,); } cur cur.next; } stringBuilder.append(]); return stringBuilder.toString(); }核心要点LinkedNode next存的是另一个节点的引用null代表没有节点。遍历LinkedNode cur head; while(cur ! null){ cur cur.next; }。找最后节点while(cur.next ! null)。插入中间、删除中间一定要拿到前驱节点prev。插入顺序新节点先接后面再让前驱接新节点顺序反直接断链。头节点没有前驱头插、删头节点全部要单独写分支处理。size()方法每次调用都完整遍历链表时间O(n)。今天的数据结构讲解就到这了我们下期再见诸位共勉