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

单链表的增删改查

一、链表（Linked List）

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

二、单链表的增删改查

1. 增

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

    public void add(HeroNode heroNode) {
//        因为head节点不能动，因此我们需要一个辅助遍历tempHeroNode 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标志添加的编号是否存在，默认为falseboolean 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;}}

全部代码

代码结构

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节点不能动，因此我们需要一个辅助遍历tempHeroNode 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标志添加的编号是否存在，默认为falseboolean 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@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +", nickname='" + nickname + "'" +'}';}
}

运行结果