java数据结构-链表详解_java中的链表数据结构

1.数据结构-链表详解

链表可分为三类：

1. 单链表
2. 双向链表
3. 循环列表

下面具体分析三个链表的应用。

1.1单链表

单链表是有序的列表，它在内存中存储方式如下：

虽然单链表是有序列表，但是其元素并不是连续存储的。我们从图中可以看出，a1的next域为110，而地址为110的元素为a2；a2的next域为180，而地址为180的元素为a3，以此类推。
综上所述：

• 单链表是以节点的方式来存储的
• 每个节点包含data域(存储数据)，next域(指向下一个节点)
• 单链表的各个节点不一定是连续存储的

1.1.1单链表节点的尾部添加

对单链表的概念和特点有所了解之后，我们通过一个案例来感受一下单链表的魅力所在。
需求：使用带head头节点的单向链表实现——水浒英雄排行榜管理，完成对英雄人物的增删改查操作。

根据该示意图，我们可以得出创建单链表的具体过程：

1. 先创建一个head头节点，不存储数据，作用就是表示单链表的头
2. 后面每添加一个节点，就直接加入到链表的末尾

源码实现：

//定义SingleLinkedList 管理英雄
class SingleLinkedList {
	// 初始化一个头节点 不存放具体数据
	private HeroNode head = new HeroNode(0, "", "");

	// 添加节点到单向链表
	public void add(HeroNode heroNode) {
		// 当不考虑编号的顺序时:
		// 1、找到当前链表的最后节点
		// 2、将最后这个节点的next域指向新的节点即可

		// 因为head头节点不能动，因此我们需要一个辅助节点temp
		HeroNode temp = head;
		// 遍历链表，找到尾节点
		while (true) {
			// 找到链表的尾节点
			if (temp.next == null) {
				break;
			}
			// 如果不是尾节点，将temp后移
			temp = temp.next;
		}

		// 循环结束后，temp指向的是尾节点
		temp.next = heroNode;// 将next域指向新节点
	}

	// 显示链表
	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;
	}

	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

这样链表就编写完毕了，接下来编写测试代码：

	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();
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

运行结果：

HeroNode [no=1, name=宋江, nickname= 及时雨]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]

1
2
3
4
5

现在这个程序虽然可以创建链表，但是它并不能保证元素按照编号进行排序，它只是按照添加的顺序进行创建的。
那么如何使英雄在添加进链表的时候始终按照排名添加呢？
我们来分析一下：

1. 首先要找到新添加的节点位置，通过一个辅助节点
2. 让新节点的next等于辅助节点的next，因为辅助节点已经找到了要添加的位置，所以将辅助节点的next赋给新节点的next即可
3. 将新节点的赋值给辅助节点的next

1.1.2单链表节点的自动排序添加

源码实现：

//定义SingleLinkedList 管理英雄
class SingleLinkedList {
	// 初始化一个头节点 不存放具体数据
	private HeroNode head = new HeroNode(0, "", "");
	
	// 第二种添加方式，根据排名进行添加
	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;// 将temp后移
		}
		// 循环结束后，判断flag
		if (flag) {
			// 编号存在，不能添加
			System.out.println("准备插入的英雄编号" + heroNode.no + "重复，不能加入");
		} else {
			// 插入到链表中
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}

	// 显示链表
	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;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

编写测试代码：

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.addByOrder(hero1);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero2);
		
		// 显示链表
		singleLinkedList.list();
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

运行效果：

HeroNode [no=1, name=宋江, nickname= 及时雨]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]

1
2
3
4
5

此时即使添加顺序不正确，在插入后链表依然将英雄排名进行了排序，这是在插入的时候就已经完成了排序。

1.1.3单链表节点的修改

通过上面的分析和实践，我们已经知道如何去创建一个单链表，那么如何对单链表的节点修改呢？

// 修改节点的信息，根据no编号来修改
	public void update(HeroNode newHeroNode) {
		// 根据newHeroNode的编号进行修改
		// 判断链表是否为空
		if (head == 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;// 将temp后移
		}
		// 根据flag判断是否已经找到要修改的节点
		if (flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else {
			// 没有找到节点
			System.out.println("没有找到");
		}
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

修改的实现相对来说就非常简单了。

下面测试一下：

	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.addByOrder(hero1);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero2);
		
		//修改节点
		HeroNode newHeroNode = new HeroNode(2, "小卢","~玉麒麟~");
		singleLinkedList.update(newHeroNode);
		
		// 显示链表
		singleLinkedList.list();
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

运行结果：

HeroNode [no=1, name=宋江, nickname= 及时雨]
HeroNode [no=2, name=小卢, nickname=~玉麒麟~]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]

1
2
3
4
5

编号为2的英雄信息就被修改过来了。

1.1.4单链表节点的删除

接下来是最后一个操作，删除。
首先分析一下：

1. 先找到需要删除节点的前一个节点，通过一个辅助节点temp
2. temp.next = temp.next.next，也就是说需要删除节点的前一个节点本来指向的是删除节点，然后我们使其指向删除节点的下一个节点，直接跳过删除节点，这样该节点也就相当于被删除了
3. 被删除的节点将不会有其它引用指向，会被垃圾回收器回收

源码实现：

	// 删除节点
	public void delete(int no) {
		// 定义辅助节点
		HeroNode temp = head;
		boolean flag = false;// 是否找到待删除节点的前一个节点
		while (true) {
			if (temp.next == null) {
				// 遍历结束
				break;
			}
			if (temp.next.no == no) {
				// 找到
				flag = true;
				break;
			}
			temp = temp.next;// 将temp后移
		}
		// 判断flag
		if (flag) {
			// 找到
			// 可以删除
			temp.next = temp.next.next;
		} else {
			// 未找到
			System.out.println("要删除的节点不存在");
		}
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

测试代码：

	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.addByOrder(hero1);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero2);
		
		//删除节点
		singleLinkedList.delete(1);

		// 显示链表
		singleLinkedList.list();
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

运行结果：

HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]

1
2
3
4

宋江被成功删除。

到这里，关于单链表的增删改查操作就全部结束。

1.2单链表面试题

1.2.1单链表的有效节点个数

代码实现：

//方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)
	/**
	 * 
	 * @param head 链表的头节点
	 * @return 返回的就是有效节点的个数
	 */
	public static int getLength(HeroNode head) {
		if(head.next == null) { //空链表
			return 0;
		}
		int length = 0;
		//定义一个辅助的变量, 这里我们没有统计头节点
		HeroNode cur = head.next;
		while(cur != null) {
			length++;
			cur = cur.next; //遍历
		}
		return length;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

测试代码：

	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.addByOrder(hero1);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero2);
		
		//测试单链表中有效节点的个数
        System.out.println("有效的节点个数=" +getLength(singleLinkedList.getHead()));//2 
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

运行结果：

有效的节点个数=4
1

1.2.2单链表倒数第k个结点

代码实现：

//查找单链表中的倒数第k个结点 【新浪面试题】
	//思路
	//1. 编写一个方法，接收head节点，同时接收一个index 
	//2. index 表示是倒数第index个节点
	//3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
	//4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
	//5. 如果找到了，则返回该节点，否则返回nulll
	public static HeroNode findLastIndexNode(HeroNode head, int index) {
		//判断如果链表为空，返回null
		if(head.next == null) {
			return null;//没有找到
		}
		//第一个遍历得到链表的长度(节点个数)
		int size = getLength(head);
		//第二次遍历  size-index 位置，就是我们倒数的第K个节点
		//先做一个index的校验
		if(index <=0 || index > size) {
			return null; 
		}
		//定义给辅助变量， for 循环定位到倒数的index
		HeroNode cur = head.next; //3 // 3 - 1 = 2
		for(int i =0; i< size - index; i++) {
			cur = cur.next;
		}
		return cur;
		
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

测试代码：

	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.addByOrder(hero1);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero2);
		
		//测试一下看看是否得到了倒数第K个节点
		HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 3);
		System.out.println("倒数第3个节点=" + res);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

运行结果：

倒数第3个节点=HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
1

1.2.3单链表反转

代码实现：

//将单链表反转
	public static void reversetList(HeroNode head) {
		//如果当前链表为空，或者只有一个节点，无需反转，直接返回
		if(head.next == null || head.next.next == null) {
			return ;
		}
		
		//定义一个辅助的指针(变量)，帮助我们遍历原来的链表
		HeroNode cur = head.next;
		HeroNode next = null;// 指向当前节点[cur]的下一个节点
		HeroNode reverseHead = new HeroNode(0, "", "");
		//遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
		//动脑筋
		while(cur != null) { 
			next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
			cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
			reverseHead.next = cur; //将cur 连接到新的链表上
			cur = next;//让cur后移
		}
		//将head.next 指向 reverseHead.next , 实现单链表的反转
		head.next = reverseHead.next;
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

测试代码：

	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.addByOrder(hero1);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero2);
		//测试反转单链表
        System.out.println("原来链表的情况~~");
		singleLinkedList.list();

		System.out.println("反转单链表~~");
		reversetList(singleLinkedList.getHead());
		singleLinkedList.list();	
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

运行结果：

原来链表的情况~~
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]
反转单链表~~
HeroNode [no=4, name=林冲, nickname=豹子头]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=1, name=宋江, nickname=及时雨]
1
2
3
4
5
6
7
8
9
10

1.2.4单链表逆序打印

代码实现：

//可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
	public static void reversePrint(HeroNode head) {
		if(head.next == null) {
			return;//空链表，不能打印
		}
		//创建要给一个栈，将各个节点压入栈
		Stack<HeroNode> stack = new Stack<HeroNode>();
		HeroNode cur = head.next;
		//将链表的所有节点压入栈
		while(cur != null) {
			stack.push(cur);
			cur = cur.next; //cur后移，这样就可以压入下一个节点
		}
		//将栈中的节点进行打印,pop 出栈
		while (stack.size() > 0) {
			System.out.println(stack.pop()); //stack的特点是先进后出
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

测试代码：

	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.addByOrder(hero1);
		singleLinkedList.addByOrder(hero3);
		singleLinkedList.addByOrder(hero4);
		singleLinkedList.addByOrder(hero2);
		//测试逆序打印单链表, 没有改变链表的结构
		System.out.println("原来链表的情况~~");
		singleLinkedList.list();
	
		System.out.println("测试逆序打印单链表, 没有改变链表的结构~~");
		reversePrint(singleLinkedList.getHead());
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

运行结果：

原来链表的情况~~
HeroNode [no=1, name=宋江, nickname=及时雨]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=4, name=林冲, nickname=豹子头]
测试逆序打印单链表, 没有改变链表的结构~~
HeroNode [no=4, name=林冲, nickname=豹子头]
HeroNode [no=3, name=吴用, nickname=智多星]
HeroNode [no=2, name=卢俊义, nickname=玉麒麟]
HeroNode [no=1, name=宋江, nickname=及时雨]
1
2
3
4
5
6
7
8
9
10

1.3双向链表

1.3.1双向链表介绍

1. 双向链表可以向前或者向后查找。而单向链表，只能一个方向查找。
2. 双向链表，可以自我删除。单向链表不能自我删除，需要靠辅助节点 ，所以前面我们单链表删除节点时，总是找到temp,temp是待删除节点的前一个节点。

1.3.2双向链表增删改查

源码实现：

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.addByOrder(hero4);
		doubleLinkedList.addByOrder(hero3);
		doubleLinkedList.addByOrder(hero2);
		doubleLinkedList.addByOrder(hero1);
		
		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 addByOrder(HeroNode2 heroNode) {
			//因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
			//因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
			HeroNode2 temp = head;
			boolean flag = false; // 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) {//说明希望添加的heroNode的编号已然存在
					
					flag = true; //说明编号存在
					break;
				}
				temp = temp.next; //后移，遍历当前链表
			}
			//判断flag 的值
			if(flag) { //不能添加，说明编号存在
				System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
			} else {
				heroNode.next = temp.next;
				//（若temp是最后一个节点则不需要执行这句话否则出现空指针）
				if(temp.next!=null)
		        temp.next.pre = heroNode;

		        heroNode.pre = temp;
		        temp.next = heroNode;
			}
		}

	// 添加一个节点到双向链表的最后.
	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 + "]";
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225

1.4单向环形链表

示意图：

1.4.1约瑟夫（Josephu）环问题

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

思路提示：( 使用单向环形链表解决Josephu问题)

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

源码实现：

public class Josephu {

	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";
	}

}

// 创建一个环形的单向链表
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());
		
	}
}

// 创建一个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;
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143