带头节点单链表（Linked List）底层增删改查原理

蔚落 2022-10-12 04:07 83阅读 0赞

### 文章目录 ###

*   *  一。简介
     *  二。应用实例
     *   *  1.初始化英雄节点以及单链表
         *  2.无序添加
         *  3.有序添加
         *  4.修改
         *  5.删除
     *  三。完整代码

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

## 一。简介 ##

链表是有序的列表，它在内存中的存储方式如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70]

*  链表是以节点的方式来存储，是链式存储
 *  每个节点包含data域，next域：指向下一个节点，当某个节点的`next==null`时表示该节点为最后一个节点
 *  链表的各个节点不一定是连续存储，而是通过类似于指针的方式，让本身的next域指向下一个节点，从而做到链表读取
 *  链表分带头节点的链表和没有带头节点的链表，根据实际的需求来确定

单链表逻辑结构示意图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 1]

## 二。应用实例 ##

使用带head头的单向链表实现 –水浒英雄排行榜管理  
![在这里插入图片描述][20210703101535104.png]

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

### 1.初始化英雄节点以及单链表 ###

/** * @author Keson * @version 1.0 * @description: TODO * @date 2021/7/3 7:10 */
    public class SingleLinkedListDemo { 
    
        //先定义一个英雄的节点类
        class HeroNode{ 
            private int id;//唯一id编号
            private String name;//真实姓名
            private String nickName;//昵称
            private HeroNode next;//模拟单链表的next域：指向下一个节点
    
            //构造器
            public HeroNode(int id,String name,String nickName){ 
                this.id=id;
                this.name=name;
                this.nickName=nickName;
            }
            
        }
    
        class SingleLinkedList{ 
            //先初始化一个头节点, 头节点不要动, 不存放具体的数据
            private HeroNode head = new HeroNode(0, "", "");
    
            //无序添加方式(不考虑编号顺序时)
           
            //有序添加方式(考虑编号顺序时)
    
            //修改
    
            //删除
    
            //显示
        }
    }

### 2.无序添加 ###

实现思路：

1.  先创建一个head 头节点， 作用就是表示单链表的头
2.  后面我们每添加一个节点，就直接加入到链表的最后
3.  通过一个辅助变量遍历，帮助遍历整个链表  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 2]

**SingleLinkedList（添加无序插入以及遍历显示方法）：**

//定义一个单链表存储英雄节点信息
        static class SingleLinkedList{ 
            //先初始化一个头节点, 头节点不要动, 不存放具体的数据
            private HeroNode head = new HeroNode(0, "", "");
    
            //无序添加方式(不考虑编号顺序时)
            //1. 找到当前链表的最后节点
            //2. 将最后这个节点的next指向新的节点
            public void add(HeroNode heroNode){ 
                //因为头节点是不能动的，所以需要初始化一个辅助变量来实现遍历（类似于指针）
                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.print("该链表为空！");
                }
                //因为头节点是不能动的，所以需要初始化一个辅助变量来实现遍历（类似于指针）
                HeroNode temp = head.next;
                while(true){ 
                    if(temp == null){ 
                        break;
                    }
                    //输出节点的信息
                    System.out.println(temp);
                    //指针后移
                    temp = temp.next;
                }
            }
        }

**HeroNode（重写toString方法）：**

@Override
            public String toString() { 
                return "HeroNode{" +
                        "id=" + id +
                        ", name='" + name + '\'' +
                        ", nickName='" + nickName + '\'' +
                        '}';
            }

**主程序入口：**

**程序运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 3]

### 3.有序添加 ###

实现思路：

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 4]  
**SingleLinkedList（添加有序插入）：**

//有序添加方式(考虑编号顺序时)
    public void addByOrder(HeroNode heroNode){ 
        //因为头节点是不能动的，所以需要初始化一个辅助变量来实现遍历（类似于指针）
        HeroNode temp = head;
        boolean flag = false;//判断编号是否存在标志
        while (true) { 
            //如果链表为空
            if(temp.next == null){ 
                break;
            }
            //找到插入位置
            if(temp.next.id > heroNode.id){ 
                break;
            }else if(temp.next.id == heroNode.id){ 
                flag = true; //说明编号存在
                break;
            }
            //继续进行遍历
            temp = temp.next;
        }
    
        //判断flag 的值
        if(flag) {  //不能添加，说明编号存在
            System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.id);
        } else { 
            //插入到链表中, temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

**主程序入口：**

**程序运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 5]

### 4.修改 ###

实现思路：

根据编号找到需要修改的节点, 修改该节点信息即可。

**SingleLinkedList（添加更新操作）：**

//修改
    public void update(HeroNode heroNode){ 
        //因为头节点是不能动的，所以需要初始化一个辅助变量来实现遍历（类似于指针）
        HeroNode temp = head.next;
        boolean flag = false;//判断编号是否存在标志
        while(true){ 
            //如果链表为空
            if(temp == null){ 
                System.out.print("该链表为空！");
                break;
            }
            //如果找到需要修改的节点
            if(temp.id == heroNode.id){ 
                flag = true;
                break;
            }
            //继续进行遍历
            temp = temp.next;
        }
    
        //修改属性
        if(flag){ 
            temp.name = heroNode.name;
            temp.nickName = heroNode.nickName;
        }else {  //没有找到
            System.out.printf("没有找到 编号 %d 的节点，不能修改\n", heroNode.id);
        }
    }

**主程序入口：**

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

**程序运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 6]

### 5.删除 ###

实现思路：

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 7]  
**SingleLinkedList（添加删除操作）：**

//删除
    public void remove(int id){ 
        //因为头节点是不能动的，所以需要初始化一个辅助变量来实现遍历（类似于指针）
        HeroNode temp = head;
        boolean flag = false;//判断是否找到需要删除的节点标志
        while(true){ 
            //如果链表为空
            if(temp.next == null){ 
                System.out.print("该链表为空！");
                break;
            }
            //如果找到需要删除的节点
            if(temp.next.id == id){ 
                flag = true;
                break;
            }
            //继续进行遍历
            temp = temp.next;
        }
        //判断flag
        if(flag){ 
            temp.next = temp.next.next;
        }else { 
            System.out.printf("要删除的 %d 节点不存在\n", id);
        }
    }

**主程序入口：**

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.remove(1);
            singleLinkedList.remove(4);
            System.out.println("删除后的链表情况~~");
            singleLinkedList.list();
        }

**程序运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 8]

## 三。完整代码 ##

/** * @author Keson * @version 1.0 * @description: TODO * @date 2021/7/3 7:10 */
    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.remove(1);
            singleLinkedList.remove(4);
            System.out.println("删除后的链表情况~~");
            singleLinkedList.list();
        }
    
        //先定义一个英雄的节点类
        static class HeroNode{ 
            private int id;//唯一id编号
            private String name;//真实姓名
            private String nickName;//昵称
            private HeroNode next;//模拟单链表的next域：指向下一个节点
    
            //构造器
            public HeroNode(int id,String name,String nickName){ 
                this.id=id;
                this.name=name;
                this.nickName=nickName;
            }
    
    
            @Override
            public String toString() { 
                return "HeroNode{" +
                        "id=" + id +
                        ", name='" + name + '\'' +
                        ", nickName='" + nickName + '\'' +
                        '}';
            }
        }
    
        //定义一个单链表存储英雄节点信息
        static class SingleLinkedList{ 
            //先初始化一个头节点, 头节点不要动, 不存放具体的数据
            private HeroNode head = new HeroNode(0, "", "");
    
            //无序添加方式(不考虑编号顺序时)
            //1. 找到当前链表的最后节点
            //2. 将最后这个节点的next指向新的节点
            public void add(HeroNode heroNode){ 
                //因为头节点是不能动的，所以需要初始化一个辅助变量来实现遍历（类似于指针）
                HeroNode temp = head;
                //遍历链表，找到最后
                while(true) { 
                    //找到链表的最后（空链表的情况）
                    if(temp.next == null) { 
                        break;
                    }
                    //如果没有找到最后, 将temp后移
                    temp = temp.next;
                }
                //当退出while循环时，temp就指向了链表的最后
                //将最后这个节点的next指向新的节点
                temp.next = heroNode;
            }
    
            //有序添加方式(考虑编号顺序时)
            public void addByOrder(HeroNode heroNode){ 
                //因为头节点是不能动的，所以需要初始化一个辅助变量来实现遍历（类似于指针）
                HeroNode temp = head;
                boolean flag = false;//判断编号是否存在标志
                while (true) { 
                    //如果链表为空
                    if(temp.next == null){ 
                        break;
                    }
                    //找到插入位置
                    if(temp.next.id > heroNode.id){ 
                        break;
                    }else if(temp.next.id == heroNode.id){ 
                        flag = true; //说明编号存在
                        break;
                    }
                    //继续进行遍历
                    temp = temp.next;
                }
    
                //判断flag 的值
                if(flag) {  //不能添加，说明编号存在
                    System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.id);
                } else { 
                    //插入到链表中, temp的后面
                    heroNode.next = temp.next;
                    temp.next = heroNode;
                }
            }
    
    
            //修改
            public void update(HeroNode heroNode){ 
                //因为头节点是不能动的，所以需要初始化一个辅助变量来实现遍历（类似于指针）
                HeroNode temp = head.next;
                boolean flag = false;//判断编号是否存在标志
                while(true){ 
                    //如果链表为空
                    if(temp == null){ 
                        System.out.print("该链表为空！");
                        break;
                    }
                    //如果找到需要修改的节点
                    if(temp.id == heroNode.id){ 
                        flag = true;
                        break;
                    }
                    //继续进行遍历
                    temp = temp.next;
                }
    
                //修改属性
                if(flag){ 
                    temp.name = heroNode.name;
                    temp.nickName = heroNode.nickName;
                }else {  //没有找到
                    System.out.printf("没有找到 编号 %d 的节点，不能修改\n", heroNode.id);
                }
            }
    
            //删除
            public void remove(int id){ 
                //因为头节点是不能动的，所以需要初始化一个辅助变量来实现遍历（类似于指针）
                HeroNode temp = head;
                boolean flag = false;//判断是否找到需要删除的节点标志
                while(true){ 
                    //如果链表为空
                    if(temp.next == null){ 
                        System.out.print("该链表为空！");
                        break;
                    }
                    //如果找到需要删除的节点
                    if(temp.next.id == id){ 
                        flag = true;
                        break;
                    }
                    //继续进行遍历
                    temp = temp.next;
                }
                //判断flag
                if(flag){ 
                    temp.next = temp.next.next;
                }else { 
                    System.out.printf("要删除的 %d 节点不存在\n", id);
                }
            }
    
            //遍历链表
            public void list(){ 
                //判断链表是否为空
                if(head.next == null){ 
                    System.out.print("该链表为空！");
                }
                //因为头节点是不能动的，所以需要初始化一个辅助变量来实现遍历（类似于指针）
                HeroNode temp = head.next;
                while(true){ 
                    if(temp == null){ 
                        break;
                    }
                    //输出节点的信息
                    System.out.println(temp);
                    //指针后移
                    temp = temp.next;
                }
            }
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70]: /images/20221005/fdb98d9008ce4057adb371d4ad919aa6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 1]: /images/20221005/649b55ee5c2244ad83708b6060758ab8.png
[20210703101535104.png]: /images/20221005/362f8a0e01114befb0137853d259d984.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 2]: /images/20221005/354434e7d7dd40f484351f2b4fdb7534.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 3]: /images/20221005/f81df31fc0b3412bbca9e1010ea3877c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 4]: /images/20221005/b4095daa6b6a494493d31658149a3e4d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 5]: /images/20221005/8444d61c005a404097caab683992b2b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 6]: /images/20221005/55ad721c179d48f08caf0d9ed3b3ffc4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 7]: /images/20221005/d70df463b27c4c27b1ee98ac22e6468c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70 8]: /images/20221005/634390e3e02c4c129e0ef0bcf96c5875.png