前言

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

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

1. 链表

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

链表的逻辑结构

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

2. 单链表

2.1 单链表的创建:

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

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

代码：

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

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为空，证明该链表为空链表，直接返回
flowchart LR Head-.-x*
  • 如果头结点next不为空，定义一个current指针，指向头结点的下一个节点，也就是真正有值的第一个节点处。
flowchart LR Head-->A-->B-->C 1((current))-.->A
  • 当current指针指向的当前节点不为null时，打印这个节点，并右移current指针。
flowchart LR Head-->A-->B-->C 1((current))-.->A
flowchart LR Head-->A-->B-->C 1((current))-.->B
  • 当current指针指向null时，打印结束。
flowchart LR Head-->A-->B-->C--x* 1((current))-.->*

代码：

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如图所示：
flowchart LR Head-->A-->B C
  • 定义一个头结点位置处的指针temp
flowchart LR 1((temp))-.->Head-->A-->B C
  • 当temp指针指向的不是尾节点时，右移temp指针，直到到达尾节点处
flowchart LR Head-->A-->B 1((temp))-.->B C
  • 将temp指针指向的节点连接到新插入的节点C
flowchart LR Head-->A-->B-->C 1((temp))-.->B

2.4 单链表的按顺序添加

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

  • 现在有一个链表和待插入的节点5：
flowchart LR Head-->1-->2-->3-->4-->6-->7-->8-->9 id[5]
  • 定义一个指针temp，指向head
flowchart LR 111((temp))-.->Head Head-->1-->2-->3-->4-->6-->7-->8-->9 id[5]
  • 当temp指向的节点不是尾节点时，开始循环，希望通过循环找到待插入的位置。
    • 比较temp指向的节点的下一个节点的值是否比5大，如果不比5大，就指针右移;
    • 如果比5大，就退出循环，指针的指向就是我们要找的待插入的位置。
    • 在循环过程中，如果指针指向的节点的值和待插入的节点的值相同，那就重复了。不插入重复的节点。直接return。
flowchart LR 111((temp))-.->4 Head-->1-->2-->3-->4-->6-->7-->8-->9 id[5]

  • 在temp处插入元素

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

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

flowchart LR 111((temp))-.->Head Head id[5]
flowchart LR 111((temp))-.->2 Head-->1-->2 id[9]
  • 回到上面那个案例，插入时，将待插入的节点连接temp指针指向的节点的下一个节点，并将temp指针指向的节点连接到插入的节点：
flowchart LR 111((temp))-.->4 Head-->1-->2-->3-->4-->6-->7-->8-->9 5-->6
flowchart LR 111((temp))-.->4 Head-->1-->2-->3-->4 6-->7-->8-->9 4-->5 5-->6

代码（在上文基础上）：

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。

代码:

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. 被删除的结点不会被引用，会被垃圾回收机制删除
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个

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

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，然后拖动指针遍历的方法真的很有用！ 
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. 腾讯面试题-单链表的反转

需求: 单链表的反转

解决思路（头插法）:

  • 现有一个链表：

    flowchart LR Head-->A-->B-->C

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

    flowchart LR Head-->A-->B-->C reverseHead

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

    flowchart LR Head-->B-->C reverseHead-->A

flowchart LR Head-->C reverseHead-->B-->A
flowchart LR Head reverseHead-->C-->B-->A
  • 让head节点指向reverseHead链表中的第一个节点，并将reverseHead指向null
flowchart LR Head-->C reverseHead--xC-->B-->A
  • 结果
flowchart LR Head-->C C-->B-->A

代码实现：

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

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中栈的小演示：

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实现从尾到头打印单链表。

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
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("未找到需要删除的元素");
        }
    }

}

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指针，分别指向最末端和第一个节点。
flowchart LR A-->B-->C-->D-->E-->A 1((current))-.->A 2((helper))-.->E
  • 将helper指针和current指针指向当前需要报数（也就是第K个）人处，helper始终在current的后一位（这里假设从第1一个人开始报数，那指针就不用移动了）
flowchart LR A-->B-->C-->D-->E-->A 1((current))-.->A 2((helper))-.->E
  • 报m个数，比如m=2（注意，current指向的节点会报"1"，所以只需要移动一次）
flowchart LR A-->B-->C-->D-->E-->A 1((current))-.->B 2((helper))-.->A
  • 将current指针右移
flowchart LR A-->B-->C-->D-->E-->A 1((current))-.->C 2((helper))-.->A
  • 将helper指针指向的节点A连接到当前current指针指向的节点C
flowchart LR B-->C-->D-->E-->A-->C 1((current))-.->C 2((helper))-.->A
  • 打印（取出）B节点。
flowchart LR C-->D-->E-->A-->C 1((current))-.->C 2((helper))-.->A B

完整代码：

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

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

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

    }
}