【数据结构】单向链表的修改和删除

【数据结构】单向链表的修改和删除

单向链表的修改和删除

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

1、单向链表的修改操作

1.1 代码编写

（1）定义HeroNode类，每个HeroNode对象就是一个节点

class HeroNode{public int no;public String name;public String nickname;public HeroNode next;//指向下一个节点//构造器public HeroNode(int no,String name,String nickname){ = no;this.name = name;this.nickname = nickname;}//重写toString方法public String toString(){return "HeroNode[no="+no+",name="+name+",nickname="+nickname+"]";}
}

（2）定义SingleLinkedList来管理英雄
① 先初始化一个头节点，头节点不要动，不存放具体数据

private HeroNode head = new HeroNode(0,"","");

②添加节点到单向链表

  public void addByOrder(HeroNode heroNode){//因为head节点不能动，因此需要新建一个辅助变量temp,temp是位于添加位置的前一个节点HeroNode temp = head;boolean flag = false;//flag标识添加的编号是否存在，默认为falsewhile (true){ == null){//说明temp在链表最后break;}o > ){//位置找到，就在temp后面插入break;}else o == ){//说明希望添加的heroNode的编号已然存在flag = true;//说明编号存在break;}temp = ;//temp后移,遍历当前链表}//判断flag的值if(flag){System.out.printf("准备插入节点的编号%d已经存在了，不能再插入n",);}else//可以插入到链表中，在temp的后面{ = ; = heroNode;}//当退出while循环时，temp就指向了链表最后节点，将temp的next指向新的节点 = heroNode;}

(3)显示链表（遍历）

public void show(){
//判断链表是否为空
 == null){
System.out.println(“链表为空”);
return;
}
//因为head节点不能动，因此需要新建一个辅助变量temp
HeroNode temp = ;
while(true){
//判断是否到链表最后
if(temp == null){
break;
}
//输出节点信息
System.out.println(temp);
//将temp后移
temp = ;
}
}

（4） 修改节点的信息，根据编号no来修改，即编号no不能改

  public void update(HeroNode heroNode){//判断链表是否为空if ( == null){System.out.println("链表为空");return;}//根据编号no找到需要修改的节点//因为head节点不能动，因此需要新建一个辅助变量tempHeroNode temp = ;boolean flag = false;//表示是否找到该节点while(true){if(temp == null){//表示链表已经遍历结束break;} == ){//表示找到了flag = true;break;}temp = ;}//根据flag判断是否找到要修改的节点if(flag){temp.name = heroNode.name;temp.nickname = heroNode.nickname;}else {System.out.printf("没有找到编号%d的节点，不能修改n",);}}

（5）编写主程序，创建节点，添加节点后，显示修改前链表信息，修改节点信息，显示修改后链表信息

public static void main(String[] args) {HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");HeroNode hero3 = new HeroNode(4,"吴用","智多星");HeroNode hero4 = new HeroNode(3,"林冲","豹子头");SingleLikedList singleLikedList = new SingleLikedList();singleLikedList.addByOrder(hero1);singleLikedList.addByOrder(hero2);singleLikedList.addByOrder(hero3);singleLikedList.addByOrder(hero4);System.out.println("====修改前的遍历链表信息===");singleLikedList.show();HeroNode newhero1 = new HeroNode(1,"宋押司","及时雨~");singleLikedList.update(newhero1);System.out.println("====修改后的遍历链表信息===");singleLikedList.show();}

1.2 运行结果

1.3 完整源码

public class SingleLinedListDemo3 {public static void main(String[] args) {HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");HeroNode hero3 = new HeroNode(4,"吴用","智多星");HeroNode hero4 = new HeroNode(3,"林冲","豹子头");SingleLikedList singleLikedList = new SingleLikedList();singleLikedList.addByOrder(hero1);singleLikedList.addByOrder(hero2);singleLikedList.addByOrder(hero3);singleLikedList.addByOrder(hero4);System.out.println("====修改前的遍历链表信息===");singleLikedList.show();HeroNode newhero1 = new HeroNode(1,"宋押司","及时雨~");singleLikedList.update(newhero1);System.out.println("====修改后的遍历链表信息===");singleLikedList.show();}
}
//定义SingleLinkedList来管理英雄
class SingleLikedList {//先初始化一个头节点，头节点不要动，不存放具体数据private HeroNode head = new HeroNode(0,"","");public void addByOrder(HeroNode heroNode){//因为head节点不能动，因此需要新建一个辅助变量temp,temp是位于添加位置的前一个节点HeroNode temp = head;boolean flag = false;//flag标识添加的编号是否存在，默认为falsewhile (true){ == null){//说明temp在链表最后break;}o > ){//位置找到，就在temp后面插入break;}else o == ){//说明希望添加的heroNode的编号已然存在flag = true;//说明编号存在break;}temp = ;//temp后移,遍历当前链表}//判断flag的值if(flag){System.out.printf("准备插入节点的编号%d已经存在了，不能再插入n",);}else//可以插入到链表中，在temp的后面{ = ; = heroNode;}//当退出while循环时，temp就指向了链表最后节点，将temp的next指向新的节点 = heroNode;}//修改节点的信息，根据编号no来修改，即编号no不能改public void update(HeroNode heroNode){//判断链表是否为空if ( == null){System.out.println("链表为空");return;}//根据编号no找到需要修改的节点//因为head节点不能动，因此需要新建一个辅助变量tempHeroNode temp = ;boolean flag = false;//表示是否找到该节点while(true){if(temp == null){//表示链表已经遍历结束break;} == ){//表示找到了flag = true;break;}temp = ;}//根据flag判断是否找到要修改的节点if(flag){temp.name = heroNode.name;temp.nickname = heroNode.nickname;}else {System.out.printf("没有找到编号%d的节点，不能修改n",);}}//显示链表（遍历）public void show(){//判断链表是否为空 == null){System.out.println("链表为空");return;}//因为head节点不能动，因此需要新建一个辅助变量tempHeroNode temp = ;while(true){//判断是否到链表最后if(temp == null){break;}//输出节点信息System.out.println(temp);//将temp后移temp = ;}}
}//定义HeroNode类，每个HeroNode对象就是一个节点
class HeroNode{public int no;public String name;public String nickname;public HeroNode next;//指向下一个节点//构造器public HeroNode(int no,String name,String nickname){ = no;this.name = name;this.nickname = nickname;}//重写toString方法public String toString(){return "HeroNode[no="+no+",name="+name+",nickname="+nickname+"]";}
}

2、单向链表的删除操作

2.1 思路

2.2 代码编写

（1）定义HeroNode类，每个HeroNode对象就是一个节点

class HeroNode{public int no;public String name;public String nickname;public HeroNode next;//指向下一个节点//构造器public HeroNode(int no,String name,String nickname){ = no;this.name = name;this.nickname = nickname;}//重写toString方法public String toString(){return "HeroNode[no="+no+",name="+name+",nickname="+nickname+"]";}
}

（2）定义SingleLinkedList来管理英雄
① 先初始化一个头节点，头节点不要动，不存放具体数据

private HeroNode head = new HeroNode(0,"","");

②添加节点到单向链表

  public void addByOrder(HeroNode heroNode){//因为head节点不能动，因此需要新建一个辅助变量temp,temp是位于添加位置的前一个节点HeroNode temp = head;boolean flag = false;//flag标识添加的编号是否存在，默认为falsewhile (true){ == null){//说明temp在链表最后break;}o > ){//位置找到，就在temp后面插入break;}else o == ){//说明希望添加的heroNode的编号已然存在flag = true;//说明编号存在break;}temp = ;//temp后移,遍历当前链表}//判断flag的值if(flag){System.out.printf("准备插入节点的编号%d已经存在了，不能再插入n",);}else//可以插入到链表中，在temp的后面{ = ; = heroNode;}//当退出while循环时，temp就指向了链表最后节点，将temp的next指向新的节点 = heroNode;}

(3)显示链表（遍历）

public void show(){
//判断链表是否为空
 == null){
System.out.println(“链表为空”);
return;
}
//因为head节点不能动，因此需要新建一个辅助变量temp
HeroNode temp = ;
while(true){
//判断是否到链表最后
if(temp == null){
break;
}
//输出节点信息
System.out.println(temp);
//将temp后移
temp = ;
}
}

（4）删除节点

public void delete(int no) {//判断链表是否为空if ( == null) {System.out.println("链表为空");return;}//因为head节点不能动，因此需要新建一个辅助变量tempHeroNode temp = ;boolean flag = false;//flag标识是否找到需要删除节点的前一个节点，默认为falsewhile (true) {//判断是否到链表最后if ( == null) {break;}if ( == no)//找到了需要删除节点的前一个节点{flag = true;break;}//将temp后移temp = ;}if (flag) { = ;} else {System.out.printf("需要删除节点编号%d不存在", no);}}
}

（5）编写主程序，添加节点后，显示删除前链表信息，删除节点信息，显示删除后链表信息

2.3 运行结果

2.4 完整源码

public class SingleLinedListDemo4 {public static void main(String[] args) {HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");HeroNode hero3 = new HeroNode(4,"吴用","智多星");HeroNode hero4 = new HeroNode(3,"林冲","豹子头");SingleLikedList singleLikedList = new SingleLikedList();singleLikedList.addByOrder(hero1);singleLikedList.addByOrder(hero2);singleLikedList.addByOrder(hero3);singleLikedList.addByOrder(hero4);System.out.println("====删除前的遍历链表信息===");singleLikedList.show();singleLikedList.delete(2);System.out.println("====删除后的遍历链表信息===");singleLikedList.show();}
}
//定义SingleLinkedList来管理英雄
class SingleLikedList {//先初始化一个头节点，头节点不要动，不存放具体数据private HeroNode head = new HeroNode(0, "", "");public void addByOrder(HeroNode heroNode) {//因为head节点不能动，因此需要新建一个辅助变量temp,temp是位于添加位置的前一个节点HeroNode temp = head;boolean flag = false;//flag标识添加的编号是否存在，默认为falsewhile (true) {if ( == null) {//说明temp在链表最后break;}if ( > ) {//位置找到，就在temp后面插入break;} else if ( == ) {//说明希望添加的heroNode的编号已然存在flag = true;//说明编号存在break;}temp = ;//temp后移,遍历当前链表}//判断flag的值if (flag) {System.out.printf("准备插入节点的编号%d已经存在了，不能再插入n", );} else//可以插入到链表中，在temp的后面{ = ; = heroNode;}//当退出while循环时，temp就指向了链表最后节点，将temp的next指向新的节点 = heroNode;}//显示链表（遍历）public void show() {//判断链表是否为空if ( == null) {System.out.println("链表为空");return;}//因为head节点不能动，因此需要新建一个辅助变量tempHeroNode temp = ;while (true) {//判断是否到链表最后if (temp == null) {break;}//输出节点信息System.out.println(temp);//将temp后移temp = ;}}//删除节点public void delete(int no) {//判断链表是否为空if ( == null) {System.out.println("链表为空");return;}//因为head节点不能动，因此需要新建一个辅助变量tempHeroNode temp = ;boolean flag = false;//flag标识是否找到需要删除节点的前一个节点，默认为falsewhile (true) {//判断是否到链表最后if ( == null) {break;}if ( == no)//找到了需要删除节点的前一个节点{flag = true;break;}//将temp后移temp = ;}if (flag) { = ;} else {System.out.printf("需要删除节点编号%d不存在", 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){ = no;this.name = name;this.nickname = nickname;}//重写toString方法public String toString(){return "HeroNode[no="+no+",name="+name+",nickname="+nickname+"]";}
}