Java单链表的应用实例

刺骨的言语ヽ痛彻心扉 2023-10-11 15:49 83阅读 0赞

#### 目录 ####

*  单链表的应用实例
 *   *  直接添加到链表的尾部（不考虑排序）
     *  根据排名将英雄插入到指定位置

--------------------

**链表是有序的列表，它在内存中的实际结构如下**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70]

**小结：**

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

*  **单链表(带头节点)逻辑结构示意图如下**  
    ![在这里插入图片描述][20210703155930776.png]

--------------------

## 单链表的应用实例 ##

*  使用带head头的`单项链表`实现，水浒英雄排行榜管理

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 1]  
 **需求：**

1.  完成对英雄人物的增删改查操作
2.  第一种方法在添加英雄时，直接添加到链表的尾部（不考虑排序）
3.  第二种方式在添加英雄时，根据排名将英雄插入到指定位置（如果有这个排名，则添加失败，并给出提示）

--------------------

### 直接添加到链表的尾部（不考虑排序） ###

**思路分析：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 2]

添加：

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

遍历：

*  通过一个辅助变量帮助遍历整个链表。

**代码实现：**

> 定义节点

//定义 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 + '\'' +
                    '}';
        }
    }

> 定义链表来存放管理我们的英雄

//定义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;
                }
                //如果没有找到最后，将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);
                //将temp后移，一定小心
                temp = temp.next;
            }
        }
    }

> 初始化并测试

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, "鲁智深", "花和尚");
            HeroNode hero5 = new HeroNode(5, "杨志", "青面兽");
            HeroNode hero6 = new HeroNode(6, "林冲", "豹子头");
    
    
            //创建链表
            SingleLinkedList singleLinkedList =new SingleLinkedList();
            singleLinkedList.add(hero1);
            singleLinkedList.add(hero2);
            singleLinkedList.add(hero3);
            singleLinkedList.add(hero4);
            singleLinkedList.add(hero5);
            singleLinkedList.add(hero6);
    
            //显示
            singleLinkedList.list();
    
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 3]

--------------------

### 根据排名将英雄插入到指定位置 ###

**（按照编号的顺序添加）思路分析：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 4]

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

**代码实现：**

> 在 SingleLinkedList 类中重新定义一个增加方法

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;
            }
        }

> 初始化并测试 `注意：这里不按照顺序插入，我们看结果是否会自动排序`

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, "鲁智深", "花和尚");
            HeroNode hero5 = new HeroNode(5, "杨志", "青面兽");
            HeroNode hero6 = new HeroNode(6, "林冲", "豹子头");
    
    
            //创建链表
            SingleLinkedList singleLinkedList =new SingleLinkedList();
            singleLinkedList.addByOrder(hero3);
            singleLinkedList.addByOrder(hero1);
            singleLinkedList.addByOrder(hero2);
            singleLinkedList.addByOrder(hero4);
            singleLinkedList.addByOrder(hero5);
            singleLinkedList.addByOrder(hero6);
    
    
            //显示
            singleLinkedList.list();
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 5]

> 测试 2 加入重复的节点

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, "鲁智深", "花和尚");
            HeroNode hero5 = new HeroNode(5, "杨志", "青面兽");
            HeroNode hero6 = new HeroNode(6, "林冲", "豹子头");
    
    
            //创建链表
            SingleLinkedList singleLinkedList =new SingleLinkedList();
            singleLinkedList.addByOrder(hero3);
            singleLinkedList.addByOrder(hero1);
            singleLinkedList.addByOrder(hero2);
            singleLinkedList.addByOrder(hero4);
            singleLinkedList.addByOrder(hero5);
            singleLinkedList.addByOrder(hero6);
    
            //重复节点
            singleLinkedList.addByOrder(hero1);
    
    
            //显示
            singleLinkedList.list();
    
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 6]

--------------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210703154418457.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ==,size_16,color_FFFFFF,t_70
[20210703155930776.png]: https://img-blog.csdnimg.cn/20210703155930776.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210703160450355.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210704142544856.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210704143648679.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/202107042005391.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20210704201343349.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20210704201504558.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY5MjcwNQ==,size_16,color_FFFFFF,t_70