🛺前言:

        单向链表,数据结构中最基础的数据结构之一,本来我的计划是在我Java数据结构专栏的前几期就发布的,可是,理想和时间总是有冲突的,对此,最近我会把几种基础数据类型陆续推出,如:双向链表,队列,环形队列等共五篇,之后会更新史上最通俗易懂的八大排序算法,让我们拭目以待吧!

        单向链表的概述🔜单向链表的创建思路🔜单向链表的代码实现与分析🔜腾讯大厂面试题及解析🔜结论🔚

        如果喜欢勤奋的作者 ➡️ 戳我😁

往期精彩:

        迷宫回溯问题(蓝桥必备)

💞单向链表的概述: 

  单向链表:

• 单向链表是一个有序列表
• 单向链表是以节点的形式存储元素的
• 节点之间的内存地址并非连续的,这是与数组这种数据结构最大的区别
• 头节点是一个单向链表的灵魂,若头节点丢失,则整个单向链表丢失

 节点: 

• 节点有两个属性,分别是data域和next域(data域放自己想要放的元素) (next域是存放下一个节点内存地址)
• 头节点的data域为null,不能存储数据
• 头节点可以有,也可以没有 

💓单向链表的创建思路:

1.  首先创建一个节点类,里面创建对应的属性(data与next)
2.  其次创建一个单向链表类,用于管理节点和添加方法(属性是头节点)
3.  创建增删改插遍历的方法(详细的思路在代码分析处)

芜湖,完成了! 

❤️‍🔥单向链表的代码实现与分析: 

注意:本单向链表的创建以水浒英雄的信息的基础上进行创建 

•  创建一个节点类

public class HeroNode {    public int no;    public String name;    public String nickname;    public HeroNode next;    public HeroNode(int no,String name,String nickname) { this.no = no; this.name = name; this.nickname = nickname;    }    public HeroNode() {    }    public String toString() { return "英雄好汉的编号:" + no + " 名字:" + name + " 绰号:" + nickname;    }}

 代码分析:

1. 属性中的no,name,nickname是思路中的data域,用于存放数据
2. 属性中的next对应思路中的next,用于存放下一个节点的内存地址(是has a的关系即包含关系)
3. 需要提供无参构造和有参构造.无参构造的目的是为了创建一个头节点,有参构造的目的是为了创建一般的节点
4. 有参构造不能涉及下一个节点的创建

• 创建一个单向链表类

HeroNode head = new HeroNode();

1.  属性是为了创建一个头节点,从而去管理整个单向链表

•  创建一个遍历的方法

public void print() throws LinkedListException { if(head.next == null) {     throw new LinkedListException("链表为空,无法遍历"); } var cur = head.next; while(cur != null) {     System.out.println(cur);     cur = cur.next; }    }

  代码分析:

1. 当我们去遍历单向链表的时候,首先要做的就是判断该单向链表是否为空,若为空则直接抛出异常
2. 我们需要创建一个辅助引用cur去遍历链表(头节点是整个链表的灵魂,不能直接使用,避免丢失链表)
3. 如果单向链表不为空,说明单向链表有且至少有一个节点,所以给辅助引用赋予第一个节点的内存地址
4. 如果辅助引用指向的节点,不为空,即可以经行遍历输出,输出完后记得要跳到下一个节点.

        图解:

•   创建一个尾部增加节点的方法

public void finalAdd(HeroNode node) { //头节点的临时引用 var cur = head; while (cur.next != null) {     //跳转下一个节点     cur = cur.next; } cur.next = node;    }

代码分析:

1. 因为我们不知道该单向链表是否为空,所以我们不能想输出方法那样给辅助引用cur赋予第一个节点的内存地址,否则可能会出现空指针异常的情况
2. 当一个节点的next域是null的时候,说明该节点是尾节点
3. 在尾节点的next赋予下一个节点的内存地址相当于增加节点

•   创建一个插入节点的方法

public void InsertedAddByNo(HeroNode node) throws LinkedListException { boolean flag = false; var cur = head; while(true) {     if(cur.next == null) {  break;     }     if(cur.next.no > node.no){  break;     }else if(cur.next.no == node.no) {  flag = true;  break;     }     cur = cur.next; } if(!flag) {     node.next = cur.next;     cur.next = node;     return; } throw new LinkedListException("该编号已存在,无法添加");    }

 代码分析:

1.  注意的是,该插入的逻辑是按no这个属性的升序插入
2.  一般插入节点与删除节点都要打一布尔标记,以判断是否能插入或者能删除
3.  本代码同理得,由于不知道该单向链表是否有节点,所以辅助引用应当指向头节点
4.  第一个if的含义:如果是尾节点,直接跳出循环,避免空指针异常,也说明了直接将节点放入最后
5.  第二个if的含义:如果该节点的下一个节点的no大于待插入节点的no,说明该节点介于这两者之间

图解 

说明:

        单向链表中删除节点和插入节点都是要找该节点的上一个节点 

     6. 若该节点的下一个节点的no与node的no相等,说明该节点已经有了,应该改flag,避免插入

     7.最后通过flag,判断该节点是否已经存在,再加入(赋值顺序很重要)

     8.首先要node.next = cur.next;让他们两个同时指向一个节点,然后cur.next = node;让一个断掉

图解

•  创建一个删除节点的方法

public void delete(int no) throws LinkedListException { boolean flag = false; var cur = head; while(true) {     if(cur.next == null) {  break;     }     if(cur.next.no == no) {  flag = true;  break;     }     cur = cur.next; } if(flag) {     cur.next = cur.next.next;     return; } throw new LinkedListException("没有此节点");    }

代码分析:

1. 删除节点需要打一布尔标记,默认匹配不到待删除的节点
2. 本代码同理得,由于不知道该单向链表是否有节点,所以辅助引用应当指向头节点
3. 循环第一个if是判断是否为空,若为空直接跳出
4. 循环第二个if是判断下一个节点是否为待删除的节点,如果是改变flag,立刻退出,否则跳到下一个节点
5. 最后通过flag来删除节点

 图解:

•   创建一个修改节点的方法

public void update(HeroNode newNode) throws LinkedListException { boolean flag = false; var cur = head.next; while(true) {     if(cur == null) {  break;     }     if(cur.no == newNode.no) {  flag = true;  break;     }     cur = temp.next; } if(flag) {     cur.name = newNode.name;     cur.nickname = newNode.nickname;     return; } throw new LinkedListException("没有此节点");    }

 代码分析:

1. 需要打一布尔标记,默认该节点不存在
2. 若修改节点,说明链表中肯定有节点,若读者不放心,想增强代码健壮性,可以选择加入一个判断语句if(head.next == null) 若成立则抛异常
3. 循环中的第一个if的目的是用于判断链表是否遍历完,与遍历方法的一样,此条件若成立,说明没有符合条件的节点被更改
4. 循环中的第二个if的目的是用于匹配.匹配成功就退出循环并改标记
5. 最后根据标记修改即可(该方法较为简单,不详细阐述)

 完整代码:

package datastructure.chapter01.linked_list.single_linked_list.instance;// 注意: 代码中的tmep = curpublic class SingleLinkedList {    HeroNode head = new HeroNode();    public HeroNode getHead() { return head;    }    public void finalAdd(HeroNode node) { //头节点的临时引用 var temp = head; while (true) {     if(temp.next == null) {  break;     }     //跳转下一个节点     temp = temp.next; } temp.next = node;    }    public void print() throws LinkedListException { if(head.next == null) {     throw new LinkedListException("链表为空,无法遍历"); } var temp = head.next; while(true) {     if(temp == null){  break;     }     System.out.println(temp);     temp = temp.next; }    }    public void InsertedAddByNo(HeroNode node) throws LinkedListException { boolean flag = false; var temp = head; while(true) {     if(temp.next == null) {  break;     }     if(temp.next.no > node.no){  break;     }else if(temp.next.no == node.no) {  flag = true;  break;     }     temp = temp.next; } if(!flag) {     node.next = temp.next;     temp.next = node;     return; } throw new LinkedListException("该编号已存在,无法添加");    }    public void update(HeroNode newNode) throws LinkedListException { boolean flag = false; var temp = head.next; while(true) {     if(temp == null) {  break;     }     if(temp.no == newNode.no) {  flag = true;  break;     }     temp = temp.next; } if(flag) {     temp.name = newNode.name;     temp.nickname = newNode.nickname;     return; } throw new LinkedListException("没有此节点");    }    public void delete(int no) throws LinkedListException { boolean flag = false; var temp = head; while(true) {     if(temp.next == null) {  break;     }     if(temp.next.no == no) {  flag = true;  break;     }     temp = temp.next; } if(flag) {     temp.next = temp.next.next;     return; } throw new LinkedListException("没有此节点");    }}

面试题:!!!

 查找链表的倒数第k个节点:

    /**     *     * @param headNode 头节点     * @return 有效节点数     *     */    public static int size(HeroNode headNode) { if(headNode.next == null) {     return 0; } int size = 0; for(var cur = headNode.next;cur != null;size++) {     cur = cur.next; } return size;    }/**     *     * @param heroNode 头节点     * @param lastIndex 倒数第lastIndex个节点     * @return 返回该节点     * @throws LinkedListException lastIndex不合理异常     */public static HeroNode findLast(HeroNode heroNode,int lastIndex) throws LinkedListException{ if(heroNode.next == null) {     return null; } int size = size(heroNode); if(lastIndex  size){     throw new LinkedListException("lastIndex不合理"); } int length = size - lastIndex; var cur = heroNode.next; for (int i = 0; i < length ; i++) {     cur = cur.next; } return cur;    }

代码分析:

1. 第一个方法是size()方法,用于计算总节点数,由于和上述的遍历太像,第二个方法中的参数已说明,相信小伙伴都能看懂,博主就不展开阐述了
2. 我们首先要判断链表是否为空,如果是空则没有倒数之说
3. 下一个if的作用是校验传入lastIndex的合理性,如果倒数的数都比总数大或者倒数的数是负数,明显不合理
4. 将总数减去倒数的数值就是到目标节点所需要的次数(如 10 - 1 = 9 而 (1代表倒数))
5. 通过循环找到并返回即可

  单向链表的反转(腾讯):

public static void reverse(HeroNode head) { if(head.next == null || head.next.next == null) {     return; } var cur = head.next; HeroNode next = null; var reverseNode = new HeroNode(); while(cur != null) {     //这段代码很考究,放在最后会导致空指针异常     next = cur.next;     cur.next = reverseNode.next;     reverseNode.next = cur;     cur = next; } head.next = reverseNode.next;    }

 代码分析:

• 我们开始逆转单向链表时,我要要先判断单向链表是否为空,或者单向链表是否只有一个元素,如果是,直接结束方法(一个元素或者没有元素无法逆转)
• 我们要建立两个引用,一个指向当前被取出的节点,一个指向下一个节点目的是:为了不丢失链表​​​​​​​

原因:如果我们只创建一个引用去指向当前被取出的节点,那么当节点被取出后,无法找到原来的下一个节点,即整个链表就丢失了 

• 创建一个一个辅助的头节点,用于交换
• 第二个引用需要放入循环中赋值,因为当我们的cur被取走了之后,那么next就是cur,next此刻需要被重新赋值,所以next需要动态获取,若在循环外获取是静态获取

图解: 

•  通过图解可以得到,循环中的中间两条语句可以完美的嫁接在辅助节点中,即头插法
•  不断通过头插法,可以将最前面的节点放在最后,将最后面的节点放在最前面
•  然后将原来的两个引用进行移动即可
•  最后,将辅助头节点下面的所有节点交还给头节点,逆序完成

  ​​​​​​​逆序输出节点:

 public static void reversePrint(HeroNode head) { if(head.next == null) {     return; } var cur = head.next; var stack = new Stack(); while(cur != null) {     stack.push(cur);     cur = cur.next; } while(stack.size() > 0) {     System.out.println(stack.pop()); }    }

  代码分析:

1. 毫无新奇的前四行(校验是否为空,赋值)
2. 此处用到了栈的知识(先入后出,后入先出),根据这个原理,就可以将他逆序

 问题

用前面的那个先逆序在输出行不行? 可以,但是代码效率低

结论:

        本篇博客主要对单向链表的增删插改遍历进行了讲述,此外,还对面试题:逆序输出,链表逆序,倒数节点等问题一一概述,特别的是,我们最需要掌握的是一下几点:

        删除,插入,反转链表三个大点

        🚇下一站:shell排序和快速排序(排序我会两两推出,共四篇)