记录生活中的点点滴滴

0%

链表

链表

链表是我们常见的数据结构了,其实以前在学C语言的时候都写过了,不过那个引用指针什么的确实挺不容易写的,今天用Java语言写链表感觉真的方便多了。下面主要写三种链表,单链表、双向链表、单向环形链表。其实都差不太多,它们主要的方法基本也差不多,判断为空、遍历链表、表头插入、表尾插入、表头删除、指定位置删除、指定位置插入等等吧。反正我的单链表这些功能基本都实现了一遍,剩下两种链表只实现了部分功能,主要写的是思想,我感觉,自己差不多全部实现一遍会更好。

对了,先说一个约定:我们约定链表的头结点的数据域为空。

为什么这样约定,因为这样会方便我们的判断等等很多操作,不必要去纠结这个,我们要做的是去学习我们自己实现它的过程。

对于Java而言,它有一个特点我们也要注意:被删除的节点,将不会有其他引用指向,会被垃圾回收机制回收。

因为链表这部分东西不是很难的东西,所以我们自己画画图基本都能搞明白,我写的时候当然也会出现一些想不明白的问题,但是IDEA的Debug是真的香,用这玩意单步走基本就能看出来自己哪出问题了。

单链表

要想玩链表,首先我们得定义一种数据结构,对于任何链表而言,都得有个节点(Node)类吧,它要有两个属性:数据域下一个数据的指针域

此外,还得定义一个构造方法,无参和有参。我们的数据域直接用String类型了,不纠结这。ok,节点类如下所示:

1
2
3
4
5
6
7
8
9
class Node{
public String data;//数据
public Node next;//指向下一个节点
public Node(String data){
this.data = data;
}
public Node(){
}
}

OK,这是基本的东西。我们接下来会写一系列方法,都在Demo类中,然后还会有这些方法对应的测试方法,我们引用了 junit jar包,也会写在Demo类中,对应方法后面。

链表是否为空

开始吧,首先第一件事就是判断链表是否为空,这太重要了,因为后续的插入删除什么的都会先用到这个方法。怎么样这个链表会是空的,废话,因为我们约定头结点为空了,所以只要头结点的next域为空,那么链表为空。代码如下:

1
2
3
4
//判断是否为空
public static boolean isEmpty(Node head){
return head.next == null;
}
遍历链表

接下来,怎样去遍历链表。我们思考下,如果链表为空,那么还遍历锤子;不为空的话,我们用一个while循环即可,不过记得要先 Node temp = head.next; ,我们可不能瞎搞head指针,要借助一个辅助变量指针,所以,遍历代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//遍历链表
public static void list(Node head){
if(isEmpty(head)){
System.out.println("链表为空...");
return;
}
//不能乱搞head节点,要借助辅助变量来遍历
Node temp = head.next;
while (temp!=null){
System.out.printf("%s\t",temp.data);
temp = temp.next;
}
System.out.println();
}

这样,我们测试一下吧,我们自己手动创建一个单链表,然后遍历一下看看对不对,如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
//测试遍历方法
@Test
public void TestList(){
Node head = new Node();
Node first = new Node("first");
Node second = new Node("second");
Node third = new Node("third");
head.next = first;
first.next = second;
second.next = third;
list(head);
}

结果如下所示:

头插

头插怎么办,看看下面的图片:

基本就是这样,不多bb直接上代码了,后面也懒得画图了,都不难(主要懒得画,麻烦的要死):

1
2
3
4
5
6
//表头插入
public static void insertHead(Node head, Node node){
Node oldFirst = head.next;//原来的第一个节点(切记:头结点为空,我们约定它后面的那个节点为第一个节点)
node.next = oldFirst;//让加入的节点后面为原来的第一个节点
head.next = node;//头结点后面为node
}

再进行测试:

1
2
3
4
5
6
7
8
9
//测试头插方法
@Test
public void TestInsertHead(){
Node head = new Node();
insertHead(head,new Node("third"));
insertHead(head,new Node("second"));
insertHead(head,new Node("first"));
list(head);
}

输出应该和上一次输出的一样。

尾插

尾插先找到最后一个非空节点,然后让它的next域指向新节点即可,代码:

1
2
3
4
5
6
7
8
//表尾插入方法
public void insertLast(Node head, Node node){
Node temp = head;//避免判断是否为空,如果用head.next且表为空,则下面的判断会报空指针异常
while (temp.next!=null){//找到最后那个节点
temp = temp.next;
}
temp.next = node;//最后节点的next设为node即可
}

测试一把:

1
2
3
4
5
6
7
8
9
//测试表尾插入方法
@Test
public void TestInsertLast(){
Node head = new Node();
insertLast(head,new Node("first"));
insertLast(head,new Node("second"));
insertLast(head,new Node("third"));
list(head);
}

也没啥毛病应该。

表头删除

表头删除,让头节点指向第二个节点即可,但是要注意先判断一下是否为空。

1
2
3
4
5
6
7
8
//表头删除
public void delHead(Node head){
if(isEmpty(head)){
throw new RuntimeException("链表为空,删除失败...");
}
// head.next.next = head.next;//执行这个命令,俺电脑直接爆了。。。如下所示
head.next = head.next.next;
}

测试一把:

1
2
3
4
5
6
7
8
9
10
11
12
//表头删除方法测试
@Test
public void TestDelHead(){
Node head = new Node();
insertLast(head,new Node("second"));
insertLast(head,new Node("third"));
insertHead(head,new Node("first"));
list(head);
delHead(head);
delHead(head);
list(head);
}

结果如下:

其他位置插入

后面这三个方法纯粹是闲的没事干,多写几个方法加深自己的印象,多练习练习。

如果想要在data后面插入一个新节点,我们思考一下怎么办。

首先肯定得看链表是否是空链表了,如果为空,插入个锤子;

还得遍历一下链表,看看data是否在链表中,在的话就break,进行插入;如果遍历完都没有data值,那也得告诉用户一下。基本思想就是这样,我们再自行思考思考具体的插入过程,代码如下:

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
//其他位置插入,即在data后面插入
public void insert(Node head, String data, Node node){
if(isEmpty(head)){
System.out.println("链表为空,插入失败...");
return;
}
Node temp = head.next;
boolean flag = false;//标记,看数据是否存在链表中
while (temp!=null){//遍历链表
if(temp.data == data){
flag = true;
break;
}
temp = temp.next;
}
if(flag){
if(temp.next == null){//如果目标节点是尾节点
temp.next = node;
}else {//如果不是尾节点,则做如下操作
Node pNext = temp.next;//目标后的节点
temp.next = node;//目标后节点
node.next = pNext;
}
return;
}
System.out.println("数据不在列表中,插入失败...");
}

测试一把:

1
2
3
4
5
6
7
8
9
10
11
12
//其他位置插入方法测试
@Test
public void TestInsert(){
Node head = new Node();
insertLast(head,new Node("second"));
insertLast(head,new Node("third"));
insertHead(head,new Node("first"));
// insert(head,"hello");
Node node = new Node("insert");
insert(head,"second",node);
list(head);
}

结果如下图:

其他位置删除

从链表中删除data,首先还是先判断链表是否为空,如果是空链表删锤子;非空的话还要找到要删除的前驱节点,然后进行删除操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void del(Node head, String data){
if(isEmpty(head)){
System.out.println("链表为空,删除失败...");
return;
}
Node temp = head;//避免判断是否为空,如果用head.next且表为空,则下面的判断会报空指针异常
boolean flag = false;//标记,看数据是否在链表中
while (temp.next!=null){
if(temp.next.data == data){
flag = true;//此时temp是目标节点的前驱结点
break;
}
temp = temp.next;
}
if(flag){
temp.next = temp.next.next;
return;
}
System.out.println("数据不在链表中,删除失败...");
}

测试一把:

1
2
3
4
5
6
7
8
9
10
11
12
13
//其他位置删除方法测试
@Test
public void TestDel(){
Node head = new Node();
insertLast(head,new Node("second"));
insertLast(head,new Node("third"));
insertHead(head,new Node("first"));
// del(head,"hello");
// del(head,"first");
// del(head,"second");
del(head,"third");
list(head);
}

结果如下:

修改节点

更新修改节点值,还是先要看链表是否为空,然后遍历链表,还要看能否存在要删除的节点,若不存在给出用户提示,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//修改更新节点值
public void update(Node head, String former, String latter){
if(isEmpty(head)){
System.out.println("链表为空,更新失败...");
return;
}
Node temp = head.next;
while (temp!=null){
if(temp.data == former){
temp.data = latter;//修改为新的值
return;
}
temp = temp.next;
}
System.out.println("链表中不存在数据,更新失败...");
}

测试一把:

1
2
3
4
5
6
7
8
9
10
11
12
@Test
public void TestUpdate(){
Node head = new Node();
insertLast(head,new Node("second"));
insertLast(head,new Node("third"));
insertHead(head,new Node("first"));
update(head,"first","666");
//update(head,"second","666");
//update(head,"third","666");
update(head,"hello","666");
list(head);
}

结果如下图:

单链表到此应该就差不多了,其实重要的是我们把它们全部都实现了一遍,这中间的思考过程以及码代码的能力。

双向链表

接着进行双向链表,双向链表无非就是在单链表中加入一个前驱节点的指针罢了。

我们老老实实画画图基本都能解决,对应和插入删除可能会不一样。

先写出双向链表类:

1
2
3
4
5
6
7
8
9
10
class Node{
public String data;//数据
public Node prev;//前一个节点
public Node next;//后一个节点
public Node(String data) {
this.data = data;
}
public Node() {
}
}
是否为空

还是老样子,先写判断双向链表是否为空的函数:

1
2
3
4
//判断双向链表是否为空
public boolean isEmpty(Node head){
return head.next == null;
}

这个和单链表一样,不多解释。

遍历

遍历还是老样子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//遍历
public void list(Node head){
if(isEmpty(head)){
System.out.println("链表为空...");
return;
}
//不能乱搞head节点,要借助辅助变量来遍历
Node temp = head.next;
while (temp!=null){
System.out.printf("%s\t",temp.data);
temp = temp.next;
}
System.out.println();
}
头插

在双向链表表头插如数据可就不一样了,我们还要考虑前驱节点问题。还有双向链表本来为空还是非空的插入操作代码还不一样,具体如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
//表头插入
public void insertHead(Node head,Node node){
if(isEmpty(head)){//判断是否为空。如果为空
head.next = node;
node.prev = head;
}else {//如果不为空
Node oldFirst = head.next;
oldFirst.prev = node;
head.next = node;
node.prev = head;
node.next = oldFirst;
}
}

测试一把:

1
2
3
4
5
6
7
8
9
10
11
12
//表头插入方法测试
@Test
public void TestInsertHead(){
Node head = new Node();
Node first = new Node("first");
Node second = new Node("second");
Node third = new Node("third");
insertHead(head,third);
insertHead(head,second);
insertHead(head,first);
list(head);
}

结果如下:

尾插

尾插的话和单链表差不多,都是先找尾节点,然后把node放到尾节点的next域中,不过双向链表还要注意要把node的前驱节点设置为尾节点,代码如下:

1
2
3
4
5
6
7
8
9
//表尾插入
public void insertLast(Node head,Node node){
Node temp = head;//避免判断是否为空,如果用head.next且表为空,则下面的判断会报空指针异常
while (temp.next!=null){
temp = temp.next;
}
temp.next = node;
node.prev = temp;
}

测试一把:

1
2
3
4
5
6
7
8
9
//表尾插入方法测试
@Test
public void TestinsertLast(){
Node head = new Node();
insertLast(head,new Node("first"));
insertLast(head,new Node("second"));
insertLast(head,new Node("third"));
list(head);
}

结果和上一个结果一样。

表头删除

还是老样子,先判断是否为空;非空还要接着判断是否只含有一个元素,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
//表头删除
public void delHead(Node head){
if(isEmpty(head)){
throw new RuntimeException("链表为空,删除失败...");
}
//这个时候还得判断,双向链表是否只含有一个元素
if (head.next.next == null) {//只含有一个元素
head.next = null;
}else {
head.next = head.next.next;
head.next.prev = head;
}
}

测试一把:

1
2
3
4
5
6
7
8
9
10
11
12
13
public void TestDelHead(){
Node head = new Node();
insertLast(head,new Node("second"));
insertLast(head,new Node("third"));
insertHead(head,new Node("first"));
list(head);// first second third
delHead(head);
list(head);// second third
delHead(head);
list(head);//third
delHead(head);
list(head);//链表为空...
}

结果如下:

双向链表写这么多就可以了,还有一些方法基本都差不多。

单向环形链表

单向环形链表我们生活中的例子也不少,我们也得写一下,它和单链表相比,就是最后一个节点的指针指向头结点。

它的Node类和单链表的差不多,不过记得无参初始化的时候要把它的next域指向自己。具体如下:

1
2
3
4
5
6
7
8
9
10
class Node{
public String data;//数据
public Node next;//指向下一个节点
public Node(String data){
this.data = data;
}
public Node(){
this.next = this;//这是单向循环链表和其他链表的不同之处
}
}
是否为空
1
2
3
4
//判断是否为空
public static boolean isEmpty(Node head){
return head.next == head;
}

单向环形链表为空的话,那么head.next就是head。

遍历

和单链表一样,判断那个地方不是判断非空了,改成判断非head即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//遍历链表
public static void list(Node head){
if(isEmpty(head)){
System.out.println("链表为空...");
return;
}
//不能乱搞head节点,要借助辅助变量来遍历
Node temp = head.next;
while (temp!=head){
System.out.printf("%s\t",temp.data);
temp = temp.next;
}
System.out.println();
}
头插
1
2
3
4
5
6
7
8
9
10
11
//表头插入
public static void insertHead(Node head, Node node){
if(isEmpty(head)){//如果为空
head.next = node;
node.next = head;
}else {
Node temp = head.next;
head.next = node;
node.next = temp;
}
}

测试一把:

1
2
3
4
5
6
7
8
9
//测试头插方法
@Test
public void TestInsertHead(){
Node head = new Node();
insertHead(head,new Node("third"));
insertHead(head,new Node("second"));
insertHead(head,new Node("first"));
list(head);
}

结果如下:

尾插
1
2
3
4
5
6
7
8
9
//表尾插入
public void insertLast(Node head,Node node){
Node temp =head;
while (temp.next!=head){
temp = temp.next;
}
temp.next = node;
node.next = head;
}

测试一把:

1
2
3
4
5
6
7
8
9
@Test
//表尾插入测试
public void TestInsertLst(){
Node head = new Node();
insertLast(head,new Node("second"));
insertLast(head,new Node("third"));
insertHead(head,new Node("first"));
list(head);
}

结果和上一个一样。

表头删除
1
2
3
4
5
6
7
8
//表头删除
public void delHead(Node head){
if(isEmpty(head)){
System.out.println("链表为空,插入失败...");
return;
}
head.next = head.next.next;
}

测试一把:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//表头删除方法测试
@Test
public void TestDelHead(){
Node head = new Node();
insertHead(head,new Node("third"));
insertHead(head,new Node("second"));
insertHead(head,new Node("first"));
list(head);
delHead(head);
list(head);
delHead(head);
list(head);
delHead(head);
list(head);
}

面试题:将单链表反转

我们最后来个测试,做一道面试题:将单链表反转。我们先想想怎么办?

直接说怎么做了,我们先直接构造一个空节点作为一个新的头结点。然后遍历原链表,依次将链表中节点的数据用头插法插入到我们刚刚定义的那个新的头结点后面。最后将头结点的next域指向新的头结点的next域即可。大功告成!代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
//面试题:单链表的反转
public void reverse(Node head){
Node newHead = new Node();//新定义头结点
//遍历原链表,逐个头插
Node temp = head.next;
while (temp!=null){
Node t = new Node(temp.data);
insertHead(newHead,t);
temp = temp.next;
}
head.next = newHead.next;
}

测试一把:

1
2
3
4
5
6
7
8
9
10
11
12
13
//单链表反转测试
@Test
public void TestReverse(){
Node head = new Node();
insertLast(head,new Node("second"));
insertLast(head,new Node("third"));
insertHead(head,new Node("first"));
insertHead(head,new Node("111111"));
list(head);
System.out.println("将单链表反转...");
reverse(head);
list(head);
}

结果如下:

约瑟夫(Josephu)问题

设编号为1,2,3……n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,到m的那个人出列,它的下一位又从1开始报数,数到m的人又出列。以此类推,直到所有人出列为止,由此产生一个出对编号的序列。

这就是经典的约瑟夫问题,去年这个时候大二学数据结构,有一次上机考试的时候,就是这一道题。读完感觉这个问题很容易懂,感觉挺简单,然后让我自己写,写个锤子,毛都写不出来。

现在回过头再来看看这题,感觉应该是不算难的,反正我自己用Java写了半个小时,终于写了出来,嘿嘿嘿。

单链表解约瑟夫

这个问题就是相当于一群小孩子,然后一直出队。不用说,用什么数据结构去实现这个问题?肯定是环形链表了。

还得要说一点,这一次我们这个环形链表的头结点默认非空了,它就是第一个数值。

接下来,我们把出队这个操作作为函数,把链表、k、m这三个参数传入,怎么做?

  1. 先设置辅助变量,我们不能乱动头结点
  2. 根据k找到对应的开始的节点,即第一个开始报数的人
  3. 设置一个循环,跳出条件是链表只剩一个元素,即 temp.next!=temp
  4. 将temp定位到喊m的人前面一位,输出m的人的值,将m出队,即 temp.next= temp.next.next; ,接着temp还要指向下一次开始报数的人,即 temp = temp.next;
  5. 退出循环,此时环形链表只有一个人了,将次数据输出即可

好的,这就是基本思路,下面是代码部分:

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
//节点类
class Node{
public int data;
public Node next;
public Node(int data){
this.data = data;
}
}
public class JosephuDemo {
public static void main(String[] args) {
//约定头结点不为空
Node head = new Node(1);
Node temp = head;
for (int i = 2; i < 13; i++) {
temp.next = new Node(i);
temp = temp.next;
}
temp.next = head;//构成循环链表

out(head,5,3);
}

/***
* 约瑟夫出队函数
* @param head 链表头结点
* @param k 编号为k,从1开始
* @param m 报到m的人出列
*/
public static void out(Node head,int k,int m){
//辅助变量节点
Node temp = head;
//定位到开始报数的人
while (--k>0){
temp = temp.next;
}
while (temp.next!=temp){//一直出队,直到只剩下一个人
int t = m-1;
//定位到第一次数到m前的人
while (--t>0){
temp = temp.next;
}//记住现在这人是m-1,这样有利于我们删除m
//输出m那个人的值
System.out.printf("%d\t",temp.next.data);
//将m出队
temp.next= temp.next.next;
temp = temp.next;
}
//将最后一个人出队
System.out.printf("%d\t",temp.data);
}
}
公式法解约瑟夫

先把约瑟夫问题简化一下,把k去掉,直接从1开始,还有我们只求到最后的那个胜利者。

约瑟夫环是一个经典的数学问题,我们不难发现这样的依次报数,似乎有规律可循。为了方便导出递推式,我们重新定义一下题目。

问题: N个人编号为1,2,……,N,依次报数,每报到M时,杀掉那个人,求最后胜利者的编号。

这边我们先把结论抛出了。之后带领大家一步一步的理解这个公式是什么来的。

递推公式:f(N,M)= ( f(N-1,M)+M)% N

  • f(N,M)表示,N个人报数,每报到M时杀掉那个人,最终胜利者的编号
  • f(N-1,M)表示,N-1个人报数,每报到M时杀掉那个人,最终胜利者的编号

下面我们不用字母表示每一个人,而用数字。

1 2 3 4 5 6 7 8 9 10 11

表示11个人,他们先排成一排,假设每报到3的人被杀掉。

  • 刚开始时,头一个人编号是1,从他开始报数,第一轮被杀掉的是编号3的人。
  • 编号4的人从1开始重新报数,这时候我们可以认为编号4这个人是队伍的头。第二轮被杀掉的是编号6的人。
  • 编号7的人开始重新报数,这时候我们可以认为编号7这个人是队伍的头。第三轮被杀掉的是编号9的人。
  • ……
  • 第九轮时,编号2的人开始重新报数,这时候我们可以认为编号2这个人是队伍的头。这轮被杀掉的是编号8的人。
  • 下一个人还是编号为2的人,他从1开始报数,不幸的是他在这轮被杀掉了。
  • 最后的胜利者是编号为7的人。

下图表示这一过程(先忽视绿色的一行)

现在再来看我们递推公式是怎么得到的!

将上面表格的每一行看成数组,这个公式描述的是:幸存者在这一轮的下标位置*

  • f(1,3):只有1个人了,那个人就是获胜者,他的下标位置是0
  • f(2,3)=(f(1,3)+ 3)% 2 = 3 % 2 = 1:在有2个人的时候,胜利者的下标位置为1
  • f(3,3)=(f(2,3)+ 3)% 3 = 4 % 3 = 1:在有3个人的时候,胜利者的下标位置为1
  • f(4,3)=(f(3,3)+ 3)% 4 = 4 % 4 = 0:在有4个人的时候,胜利者的下标位置为0
  • …….
  • f(11,3)= 6

理解这个递推式的核心在于关注胜利者的下标位置是怎么变的。

没杀掉一个人,下一个人成为头,其实就是把整个数组往前移动M位。

看上面每一行最后一个人的运行轨迹(蓝颜色的),已知 f(N,M),顺着我们可以推出 f(N-1,M):

f(N-1,M)= ( f(N,M)- M)% (N-1)

我们逆着推,已知 f(N,M)可以推出 f(N+1,M):

f(N+1,M)= ( f(N,M)+M)%(N+1)

我们把上面的N用N-1代替,N+1用N代替,于是就变成:

f(N,M)= ( f(N-1,M)+M)% N

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class JosephuDemo2 {
/***
* 一共n个人,从第1个人开始从1报数,报m的人出队,依次类推
* 返回最后的胜利者的数组下标,数组下标从0开始算
*/
public static int winner(int n,int m){
int win = 0;//一个人为0,废话,就特么这一个
//采用递推方法
for (int i = 2; i <= n; i++) {
win = (win+m) % i;
}
return win;
}

public static void main(String[] args) {
System.out.println(winner(12,3)); //9
System.out.println(winner(11,3)); //6
}
}
存入List法解约瑟夫

上面如果能看懂的话,我们再思考一下,把这些1到n存到List数组中,然后通过不断遍历删除对应值。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.ArrayList;
public class JosephuDemo3 {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 1; i <= 12; i++) {
list.add(i);
}
josephu(list,3);
}
public static void josephu(ArrayList<Integer> list,int m){
int k = -1;
while (list.size()>0){
k = k+m;//向后移动m位
k = k%(list.size());//越界之后要用取余
//否则,直接输出k对应的元素
System.out.print(list.get(k)+" ");
list.remove(k--);//将对应元素删除,并将k--
}
}
}

输出结果如下: