文章目录

• 开篇
• 一、单链表的应用实例
• • • 通过插入顺序实现链表存储代码实现：
    • 按照编号的顺序添加
    • 单链表节点的修改
    • 单链表节点的删除
• 二、面试题分享：
• • • 求单链表有效节点的个数：
    • 查找单链表中倒数第K个结点
    • 单链表翻转
    • 单链表从尾到头逆序打印

开篇

链表（Linked LIst）是一个有序的列表，在内存中存储如下：

1. 链表是节点的方式存储的，是链式存储；
2. 每个节点包含data域，next域（指向下一个节点）
3. 发现链表的各个节点不一定是连续存放
4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

一、单链表的应用实例

单链表创建示意图：

添加（创建）：

1. 先创建一个head头结点，作用就是表示单链表的头
2. 后面我们每添加一个节点，就直接加入到链表的最后，遍历；

遍历：
通过一个辅助遍历，帮助遍历整个链表

通过插入顺序实现链表存储代码实现：

public class SingleLinkedListDemo {    public static void main(String[] args) { System.out.println("单链表测试~~~~~"); HeroNode hero1 = new HeroNode(1, "孙悟空", "孙行者"); HeroNode hero2 = new HeroNode(2, "猪八戒", "猪悟能"); HeroNode hero3 = new HeroNode(3, "沙师弟", "沙悟净"); HeroNode hero4 = new HeroNode(4, "唐僧", "唐三藏"); //创建一个链表 SingleLinkedList singleLinkedList = new SingleLinkedList(); singleLinkedList.add(hero1); singleLinkedList.add(hero2); singleLinkedList.add(hero3); singleLinkedList.add(hero4); //显示单链表 singleLinkedList.list();    }}//定义一个SingleLinkedList管理我们的英雄class SingleLinkedList{    //先初始化一个头结点,不发生变化    private HeroNode head=new HeroNode(0,"","");    //添加节点到单向链表//    思路：找到当前链表的最后节点，将最后节点的next指向新的节点    public void add(HeroNode heroNode){ //因为头节点不能动，因此我们需要一个辅助遍历temp HeroNode temp = head; //遍历链表，找到最后 while (true){     //  找到链表的最后     if (temp.next==null){  break;     }     //如果没有找到，将temp后移     temp=temp.next; } //当退出while循环的时候，temp就指向了链表的最后 //将最后这个节点的next 指向新的节点 temp.next=heroNode;    }    //显示链表【遍历】    public  void list(){ //先判断了链表是否为空 if (head.next==null){     System.out.println("链表为空");     return; } //如果链表不为空，首先定义一个辅助节点 HeroNode temp = head.next; while (true){     //判断是否到链表的最后     if (temp==null){  break;     }     //输出节点信息     System.out.println(temp);     //将next后移     temp=temp.next; }    }}//先定义一个HeroNode，每一个HeroNode对象就是一个节点class HeroNode{    public int no;    public String name;    public  String nickname;    public HeroNode next;//指向下一个节点    //构造器    public HeroNode(int hNo,String hName,String hNickname) { this.no=hNo; this.name=hName; this.nickname=hNickname;    }    //为了显示方便，重写头String方法    @Override    public String toString() { return "HeroNode{" +  "no=" + no +  ", name='" + name + '\'' +  ", nickname='" + nickname + '\'' +//  ", next=" + next +  '}';    }}

运行结果：

按照编号的顺序添加

1. 首先找到新添加的节点的位置，是通过辅助变量（指针），通过遍历来搞定；
2. 新的节点.next=temp.next
3. 将temp.next=新的节点

代码实现：
给原来的单链表新建一个addByOrder的方法：

//按照排名添加节点    public void addByOrder(HeroNode heroNode) { //因为头结点不能动，因此仍然需要一个辅助指针来帮助找到添加的位置 //因为单链表，我们找的temp是位于添加位置的前一个节点，否则插入不了 HeroNode temp = head; boolean flag = false;//标志添加的节点是否存在，默认为false while (true) {     if (temp.next == null) {//说明temp已经在链表的最后  break;//     }     if (temp.next.no > heroNode.no) {//位置找到，就在temp的后面插入  break;     } else if (temp.next.no == heroNode.no) {//说明希望添加的heroNode的编号已经存在  flag = true;  break;     }     temp = temp.next;//后移，遍历当前列表 } if (flag = true) {     System.out.printf("准备插入的节点编号 %d已经存在了，不能加入\n", heroNode.no); } else {     //插入到链表中，temp的后面     heroNode.next = temp.next;     temp.next = heroNode; }    }

运行结果：

单链表节点的修改

代码实现方式：

//修改节点的信息，根据no编号来修改，即no编号不能改变    //说明    //1.根据newHeroNode的no来修改即可    public void  update(HeroNode newHeroNode){ //判断是否为空 if (head==null){     System.out.println("链表为空");     return; } //找到需要修改的节点，根据no编号 //定义一个辅助变量 HeroNode temp=head; boolean flag=false;//表示是否找到该节点 while (true){     if (temp==null){//表示已经遍历完链表  break;     }     if (temp.no==newHeroNode.no){//表示找到该节点  flag=true;  break;     }      temp=temp.next; } //根据flag判断是否找打要修改的节点 if (flag) {     temp.name= newHeroNode.name;     temp.nickname= newHeroNode.nickname; }else{     //说明没有找到要修改的节点     System.out.printf("没有找到编号%d 的节点，不能进行修改",newHeroNode.no); }    }

执行结果:

单链表节点的删除

1. 我们需要先找到这个需要删除节点的前一个节点temp
2. temp.next=temp.next.next
3. 被删除的节点 ，将不会有其它的引用，会被垃圾回收机制回收

代码实现：

//删除节点    public void del(int no){ HeroNode temp=head; boolean flag=false;//标志是否找到待删除节点的前一个 while (true){     if (temp.next==null){//表示已经到链表的最后  break;     }     if (temp.next.no==no){//找到待删除节点的前一个节点temp  flag=true;  break;     }     temp=temp.next;//temp后移，遍历 } if (flag){//找到     //删除     temp.next=temp.next.next; }else{     System.out.printf("没有找到要删除的%d 的节点，不能进行修改",no); }

删除第一个节点，运行结果如下：

二、面试题分享：

求单链表有效节点的个数：

思路：从该单链表头结点的下一个节点开始遍历，每遍历一次记录一次，直到下一个指向为空；

//获取单链表节点的个数（如果是带头结点的链表，需要不统计头节点）    public static int getLength(HeroNode head){ if (head.next==null){//如果为空链表     return 0; } int length=0; //定义一个辅助的变量 HeroNode cur=head.next; while (cur != null){     length++;     cur=cur.next;//遍历 } return  length;    }

查找单链表中倒数第K个结点

思路：
1.编写一个方法，接受head节点，同时接受一个index（表示倒数第index节点）
2.先把链表从头到尾遍历，得到链表的总长度
3.得到size之后，我们从链表的第一个开始遍历（size-index）个。就可以得到倒数第k个节点的值
4.如果找到了，则返回该节点，否则返回null

public  static HeroNode findLastIndexNode(HeroNode head,int index){ //判断如果链表为空，则返回null if (head.next==null){     return null; } //第一个遍历得到链表的长度（节点个数） int size=getLength(head); //第二次遍历 size-index位置，就是我们倒数的第K个节点 //先做一个index的校验 if (index<=0||index>size){     return null; } //定义一个辅助变量,使用for循环定位到倒数的index HeroNode cur=head.next; for (int i = 0; i <size-index; i++) {     cur=cur.next; } return cur;    }

单链表翻转

 public static void reversetList(HeroNode head){ //如果当前链表为空，或者只有一个节点，则无须翻转，直接返回 if (head.next==null||head.next.next==null){     return; } //定义一个辅助的指针，帮助我们遍历原来的链表 HeroNode cur=head.next; HeroNode next=null;//指向当前节点[cur]的下一节点 HeroNode reverseHead=new HeroNode(0,"",""); //遍历原来的链表 //每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端 while (cur != null){     next=cur.next;//先暂时保存当前节点的下一节点，后面需要使用     cur.next=reverseHead.next;//将cur的下一节点指向新链表的最前端     reverseHead.next=cur;//将cur连接到新的链表上     cur=next;//让cur后移 } //将head.next指向reverseHead.next。实现单链表的翻转 head.next=reverseHead.next;    }

单链表从尾到头逆序打印

可以使用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果；
代码实现：

//将单链表逆序进行输出：    public static void  reversePrint(HeroNode head){ if (head.next==null){     return; } //创建一个栈，将各个节点压入栈中 Stack<HeroNode> stack=new Stack<>(); HeroNode cur=head.next; while (cur!=null){     stack.push(cur);     cur=cur.next;//cur后移，这样就可以压入下一个节点 } //将栈中的节点进行打印，pop出值 while (stack.size()>0){     System.out.println(stack.pop());//stack的特点是先进后出 }

如果感觉内容写的还不错的话，一键三连不迷路！！！！
后面将会更新更多学习内容，一起学习吧！！！！！！

开发者涨薪指南 48位大咖的思考法则、工作方式、逻辑体系NICE