数据结构4-单链表的删除修改和查找

1.单链表按照顺序插入节点

package com.yin.m3LinkedList;

public class SingleLinkedListDemo {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//测试
		//创建节点
		HeroNode hero1=new HeroNode(1,"1白敬亭","1小白");
		HeroNode hero2=new HeroNode(2,"2杨洋","2小羊");
		HeroNode hero3=new HeroNode(3,"3刘昊然","3然然");
		HeroNode hero4=new HeroNode(4,"4刘瑞琳","4小刘");
		//创建链表
		SingleLinkedList singleLinkedList=new SingleLinkedList();
		//加入   
//		singleLinkedList.add(hero1);
//		singleLinkedList.add(hero2);
//		singleLinkedList.add(hero3);
//		singleLinkedList.add(hero4);
		
		//加入，按照编号顺序
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero2);
		singleLinkedList.addByOrder(hero1);
		singleLinkedList.addByOrder(hero4);
		//显示
		singleLinkedList.list();
	}
}

//定义一个SingleLinkedList管理
class SingleLinkedList{
	//初始化头节点
	private HeroNode head = new HeroNode(0,"","");
	
	//添加节点到单项列表
	public void add(HeroNode heroNode) {
		//1.找到链表最后节点
		HeroNode temp=head;
		while(true) {
			//找到链表的最后
			if(temp.next==null) {
				break;
			}
			temp=temp.next;
		}//退出循环时，temp指向链表最后
		temp.next=heroNode;
	}
	
	//第二种方式添加英雄时，根据排名将英雄插入到指定位置
	public void addByOrder(HeroNode heroNode) {
		//因为头节点不能动，利用辅助节点
		HeroNode temp=head;
		boolean 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) {//说明希望添加的编号已经存在
				flag=true;//编号存在
			break;
			}
			temp=temp.next;
		}
		//判断flag的值
		if(flag) {//编号存在，不能添加
			System.out.printf("准备插入的英雄编号%d已经存在了，不能加入\n",heroNode.no);
		}else {
			//插入到链表中
			heroNode.next=temp.next;
			temp.next=heroNode;
		}
	}
		
	//显示链表
	public void list() {
		//判断链表是否为空
		if(head.next==null) {
			System.out.println("链表为空");
			return;
		}
		//因为头节点不能动，需要辅助变量temp遍历
		HeroNode temp=head.next;
		while(true) {
			//找到链表的最后
			if(temp==null) {
				break;
			}
			//输出节点信息
			System.out.println(temp);
			//temp要后移
			temp=temp.next;
		}//退出循环时，temp指向链表最后
	}
}

//定义一个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方法  alt+shift+s
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" +"]";
	}
}

2.单链表结点的修改

package com.yin.m3LinkedList;

public class SingleLinkedListDemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//测试
		//创建节点
		HeroNode hero1=new HeroNode(1,"1白敬亭","1小白");
		HeroNode hero2=new HeroNode(2,"2杨洋","2小羊");
		HeroNode hero3=new HeroNode(3,"3刘昊然","3然然");
		HeroNode hero4=new HeroNode(4,"4刘瑞琳","4小刘");
		//创建链表
		SingleLinkedList singleLinkedList=new SingleLinkedList();
		//加入   
//		singleLinkedList.add(hero1);
//		singleLinkedList.add(hero2);
//		singleLinkedList.add(hero3);
//		singleLinkedList.add(hero4);
		
		//加入，按照编号顺序
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero2);
		singleLinkedList.addByOrder(hero1);
		singleLinkedList.addByOrder(hero4);
		
		//修改前显示
		System.out.println("修改前的链表情况：");
		singleLinkedList.list();
		
		//测试修改节点代码
		HeroNode newHeroNode=new HeroNode(2,"2更改后的杨洋","2黑风夕");
		singleLinkedList.update(newHeroNode);
		
		
		//显示
		System.out.println("修改后的链表情况：");
		singleLinkedList.list();

	}

}


//定义一个SingleLinkedList管理
class SingleLinkedList{
	//初始化头节点
	private HeroNode head = new HeroNode(0,"","");
	
	//添加节点到单项列表
	public void add(HeroNode heroNode) {
		//1.找到链表最后节点
		HeroNode temp=head;
		while(true) {
			//找到链表的最后
			if(temp.next==null) {
				break;
			}
			temp=temp.next;
		}//退出循环时，temp指向链表最后
		temp.next=heroNode;
	}
	
	//第二种方式添加英雄时，根据排名将英雄插入到指定位置
	public void addByOrder(HeroNode heroNode) {
		//因为头节点不能动，利用辅助节点
		HeroNode temp=head;
		boolean 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) {//说明希望添加的编号已经存在
				flag=true;//编号存在
			break;
			}
			temp=temp.next;
		}
		//判断flag的值
		if(flag) {//编号存在，不能添加
			System.out.printf("准备插入的英雄编号%d已经存在了，不能加入\n",heroNode.no);
		}else {
			//插入到链表中
			heroNode.next=temp.next;
			temp.next=heroNode;
		}
	}
	
	//修改节点的信息,根据编号修改，编号no不能改
	public void update(HeroNode newHeroNode) {
		//判断是否为空
		if(head.next==null) {
			System.out.println("链表为空~");
			return;
		}
		//找到需要的节点，根据no编号
		//定义一个辅助变量
		HeroNode temp=head.next;
		boolean flag=false;//表示是否找到该节点
		while(true) {
			if(temp==null) {
				break;
			}
			if(temp.no==newHeroNode.no) {
				//找到了
				flag=true;
				break;
			}
			temp=temp.next;
		}
		//根据flag 判断是否找到要修改的节点
		if(flag) {
			temp.name=newHeroNode.name;
			temp.nickname=newHeroNode.nickname;
		}else {
			//没有找到
			System.out.printf("没有找到编号为%d的节点，不能修改\n",newHeroNode.no);
		}
	}
	
	//显示链表
	public void list() {
		//判断链表是否为空
		if(head.next==null) {
			System.out.println("链表为空");
			return;
		}
		//因为头节点不能动，需要辅助变量temp遍历
		HeroNode temp=head.next;
		while(true) {
			//找到链表的最后
			if(temp==null) {
				break;
			}
			//输出节点信息
			System.out.println(temp);
			//temp要后移
			temp=temp.next;
		}//退出循环时，temp指向链表最后
	}
}



//定义一个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方法  alt+shift+s
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" +nickname+"]";
	}
	
	//
	
}

3.单链表结点的删除

注意要用temp找到待删除结点的前一个结点
让temp.next=temp.next.next*
被删除的节点不会有其他引用指向，会被垃圾回收机制回收。

//删除结点的代码
	//head节点不能动，引用temp辅助节点
	public void del(int no) {
		HeroNode temp=head;
		boolean flag=false;//表示是否找到待删除节点的前一个节点，默认是否
		while(true) {
			if(temp.next==null) {//已经遍历到链表最后
				break;
			}
			if(temp.next.no==no) {
				//找到了待删除节点的前一个节点temp
				flag=true;
				break;
			}
			temp=temp.next;//temp后移，遍历
		}
		//判断flag
		if(flag) {
			//可以删除
			temp.next=temp.next.next;
		}else {
			System.out.printf("要删除的%d节点不存在", no);
		}
	}

//删除前显示
		System.out.println("删除前的链表情况：");
		singleLinkedList.list();
				
		//测试删除节点代码
		singleLinkedList.del(2);
				
				
		//显示
		System.out.println("删除后的链表情况：");
		singleLinkedList.list();