文章目录

• • 双向链表
  • • 单向链表的缺点分析：
    • 双向链表增删改功能
    • 单向环形链表

双向链表

单向链表的缺点分析：

1. 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
2. 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点(认真体会).
3. 示意图帮助理解删除

双向链表增删改功能

（1）遍历：方法和 单链表一样，只是可以向前，也可以向后查找

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

（2）添加 ：(默认添加到双向链表的最后)

1. 先找到双向链表的最后这个节点
2. temp.next = newHeroNode
3. newHeroNode.pre = temp;

	//添加节点到双向链表的最后
	//思路，(默认添加到双向链表的最后)
	//1. 先找到双向链表的最后这个节点
	//2. temp.next = newHeroNode
	//3. newHeroNode.pre = temp;
	public void add(HeroNode2 heroNode) {
		
		//因为head节点不能动，因此我们需要一个辅助遍历 temp
		HeroNode2 temp = head;
		//遍历链表，找到最后
		while(true) {
			//找到链表的最后
			if(temp.next == null) {//
				break;
			}
			//如果没有找到最后, 将将temp后移
			temp = temp.next;
		}
		//当退出while循环时，temp就指向了链表的最后
		//形成一个双向链表
		temp.next = heroNode;
		heroNode.pre=temp;
	}

（3) 修改： 思路和 原来的单向链表一样.

	//修改一个节点的内容
	//修改节点的信息, 根据no编号来修改，即no编号不能改.
	//说明1. 根据 newHeroNode 的 no 来修改即可
	public void update(HeroNode2 newHeroNode) {
		//判断是否空
		if(head.next == null) {
			System.out.println("链表为空~");
			return;
		}
		//找到需要修改的节点, 根据no编号
		//定义一个辅助变量
		HeroNode2 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);
		}
	}

（4) 删除：

1. 因为是双向链表，因此，我们可以实现自我删除某个节点
2. 直接找到要删除的这个节点，比如temp
3. temp.pre.next = temp.next
4. temp.next.pre = temp.pre;

	//从双向链表中删除一个节点
	//说明：1.对于双向链表，我们可以直接找到要删除的这个节点
	//2.找到后，自我删除即可
	public void del(int no) {
		
		//判断链表是否为空
		if (head.next==null) {
			System.out.println("链表为空，无法删除");
			return;
		}
		HeroNode2 temp = head.next;//辅助节点（指针）
		boolean flag = false; // 标志是否找到待删除节点的
		while(true) {
			if(temp == null) { //已经到链表的最后
				break;
			}
			if(temp.no == no) {
				//找到的待删除节点的节点temp
				flag = true;
				break;
			}
			temp = temp.next; //temp后移，遍历
		}
		//判断flag
		if(flag) { //找到
			//可以删除
//			temp.next = temp.next.next;//单向链表删除
			temp.pre.next = temp.next;
			//这里代码有问题，若删除的节点是最后一个节点，就不需要执行下面这一不足，否则会出现空指针异常
			if(temp.next!=null) {
				temp.next = temp.pre.next;
			}
		}else {
			System.out.printf("要删除的 %d 节点不存在\n", no);
		}
	}

单向环形链表

（1）单向环形链表介绍：

（2）构建一个单向的环形链表思路

1. 先创建第一个节点, 让 first 指向该节点，并形成环形
2. 后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可.

//创建一个环形单向链表
//创建一个first节点，当前没有编号
	private Boy first = null;
	//添加小孩节点，构建成一个环形的链表
	public void addBoy(int nums) {
		//nums 做一个数据校验
		if(nums<1) {
			System.out.println("nums的值不正确");
			return;
		}
		Boy curBoy = new Boy(0);//辅助指针，帮助创建环形链表
		//使用for循环来创建我们的环形链表
		for (int i = 0; i <= nums; i++) {
			//根据编号，创建小孩节点
			Boy boy = new Boy(i);
			//如果是第一个小孩
			if(i==1) {
				first=boy;
				first.setNext(first);//构成环
				curBoy=first;//让curBoy指向第一个小孩
			}else {
				curBoy.setNext(boy);
				boy.setNext(first);
				curBoy = boy;
			}
		}
	}
	

（3）遍历环形链表

1. 先让一个辅助指针(变量) curBoy，指向first节点
2. 然后通过一个while循环遍历 该环形链表即可 curBoy.next == first结束

	//遍历当前环形链表
	public void showBoy() {
		//判断链表是否为空
		if(first==null) {
			System.out.println("链表为空，没有小孩··");
		}
		//因为first不能动，因此我们仍然使用一个辅助指针完成遍历
		Boy curBoy = first;
		while (true) {
			System.out.printf("小孩编号%d \n",curBoy.getNo());
			if(curBoy.getNext()==first) {//说明已经遍历完毕
				break;
			}
			curBoy = curBoy.getNext();
		}
	}
}

（3）约瑟夫问题：


图解及思路分析：

1. 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点.
2. 小孩报数前，先让 first 和 helper 移动 k - 1次
3. 当小孩报数时，让first 和 helper 指针同时 的移动 m - 1 次
4. 这时就可以将first 指向的小孩节点 出圈：1.first = first .next2. helper.next = first（原来first 指向的节点就没有任何引用，就会被回收）

	//根据用户的输入，计算出小孩出圈的顺序
	/**
	 * startNo  表示从第几个小孩开始数数
	 * countNum  表示数几下
	 * nums  表示最初有几个小孩在圈中
	 */
	public void countBoy(int startNo,int countNum,int nums) {
		//先对数据进行校验
		if(first==null||startNo<1||startNo>nums) {
			System.out.println("参数输入有误，请重新输入");
			return ;
		}
		//创建辅助指针，帮助完成小孩出圈
		Boy helper = first;
		//创建一个辅助指针helper，实现应该指向环形链表的最后这个节点
		while(true) {
			if(helper.getNext()==first) {//说明helper指向最后小孩节点
				break;
			}
			helper = helper.getNext();
		}
		//小孩报数前，先让 first 和  helper 移动 k - 1次
		for(int j=0;j<startNo-1;j++) {
			first=first.getNext();
			helper=helper.getNext();
		}
		//当小孩报数时，让first 和 helper 指针同时 的移动  m  - 1 次,然后出圈
		//这里是循环操作，直到圈子只有一个节点
		while (true) {
			if(helper==first) {//说明圈子只有一个节点
				break;
			}
			//让first 和 helper 指针同时 的移动  m  - 1 次,然后出圈
			for (int j = 0; j < countNum-1; j++) {
				first=first.getNext();
				helper=helper.getNext();
			}
			//这时first指向的节点，就是要出圈的小孩节点
			System.out.printf("小孩 %d 出圈\n",first.getNo());
			//这时就可以将first 指向的小孩节点 出圈
			first = first.getNext();
			helper.setNext(first);
		}
		System.out.printf("最后留在圈中的小孩编号%d \n",first.getNo());
		
	}