双向链表

单双链表的一些比较

单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。

单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点.

分析思路和代码实现

双向链表的遍历，添加，修改，删除的操作思路，代码实现

遍历方式和单链表一样，只是可以向前，也可以向后查找

添加 (默认添加到双向链表的最后)

先找到双向链表的最后这个节点

temp.next = newHeroNode

newHeroNode.pre = temp

修改思路和原来的单向链表一样.

删除

因为是双向链表，因此，我们可以实现自我删除某个节点

直接找到要删除的这个节点，比如temp

temp.pre.next = temp.next

temp.next.pre = temp.pre;

public class DoubleLinkedListDemo {	public static void main(String[] args) {		// 测试		System.out.println("双向链表的测试");		// 先创建节点		HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");		HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");		HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");		HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");		// 创建一个双向链表		DoubleLinkedList doubleLinkedList = new DoubleLinkedList();		doubleLinkedList.add(hero1);		doubleLinkedList.add(hero2);		doubleLinkedList.add(hero3);		doubleLinkedList.add(hero4);		doubleLinkedList.list();		// 修改		HeroNode2 newHeroNode = new HeroNode2(4, "公孙胜", "入云龙");		doubleLinkedList.update(newHeroNode);		System.out.println("修改后的链表情况");		doubleLinkedList.list();		// 删除		doubleLinkedList.del(3);		System.out.println("删除后的链表情况~~");		doubleLinkedList.list();	}}// 创建一个双向链表的类class DoubleLinkedList {	// 先初始化一个头节点, 头节点不要动, 不存放具体的数据	private HeroNode2 head = new HeroNode2(0, "", "");	// 返回头节点	public HeroNode2 getHead() {		return head;	}	// 遍历双向链表的方法	// 显示链表[遍历]	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;		}	}	// 添加一个节点到双向链表的最后.	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;	}	// 修改一个节点的内容, 可以看到双向链表的节点内容修改和单向链表一样	// 只是 节点类型改成 HeroNode2	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);		}	}	// 从双向链表中删除一个节点,	// 说明	// 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.pre = temp.pre;			}		} else {			System.out.printf("要删除的 %d 节点不存在\n", no);		}	}}// 定义HeroNode2 ， 每个HeroNode 对象就是一个节点class HeroNode2 {	public int no;	public String name;	public String nickname;	public HeroNode2 next; // 指向下一个节点, 默认为null	public HeroNode2 pre; // 指向前一个节点, 默认为null	// 构造器	public HeroNode2(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 + "]";	}}复制代码

单向环形链表

Josephu(约瑟夫、约瑟夫环) 问题

Josephu 问题为：设编号为1，2，…n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

提示

用一个不带头结点的循环链表来处理Josephu问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

例： n = 5 , 即有5个人。 k = 1, 从第一个人开始报数。 m = 2, 数2下。

使用环形单向链表来解决 Josephu问题

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

先创建第一个节点, 让 first 指向该节点，并形成环形，当前节点为curBoy

后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可.将新的节点称为boy,将curboy.next = boy;boy.next=first；curBoy = boy;

遍历环形链表

先让一个辅助指针(变量) curBoy，指向first节点

然后通过一个while循环遍历该环形链表即可。当 curBoy.next == first 结束遍历

根据用户的输入，生成一个小孩出圈的顺序

n = 5 , 即有5个人

k = 1, 从第一个人开始报数

m = 2, 数2下

需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点. 补充：小孩报数前，先让 first 和 helper 移动 k - 1次

当小孩报数时，让first 和 helper 指针同时的移动 m - 1 次

这时就可以将first 指向的小孩节点出圈 first = first .next; helper.next = first
原来first 指向的节点就没有任何引用，就会被回收

出圈的顺序 2->4->1->5->3

代码实现

节点类

// 创建一个Boy类，表示一个节点class Boy {	private int no;// 编号	private Boy next; // 指向下一个节点,默认null	public Boy(int no) {		this.no = no;	}	public int getNo() {		return no;	}	public void setNo(int no) {		this.no = no;	}	public Boy getNext() {		return next;	}	public void setNext(Boy next) {		this.next = next;	}}复制代码

// 创建一个环形的单向链表class CircleSingleLinkedList {	// 创建一个first节点,当前没有编号	private Boy first = null;	// 添加小孩节点，构建成一个环形的链表	public void addBoy(int nums) {		// nums 做一个数据校验		if (nums < 1) {			System.out.println("nums的值不正确");			return;		}		Boy curBoy = null; // 辅助指针，帮助构建环形链表		// 使用for来创建我们的环形链表		for (int i = 1; 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;			}		}	}	// 遍历当前的环形链表	public void showBoy() {		// 判断链表是否为空		if (first == null) {			System.out.println("没有任何小孩~~");			return;		}		// 因为first不能动，因此我们仍然使用一个辅助指针完成遍历		Boy curBoy = first;		while (true) {			System.out.printf("小孩的编号 %d \n", curBoy.getNo());			if (curBoy.getNext() == first) {// 说明已经遍历完毕				break;			}			curBoy = curBoy.getNext(); // curBoy后移		}	}	// 根据用户的输入，计算出小孩出圈的顺序	/**	 * @param startNo 表示从第几个小孩开始数数	 * @param countNum 表示数几下	 * @param 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 指针同时 的移动 countNum - 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());	}}复制代码

//测试public class Josepfu {	public static void main(String[] args) {		// 测试一把看看构建环形链表，和遍历是否ok		CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();		circleSingleLinkedList.addBoy(125);// 加入5个小孩节点		circleSingleLinkedList.showBoy();				//测试一把小孩出圈是否正确		circleSingleLinkedList.countBoy(10, 20, 125); // 2->4->1->5->3		//String str = "7*2*2-5+1-5+3-3";	}}复制代码