数据结构----单链表增删改查

分手后的思念是犯贱 2022-10-28 03:48 216阅读 0赞

## 单链表的增删改查 ##

### 一、链表（Linked List） ###

*  链表是有序列表，以节点的方式来存储的，链式存储；
 *  每个节点包含data域，next域：指向下一节点；
 *  链表的各个节点不一定是连续存储；
 *  链表分为带头节点的链表和不带头结点的链表，根据实际需求来确定。

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

### 二、单链表的增删改查 ###

###### 1. 增 ######

*  往单链表中添加内容（按照输入顺序添加—普通添加）

public void add(HeroNode heroNode) { 
    // 因为head节点不能动，因此我们需要一个辅助遍历temp
            HeroNode temp = head;
    // 遍历链表，找到最后
            while (temp.next != null) { 
                // 如果没有找到最后，将temp 后移
                temp = temp.next;
            }
    // 当退出while循环时，temp就指向了链表的最后
    // 将最后这个节点的next指向新的节点
            temp.next = heroNode;
        }

**- 往单链表中添加内容（按照排名添加，即使输入是乱序的----有序添加）**

public void addByOrder(HeroNode heroNode) { 
    
    // 因为头节点不能动，仍然通过一个辅助指针来帮助找到添加的位置
    // 因为是单链表，因为找的temp是位于添加位置的前一个节点，否则插入不了
            HeroNode temp = head;
    // flag标志添加的编号是否存在，默认为false
            boolean flag = false;
            while (true) { 
                if (temp.next == null) { 
                    break;
                }
    // 位置找到了，就在temp的后面插入
                if (temp.next.no > heroNode.no) { 
                    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;
            }
        }

*  修改单链表中的内容（编号不能动，修改编号对应的内容）

###### 2. 删 ######

*  从单链表中删除一个节点的思路：
    
     *  1.  找到待删除节点前一个节点temp
        2.  temp.next = temp.next.next
        3.  被删除的节点将不会有其他的引用指向，会被垃圾回收机制回收

// 删除节点的方法，head节点不能动
        public void deleteNode(int no) { 
            HeroNode temp = head;
    // 标识是否找到待删除节点
            boolean flag = false;
            while (true) { 
                if (temp.next == null) { 
                    System.out.println("已经到了链表最后了");
                    break;
                }
                if (temp.next.no == no) { 
    // 找到了待删除的节点的前一个节点
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if (flag) { 
                temp.next = temp.next.next;
            } else { 
                System.out.printf("没有找到要删除编号 %d 的节点\n", no);
            }
        }

###### 3. 改 ######

public void updateInfo(HeroNode newHeroNode) { 
    // 定义辅助变量
            HeroNode temp = head.next;
            boolean flag = false;
            if (temp == null) { 
                System.out.println("链表为空");
                return;
            }
            while (true) { 
                if (temp == null) { 
    // 已经遍历到了链表的最后一个
                    break;
                }
                if (temp.no == newHeroNode.no) { 
    // 已经找到了
                    flag = true;
                    break;
                }
    // 遍历链表
                temp = temp.next;
            }
    
            if (flag) { 
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
            } else { 
                System.out.printf("没有找到编号 %d 的链表，不能修改\n", newHeroNode.no);
            }
        }

###### 4. 查 ######

查看链表内容

// 显示链表[遍历]
        public void list() { 
    // 判断链表是否为空
            if (head.next == null) { 
                System.out.println("链表为空");
                return;
            }
    // 因为头节点不能动，因此需要一个辅助变量来遍历
            HeroNode temp = head.next;
            while (temp != null) { 
    // 输出节点信息
                System.out.println(temp);
    // 将temp后移，一定要后移，因为是死循环
                temp = temp.next;
            }
        }

#### 全部代码 ####

**代码结构**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA0NDE1_size_16_color_FFFFFF_t_70]

package com.starking.linkedlist;
    
    /** * @author Manix */
    
    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, "运20", "胖妞");
    
            HeroNode hero5 = new HeroNode(3, "嫦娥6", "玉兔");
    
    // 创建链表
            SingLinkedList singLinkedList = new SingLinkedList();
    // 添加英雄
            singLinkedList.addByOrder(hero1);
            singLinkedList.addByOrder(hero3);
            singLinkedList.addByOrder(hero2);
            singLinkedList.addByOrder(hero4);
    
            System.out.println("修改之前的链表");
            singLinkedList.list();
    
    // 修改3号英雄的名称和昵称
            singLinkedList.updateInfo(hero5);
            System.out.println("修改之后的链表");
            singLinkedList.list();
    
    // 删除一个节点测试
            singLinkedList.deleteNode(1);
            System.out.println("删除之后的链表");
            singLinkedList.list();
    
        }
    }
    
    
    //定义SingleLinkedList管理我们的英雄
    class SingLinkedList { 
    // 初始化头节点，不存放具体数据
        HeroNode head = new HeroNode(0, "", "");
    
    // 添加节点到单向链表
    // 思路：当不考虑编号顺序时
    // 1. 找到当前链表的最后节点
    // 2. 将最后这个节点的next指向新的节点
    
        public void add(HeroNode heroNode) { 
    // 因为head节点不能动，因此我们需要一个辅助遍历temp
            HeroNode temp = head;
    // 遍历链表，找到最后
            while (temp.next != null) { 
                // 如果没有找到最后，将temp 后移
                temp = temp.next;
            }
    // 当退出while循环时，temp就指向了链表的最后
    // 将最后这个节点的next指向新的节点
            temp.next = heroNode;
        }
    
    
        // 更新编号对应的名字和昵称的方法，编号不能修改
        public void updateInfo(HeroNode newHeroNode) { 
    // 定义辅助变量
            HeroNode temp = head.next;
            boolean flag = false;
            if (temp == null) { 
                System.out.println("链表为空");
                return;
            }
            while (true) { 
                if (temp == null) { 
    // 已经遍历到了链表的最后一个
                    break;
                }
                if (temp.no == newHeroNode.no) { 
    // 已经找到了
                    flag = true;
                    break;
                }
    // 遍历链表
                temp = temp.next;
            }
    
            if (flag) { 
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
            } else { 
                System.out.printf("没有找到编号 %d 的链表，不能修改\n", newHeroNode.no);
            }
        }
    
    
        // 第二种添加英雄的方法，根据英雄排名插入到指定位置
    // 如果有这个排名，则添加失败，并给出提示
        public void addByOrder(HeroNode heroNode) { 
    
    // 因为头节点不能动，仍然通过一个辅助指针来帮助找到添加的位置
    // 因为是单链表，因为找的temp是位于添加位置的前一个节点，否则插入不了
            HeroNode temp = head;
    // flag标志添加的编号是否存在，默认为false
            boolean flag = false;
            while (true) { 
                if (temp.next == null) { 
                    break;
                }
    // 位置找到了，就在temp的后面插入
                if (temp.next.no > heroNode.no) { 
                    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 void list() { 
    // 判断链表是否为空
            if (head.next == null) { 
                System.out.println("链表为空");
                return;
            }
    // 因为头节点不能动，因此需要一个辅助变量来遍历
            HeroNode temp = head.next;
            while (temp != null) { 
    // 输出节点信息
                System.out.println(temp);
    // 将temp后移，一定要后移，因为是死循环
                temp = temp.next;
            }
        }
    
    
        // 删除节点的方法，head节点不能动
        public void deleteNode(int no) { 
            HeroNode temp = head;
    // 标识是否找到待删除节点
            boolean flag = false;
            while (true) { 
                if (temp.next == null) { 
                    System.out.println("已经到了链表最后了");
                    break;
                }
                if (temp.next.no == no) { 
    // 找到了待删除的节点的前一个节点
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if (flag) { 
                temp.next = temp.next.next;
            } else { 
                System.out.printf("没有找到要删除编号 %d 的节点\n", no);
            }
        }
    
    }
    
    
    //定义一个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 + "'" +
                    '}';
        }
    }

##### 运行结果 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA0NDE1_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA0NDE1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/7d9b0038875241d98c67ed0de76029b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA0NDE1_size_16_color_FFFFFF_t_70]: /images/20221024/a87566ee8c0746f0abfefc5a1372a870.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA0NDE1_size_16_color_FFFFFF_t_70 1]: /images/20221024/95bb31a2bc6e4924822682e397a8aaba.png