2023-09-22
原文作者:李林超 原文地址: https://www.lilinchao.com/archives/479.html

一、链表(Linked List)介绍

链表是有序的列表,但是它在内存中是存储如下:

202309222128391251.png

上图总结

(1)链表是以节点的方式来存储,是链式存储

(2)每个节点包含data域,next域:指向下一个节点。

(3)如图:发现链表的各个节点不一定是连续存储

(4)链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定

单链表(带头节点)逻辑结构示意图如下

202309222128426852.png

二、单链表的应用实例

使用带head头的单向链表实现 水浒英雄排行榜管理完成对英雄人物的增删改查操作。

(1)第一种方法在添加英雄时,直接添加到链表的尾部

思路分析示意图:

202309222128433493.png

添加(创建)思路:

1.先创建一个head头节点,作用就是表示单链表的头

2.后面我们每添加一个节点,就直接加入到链表的最后

遍历:

1.通过一个辅助变量遍历,帮助遍历整个链表

(2)第二种方式在添加英雄时,根据排名将英雄插入到指定位置(如果有这个排名,则添加失败,并给出提示)

思路的分析示意图:

202309222128439944.png

需要按照编号的顺序添加思路:

1.首先找到新添加的节点的位置,是通过辅助的变量(指针),通过遍历来搞定

2.新的节点next=temp.next

3.将temp.next=新的节点

(3)修改节点功能

思路:

  1. 先找到该节点,通过遍历 > 2. tem.name=newHeroNode.name; temp.nickname=newHeroNode.nickname

(4)删除节点

思路分析的示意图:

202309222128448065.png

从单链表中删除一个节点的思路:

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

代码

    public class SingleLinkedListDemo {
        public static void main(String[] args) {
            //先创建一个节点
            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(hero4);
            singleLinkedList.add(hero2);
            singleLinkedList.add(hero3);*/
    
            //加入按照编号的顺序
            singleLinkedList.addByOrder(hero1);
            singleLinkedList.addByOrder(hero4);
            singleLinkedList.addByOrder(hero2);
            singleLinkedList.addByOrder(hero3);
    
            //显示
            singleLinkedList.list();
    
            //测试修改节点
            HeroNode newHeroNode = new HeroNode(2,"小卢","玉麒麟!!");
            singleLinkedList.update(newHeroNode);
    
            System.out.println("修改后的链表情况~~");
            singleLinkedList.list();
    
            //删除一个节点
            singleLinkedList.del(1);
            singleLinkedList.del(4);
            System.out.println("删除后的链表情况~~");
            singleLinkedList.list();
        }
    }
    
    //定义SingleLinkedList管理我们的英雄
    class SingleLinkedList{
        //先初始化一个头节点,头节点不要动,不存放具体的数据
        private HeroNode head = new HeroNode(0,"","");
    
        //添加节点到单向链表
        //思路:当不考虑编号顺序时
        //1.找到 当前链表的最后节点
        //2.将最后这个节点的next指向新的节点
        public void add(HeroNode heroNode){
            //因为head节点不能动,因此我们需要一个辅助遍历temp
            HeroNode temp = head;
            //遍历链表,找到最后
            while(true){
                //找到链表的最后
                if(temp.next == null){
                    break;
                }
                //如果没有找到最后,将tenp后移
                temp = temp.next;
            }
            //当退出while循环的时候,temp就指向了链表的最后
            //将最后这个节点的next指向新的节点
            temp.next = heroNode;
        }
    
        //第二种方式在添加英雄时,根据排名将英雄插入到指定位置
        //如果有这个排名,则添加失败,并给出提示
        public void addByOrder(HeroNode heroNode){
            //因为头节点不能动,因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
            //因为单链表,因为我们找的temp是位于添加位置的前一个节点,否则插入不了
            HeroNode temp = head;
            boolean flag = false;//flag标志添加的编号是否存在,默认为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;//后移,遍历当前链表
            }
            //判断flag的值
            if(flag){//不能添加,说明编号存在
                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.next == null){
                System.out.println("链表为空!");
                return;
            }
            //找到需要修改的节点,根据No编号
            //定义一个辅助变量
            HeroNode temp = head.next;
            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的节点,不能修改\n",newHeroNode.no);
            }
        }
        //删除节点
        //1.head不能动,因此我们需要一个temp辅助节点找到待删除节点的前一个节点
        //2.说明我们在比较时,是temp.next.no和 需要删除的节点的no比较
        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后移,遍历
            }
            //判断flag
            if(flag){//找到  -- 可以删除
                temp.next=temp.next.next;
            }else{
                System.out.printf("要删除的%d节点不存在\n",no);
            }
        }
        //显示链表【遍历】
        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);
                //将temp后移,一定小心
                temp = temp.next;
            }
        }
    }
    
    //定义HeroNode,每个HeroNode对象就是一个节点
    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;
        }
        //为了显示方法,我们重新toString
        @Override
        public String toString(){
            return "HeroNode [no="+no+",name="+name+",nickname="+nickname+"]";
        }
    }
阅读全文