前言

b 站 Java 数据结构学习笔记整理。尚硅谷 Java 数据结构与 java 算法（Java 数据结构与算法）

感觉还是自己写的例子好理解一些。不会附上老师的代码。

1. 链表

  1. 链表是以结点的方式来存储
  2. 每个节点包含 data 域，next 域（当然，这个节点有自己的内存地址）。
  3. 链表的各个节点不一定是连续存储。
  4. 链表分带头节点的链表和没有头结点的（头结点就一个指针指向地址，没 data）
  5. 头结点没有数据

链表的逻辑结构

链表的逻辑结构

注意，链表的逻辑结构是连续的，但是在实际的内存存储中并不是按地址连续存储的。

2. 单链表

2.1 单链表的创建:

定义一个节点类，这个节点类有成员变量 Data，和一个成员变量 next，其中 next 代表的是它所连接的下一个该类的节点。

定义一个链表类，这个链表类有一个初始的头结点，还有一个 add 添加方法，一个 list 遍历方法。

代码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package 单链表;

public 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 + '\'' +
                '}';
    }
}

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package 单链表;

import java.util.Stack;

public class SingleLinkedList {
    private HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
        return head;
    }

    public void add(HeroNode heroNode) {
    }



    public void list() {
    }
}

2.2 单链表的遍历：

  • 如果头结点的 next 为空，证明该链表为空链表，直接返回

Head

Unsupported markdown: list
  • 如果头结点 next 不为空，定义一个 current 指针，指向头结点的下一个节点，也就是真正有值的第一个节点处。

current

Head

A

B

C

  • 当 current 指针指向的当前节点不为 null 时，打印这个节点，并右移 current 指针。

current

Head

A

B

C

current

Head

A

B

C

  • 当 current 指针指向 null 时，打印结束。

current

Head

A

B

C

Unsupported markdown: list

代码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void list() {
    // 如果头结点指向的下一个节点为空，证明链表为空
    if (head.next == null) {
        System.out.println("链表为空");
    } else {
        // 链表不为空，定义一个current指针，指向第一个有信息的节点
        HeroNode current = head.next;
        // 如果current指针指向的节点不为null（有意义）
        while (current != null) {
            //输出这个current指针指向的节点
            System.out.println(current);
            //指针右移
            current= current.next;
        }
    }
}

2.3 单链表的添加：

  • 现在有一个链表和待插入的节点 C 如图所示：

Head

A

B

C

  • 定义一个头结点位置处的指针 temp

temp

Head

A

B

C

  • 当 temp 指针指向的不是尾节点时，右移 temp 指针，直到到达尾节点处

temp

Head

A

B

C

  • 将 temp 指针指向的节点连接到新插入的节点 C

temp

Head

A

B

C

2.4 单链表的按顺序添加

** 关键的事实：** 比如往列表 {1, 2, 3, 4, 6, 7, 8, 9} 中添加 5，那么只需要从头开始遍历列表，直到找到比 5 大的位置 6，然后把 5 插到 6 的前面就行了。就像打扑克一样。

  • 现在有一个链表和待插入的节点 5：

1

2

3

4

6

7

8

9

Head

5

  • 定义一个指针 temp，指向 head

1

2

3

4

6

7

8

9

temp

Head

5

  • 当 temp 指向的节点不是尾节点时，开始循环，希望通过循环找到待插入的位置。
    • 比较 temp 指向的节点的下一个节点的值是否比 5 大，如果不比 5 大，就指针右移；
    • 如果比 5 大，就退出循环，指针的指向就是我们要找的待插入的位置。
    • 在循环过程中，如果指针指向的节点的值和待插入的节点的值相同，那就重复了。不插入重复的节点。直接 return。

1

2

3

4

6

7

8

9

temp

Head

5

  • 在 temp 处插入元素

    • 当 temp 指向的节点是尾节点（即上述的循环过程根本就没进行，或者遍历了整个列表也没找到合适的位置时），就直接在 temp 处插入（此刻 temp 指向的是尾节点）。

    • 当 temp 指向的节点不是尾节点，那也直接在 temp 直接插入，因为此时 temp 指向的是待插入的位置。

temp

Head

5

1

2

temp

Head

9

  • 回到上面那个案例，插入时，将待插入的节点连接 temp 指针指向的节点的下一个节点，并将 temp 指针指向的节点连接到插入的节点：

1

2

3

4

5

6

7

8

9

temp

Head

1

2

3

4

5

6

7

8

9

temp

Head

代码（在上文基础上）：

java
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

public void addByOrder(HeroNode heroNode) {
    // 定义一个指针temp，指向head
    HeroNode temp = head;
    // 定义一个布尔值表示是否有该编号的数据了
    // 找到待插入的位置
    // 如果该指针指向的节点是尾节点，那就不用遍历了(没啥可找的了，就在末尾插入)，直接break。
    while (temp.next != null) {
        // 如果temp指针指向的节点的下一个节点比待插入的节点数字大，
        // 那这个指针指向的节点就是我们想要的
        if (temp.next.no == heroNode.no) {
            System.out.println("待插入的英雄的编号" + heroNode.no + "已经存在，不能插入\n" + heroNode.no);
            return;
        }
        if (temp.next.no > heroNode.no) {
            // 位置找到了
            break;
        }
        // 指针右移
        temp = temp.next;
    }

    heroNode.next = temp.next;
    temp.next = heroNode;

}

2.5 单链表节点的修改

修改节点信息，根据编号来改，编号本身不能改（类似于学号）。

使用上文中提到的遍历来实现。如果编号和要修改的节点相同，那就修改，然后 return。

代码:

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void update(HeroNode newHeroNode) {
    if (head.next == null) {
        System.out.println("链表为空");
    }
    HeroNode current = head.next;
    while (current != null) {
        if (current.no == newHeroNode.no) {
            current.name = newHeroNode.name;
            current.nickname = newHeroNode.nickname;
            return;
        }
        current = current.next;
    }
    System.out.println("未找到该编号下的节点" + newHeroNode.no);
}

2.6 单链表节点的删除

  1. 找到需要删除的节点的前一个结点 temp
  2. temp.next = temp.next.next;
  3. 被删除的结点不会被引用，会被垃圾回收机制删除
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void delete(int no) {
    HeroNode temp = head;
    boolean flag = true;
    while (temp.next != null) {
        if(temp.next.no == no){
            flag = false;
            temp.next = temp.next.next;
            break;
        }
        temp = temp.next;
    }
    if(flag){
        System.out.println("未找到需要删除的元素");
    }
}

之前的那个学生管理系统是用 ArrayList 做的。

3. 单链表新浪面试题 - 查找倒数第 k 个

前菜：求单链表中有效节点的个数。

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int size(HeroNode head){
    if (head.next == null) {
        System.out.println("链表为空");
        return 0;
    }else{
        int size = 0;
        HeroNode temp = head;
        while(temp.next!=null){
            temp = temp.next;
            size++;
        }
        return size;
    }
}

链表中的 head 就代表了整个链表。

新浪面试题：查找单链表中的倒数第 k 个节点。

单链表不可能从后往前遍历，所以应该先把整个列表遍历，看看一共有几个节点，倒数第 k 个就是正数 length-k 个。

定义一个指针 temp，然后拖动指针遍历的方法真的很有用！
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public HeroNode getNode(HeroNode head, int index) {
    if (head.next == null) {
        return null;
    }
    int size = size(head);
    if (index <= 0 || index > size) {
        return null;
    }
    int goalPosition = size - index + 1;
    int count = 0;
    HeroNode temp = head;
    while (temp.next != null) {
        count++;
        temp = temp.next;
        if (count == goalPosition) {
            return temp;
        }

    }
    return null;
}

4. 腾讯面试题 - 单链表的反转

需求：单链表的反转

解决思路（头插法）:

  • 现有一个链表：

    Head

    A

    B

    C

  • 定义一个辅助的头结点 reverseHead

    Head

    A

    B

    C

    reverseHead

  • 从头到尾遍历原来的链表，每遍历一个节点，就将其取出，放在辅助头结点所在的新链表的最前端。

    Head

    B

    C

    reverseHead

    A

Head

C

reverseHead

B

A

Head

reverseHead

C

B

A

  • 让 head 节点指向 reverseHead 链表中的第一个节点，并将 reverseHead 指向 null

Head

C

reverseHead

B

A

  • 结果

Head

C

B

A

代码实现：

老师的代码，晦涩，难懂（他好像自己都不理解，是背下来的），根本讲不明白…… 他说这题难，如果是听他讲好像是挺难 = = 最后还是没理解他的代码，自己写了一个。

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void reverseList(HeroNode head) {
    if (head.next == null || head.next.next == null) {
        return;
    }
    HeroNode current =  head.next;
    HeroNode reverseHead = new HeroNode(0,"","");
    while(current!=null){
        head.next = current.next;

        HeroNode jointNode = reverseHead.next;
        reverseHead.next = current;
        current.next = jointNode;

        current = head.next;
    }
    head.next = reverseHead.next;
    reverseHead.next = null;

}

原理就是上面的流程图图解。

6. 百度面试题 - 从尾到头打印单链表

要求：从尾到头打印单链表

方式 1：反转单链表，再遍历（会改变链表的结构，不推荐）

方式 2：将各个节点压入栈中，利用栈的先进后出实现逆序打印。

Java 中栈的小演示：

java
1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.add("1");
        stack.add("2");
        stack.add("3");
        
        while(stack.size()>0){
            System.out.println(stack.pop());
        }

    }

使用方式 2 实现从尾到头打印单链表。

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public  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;
    }
    while(stack.size()>0){
        System.out.println(stack.pop());
    }
}

注意，没有改变链表本身的顺序，只不过是用栈这个机制打印的。

7. 双向链表

就是有一个 pre 指向前面节点的地址。

双向链表的增删改查：

  • 遍历：和单向的一样，可以向前，也可以向后。
  • 添加：默认添加到双向链表最后，和单项一样。
    • 先找到最后节点
    • temp.next = newHeroNode
    • newHeroNode.pre = temp
  • 修改：修改思路和单项链表一样
  • 删除
    • 因为是双向链表，所以可以实现正向或者反向删除某个节点
    • 找到要删除的 temp 节点
    • temp.pre.next = temp.next
    • temp.next.pre = temp.pre
java
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
package 双链表;

public class doubleLinkedList {
    private HeroNode head = new HeroNode(0, "", "");
    public HeroNode getHead() {
        return head;
    }
    public void add(HeroNode heroNode) {
        //当不考虑编号的顺序时，找到当前链表的最后节点，将这个节点的next指向新的节点。
        HeroNode temp = head;
        // 遍历链表
        while (temp.next != null) {
            // next是成员变量，代表着下一个节点HeroNode
            temp = temp.next;
        }
        temp.next = heroNode;
        heroNode.pre = temp;
    }
    public void list() {
        // 如果头结点为空，证明链表为空
        if (head.next == null) {
            System.out.println("链表为空");
        } else {
            // 头结点不为空，头结点的下一个节点（包含data的节点）是temp
           HeroNode temp = head.next;
            // 如果它的下一个节点存在，也就是如果这个temp不是尾节点
            while (temp != null) {
                //输出这个temp节点
                System.out.println(temp);
                // temp指针指向下一个节点
                temp = temp.next;
            }
        }
    }

    public void update(HeroNode newHeroNode) {
        if (head.next == null) {
            System.out.println("链表为空");
        }
        HeroNode temp = head.next;
        boolean flag = true;
        while (temp != null) {
            if (temp.no == newHeroNode.no) {
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
                flag = false;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.println("未找到该编号下的节点" + newHeroNode.no);
        }
    }
    public void delete(int no) {
        if(head.next == null){
            System.out.println("链表为空，无法删除");
            return;
        }

        HeroNode current = head.next;
        boolean flag = true;
        while (current != null) {
            if (current.no == no) {
                flag = false;
                current.pre.next = current.next;
                if(current.next!=null){
                    current.next.pre = current.pre;
                }
                break;
            }
            current = current.next;
        }
        if (flag) {
            System.out.println("未找到需要删除的元素");
        }
    }

}

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package 双链表;


public class test {
    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,"林冲","豹子头");

        doubleLinkedList doubleLinkedList = new doubleLinkedList();
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
        doubleLinkedList.add(hero4);

        HeroNode newHero4= new HeroNode(4,"孙健耕","啥也不是");
        doubleLinkedList.update(newHero4);

        doubleLinkedList.delete(4);
        doubleLinkedList.list();
    }
}

8. 环形链表 - 约瑟夫问题

约瑟夫问题：设编号为 1，2，…n 的人围坐在一圈，约定编号为 k 的人从 1 开始报数，报到 m 的那个人出列，直到所有人都出列。求出列顺序。

解题思路：

  • 定义一个 helper 指针和一个 current 指针，分别指向最末端和第一个节点。

current

helper

A

B

C

D

E

  • 将 helper 指针和 current 指针指向当前需要报数（也就是第 K 个）人处，helper 始终在 current 的后一位（这里假设从第 1 一个人开始报数，那指针就不用移动了）

current

helper

A

B

C

D

E

  • 报 m 个数，比如 m=2（注意，current 指向的节点会报 "1"，所以只需要移动一次）

current

helper

A

B

C

D

E

  • 将 current 指针右移

current

helper

A

B

C

D

E

  • 将 helper 指针指向的节点 A 连接到当前 current 指针指向的节点 C

current

helper

B

C

D

E

A

  • 打印（取出）B 节点。

current

helper

C

D

E

A

B

完整代码：

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package 单向环型表;

public class Boy {
    private int no;
    private Boy next;

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    public Boy(int no){
        this.no = no;
    }

    public int getNo() {
        return no;
    }
}

java
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
package 单向环型表;

public class CircleSingleLinkedList {
    private Boy first = null;

    public void addBoy(int nums) {
        if (nums < 1) {
            System.out.println("输入的值有误");
            return;
        }
        Boy curBoy = null;
        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            if (i == 1) {
                first = boy;
                first.setNext(first);
                curBoy = first;
            } else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }

    public void showBoy() {
        if (first == null) {
            System.out.println("链表为空");
            return;
        }
        Boy curBoy = first;
        while (true) {
            System.out.println("小孩编号" + curBoy.getNo());
            if (curBoy.getNext() == first) {
                break;
            }
            curBoy = curBoy.getNext();
        }
    }

    public void countBoy(int startNo, int countNum, int nums) {
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("数据不合理");
            return;
        }
        Boy helper = first;
        while (helper.getNext() != first) {
            helper = helper.getNext();
        }

        for (int j = 0; j < startNo - 1; j++) {
            first = first.getNext();
            helper = helper.getNext();
        }

        while (helper != first) {
            for (int j = 0; j < countNum - 1; j++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.println(first.getNo());
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.println(first.getNo());
    }

}
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
package 单向环型表;

public class josephu {
    public static void main(String[] args) {
        CircleSingleLinkedList cl = new CircleSingleLinkedList();

        cl.addBoy(5);
        cl.showBoy();

        cl.countBoy(1,2,5);

    }
}