链表补充

链表补充

001单链表的创建、遍历

1. 先创建一个head头节点，作用表示单链表的的头

2. 后面每添加一个节点，直接加入如链表最后

3. 遍历: 通过一个辅助变量，帮助遍历整个链表

   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(hero2);
   		singleLinkedList.add(hero3);
   		singleLinkedList.add(hero4);
   		//显示
   		singleLinkedList.list();
   	}
   
   }
   
   //定义一个SingleLinkedList 管理英雄
   class SingleLinkedList {
   	//先初始化头节点，头结点不要动, 不存放具体数据
   	private HeroNode head = new HeroNode(0,"","");
   	
   	//添加节点到单向链表
   	//思路，不考虑编号顺序时，1、找到最后一个节点 2 、将最后一个节点的next 只想新节点
   	public void add(HeroNode Newnode) {
   		//应为头结点不能动，需要一个辅助变量 temp
   		HeroNode temp = head;
   		//遍历链表，找到最后
   		while(true) {
   			if(temp.next == null) {
   				break;
   			}
   			//没有找最后,后移
   			temp = temp.next;
   		}
   		//当退出循环时，temp就指向了链表的最后
   		//将最后这个节点的next 指向新的节点
   		temp.next = Newnode;
   	}
   	//显示链表遍历
   	public void list() {
   		//先判断链表是否为空
   		if(head.next == null) {
   			System.out.println("链表为空");
   			return;
   		}
   		//辅助变量来遍历
   		HeroNode temp = head.next;
   		while(true) {
   			//判断是否到链表最后
   			if (temp == null) {
   				break;
   			}
   			//输出节点信息
   			System.out.println(temp);
   			//将temp后移
   			temp = temp.next;
   		}
   	}
   	
   }
   
   
   
   //定义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 + "]";
   	}
   	
   }
   

002按照顺序插入节点

1. 首先找到新添加的节点位置，通过辅助变量，遍历
2. 新的节点 next = temp .next
3. 将 temp. next = 新的节点

	//第二种添加方法，根据排名插入到指定位置
	public void addByOrder(HeroNode Newnode) {
		//因为单链表我们找的temp 位于添加位置的前一个节点，否则加不进去
		HeroNode temp = head;
		boolean flag = false;//标志 添加得编号是否存在，默认false
		while(true) {
			if(temp.next == null) {//temp已经在最后了
				break;
			}
			if(temp.next.no > Newnode.no) {  //位置找到，就在temp 后面插入
				break;
			}else if (temp.next.no == Newnode.no){//说明编号已经存在
				flag =true;//编号存在
				break;
			}
			temp = temp.next;//后移 遍历
		}
		//判断 flag 的值
		if(flag) {//不能添加 ，编号已经存在
			System.out.printf("准备插入英雄的编号%d已经存在了，不能加入\n"+Newnode.no);
		}else {
			//插入到链表中
			Newnode.next = temp.next;
			temp.next = Newnode;
		}
	}

003修改节点

	//修改节点信息，根据NO 修改，即no编号不能改
	public void updata(HeroNode newHeroNode) {
		//判断是否为空
		if(head.next==null) {
			System.out.println("链表为空");
			return;
		}
		//找到需要修改的节点，
		//先定义辅助变量
		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);
		}
	}

004删除节点

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

	//删除节点
	public void delate(int no) {
		HeroNode temp = head;
		boolean flag =false;
		while(true) {
			if(temp.next == null) {
			break;
		}
		if(temp.next.no == no) {
			flag =true;//找到了要删除节点的前一个节点temp
			break;
		}
		temp = temp.next; //都不行的话 temp后移 遍历
	   }
		if(flag) {
			temp.next = temp.next.next;
		}else {
			System.out.printf("没有找到要删除的%d节点"+no);
		}
	}