【备注】2026年3月10日开始学习数据结构与算法，参考B站视频学习。

本节拖拖拉拉，耗时8天才学完，服了自己。

稀疏数组 sparsearray


使用数组来储存棋盘情况

因为该二维数组的很多值是默认值0, 因此记录了很多没有意义的数据.

稀疏数组的意义

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

稀疏数组的处理方法是:

  1. 记录数组一共有几行几列，有多少个不同的值
  2. 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模.
  3. 假设原数组中有n个特殊值，则对应的稀疏数组一般有n+1行，3 列。其中第一行依次储存原始数组的行数、列数、有多少个不同的值；后面的行数依次记录每个不同的值所在的行数、列数、值。

稀疏数组

思路分析


思路分析图
  1. 先将二维数组保存为稀疏数组

（1）遍历原始的二维数组，得到有效数组的个数 sum

（2）根据 sum创建稀疏数组 ： 

1
int[][] sparseArr = int[sum+1][3];

（3）根据稀疏数组的定义，依次填写稀疏数组的值

假设原数组中有n个特殊值，则对应的稀疏数组一般有n+1行，3 列。其中第一行依次储存原始数组的行数、列数、有多少个不同的值；后面的行数依次记录每个不同的值所在的行数、列数、值。

  1. 稀疏数组还原为二维数组

（1）先根据稀疏数组的第一行，创建原始数组。

（2）然后再读取稀疏数组的后面几行数据，并赋值给原始的二维数组即可。

代码实现

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
public class sparsearr {
    public static void main(String[] args){
        //创建原始数组
        int[][] arr1 = new int[6][7];
        arr1[0][3] = 22;
        arr1[0][6] = 15;
        arr1[1][1] = 11;
        arr1[1][5] = 17;
        arr1[2][3] = -6;
        arr1[3][5] = 39;
        arr1[4][0] = 91;
        arr1[5][2] = 28;

        //遍历打印原始数据，确保无误
        System.out.println("原始数组");
        for(int[] row : arr1){
            for(int data : row){
                System.out.print(data+"\t");
            }
            System.out.println();
        }

        //计算原始数组中一共有几个特殊值需要储存
        int count = 0;
        for(int i=0 ; i<arr1.length ; i++){
            for(int j=0 ; j<arr1[i].length ; j++){
                if(arr1[i][j] !=0){
                    count++;
                }
            }
        }
        System.out.printf("原始数组中一共有%d个特殊值",count);
        
        //开始创建稀疏数组
        int[][] arr2 = new int[count+1][3];
        arr2[0][0] = 6;
        arr2[0][1] = 7;
        arr2[0][2] = count;

        int row = 1;
        for(int m=0; m<arr1.length ;m++){
            for(int n=0; n<arr1[m].length ;n++){
                if(arr1[m][n] !=0){
                    arr2[row][0] = m;
                    arr2[row][1] = n;
                    arr2[row][2] = arr1[m][n];
                    row++;
                }
            }
        }


        System.out.println("稀疏数组");
        for(int[] r : arr2){
            for(int data : r){
                System.out.print(data+"\t");
            }
            System.out.println();
        }
    }
}

队列 Queue

队列介绍

  1. 队列是一个有序列表，可以用数组或是链表来实现。
  2. 遵循先入先出（FIFO）的原则。即：先存入队列的数据，要先取出。后存入的要后取出。队列像排队买票

数组队列

  • 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中maxSize 是该队
    列的最大容量。
  • 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front 及rear 分别记录队列前后端的下标，
    front 会随着数据输出而改变，而rear 则是随着数据输入而改变，如图所示

数组模拟队列示意图
  • 当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思路分析
  1. 将尾指针往后移：rear+1 , 当front == rear 【空】
  2. 若尾指针rear 小于队列的最大下标maxSize-1，则将数据存入rear 所指的数组元素中，否则无法存入数据。
    rear == maxSize - 1[队列满]

数组模拟队列-代码实现

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
//使用数组模拟队列
import java.util.Scanner;
public class Queue {
    public static void main(String[] args){
        //测试代码
        ArrayQueue queue = new ArrayQueue(3);
        char key = ' '; //等待用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        //输出一个菜单
        while(loop){
            System.out.println("s(show):显示队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列取出数据");
            System.out.println("h(head):查看队列头的数据");
            key = scanner.next().charAt(0); //接收一个字符
            switch (key) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("输入一个数，添加到数组中");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g': //取出数据
                    try {
                        int res = queue.getQueue();
                        System.out.println("取出的数据为"+res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());            
                    }
                    break;
                case 'h':
                    try {
                        int res = queue.headQueue();
                        System.out.println("队列头的数据为："+res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序结束啦！");
    }

    //使用数组模拟队列，编写一个 ArrayQueue 类
    static  class ArrayQueue{
      private int maxSize; //表示最大容量
      private int front; //表示队列头
      private int rear; //表示队列尾
      private int[] arr; //存放数据，模拟队列
      
      //创建队列的构造器
      public ArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1 ;//指向队列头的前一个位置
        rear = -1; //指向队列尾的最后一个数据

      }

      //判断队列是否满
      public boolean isFull(){
        return rear == maxSize -1;
      }

      //判断队列是否为空
      public boolean isEmpty(){
        return rear==front;
      }

      //添加数据到队列
      public void addQueue(int n){
        //首先需要判断队列是否满
        if(isFull()){
            System.out.println("队列排满，不能加入数据~");
            return;
        }
        rear++;//让 rear 往后移
        arr[rear] = n;
      }

      //获取队列的数据，出队列
      public int getQueue(){
        //首先需要判断队列是否为空
        if(isEmpty()){
            System.out.println("队列为空，不能取数据");
            //抛出异常
            throw new RuntimeException("队列空，取不了数据啊！");
        }
        front++; //front后移
        return arr[front];
        
      }

      //显示队列所有数据
      public void showQueue(){
        if(isEmpty()){
            System.out.println("队列数据为空！");
            return;
        }
        for(int i=0; i<arr.length ; i++){
            System.out.printf("arr[%d] = %d \n",i,arr[i]);
        }
      }

      //显示队列的头数据，不需要取出数据
      public int headQueue(){
        //判断是否为空
        if(isEmpty()){
            throw new RuntimeException("队列是空的，没有数据！");
        }
        return arr[front + 1];
      }
    }

}

数组模拟循环队列

思路分析

对前面的数组模拟队列的优化，充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)

  • 分析说明：
  1. 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的
    时候需要注意(rear + 1) % maxSize == front 满]
  2. rear == front [空]
  3. 分析示意图:

数组模拟循环队列示意图

代码实现

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
import java.util.Scanner;

public class CircleQueue {
    public static void main(String[] args){
        Circle queue = new Circle(5);
        char num = ' ';
        boolean loop = true;
        Scanner scanner = new Scanner(System.in);

        while(loop){
            System.out.println("s(show):显示队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列取出数据");
            System.out.println("h(head):查看队列头的数据");
            num = scanner.next().charAt(0); //接收一个字符

            switch (num) {
                case 's':
                    try {
                        queue.showArr();
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                case 'a':
                    
                    try {
                        System.out.println("请输入一个数：");
                        int value = scanner.nextInt();
                        queue.addCircle(value);
                        System.out.println("添加数据成功~");
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'g':
                    try {
                        int e = queue.getQueue();
                        System.out.println("取出的数据为"+e);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 'h':
                    try {
                        int e = queue.headArr();
                        System.out.println("队列头数据为"+e);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序结束啦！");
    }
    

    //使用循环数组模拟循环队列
    static class Circle{
        private int maxSize;
        private int[] circleArr;
        private int front;
        private int rear;

        //创建构造器

        public Circle(int arrmaxSize){
            maxSize = arrmaxSize;
            circleArr = new int[maxSize];
            front = rear =0;
        }
    
        //判断队列是否排满
        public boolean isFull(){
            return front == (rear + 1)%maxSize;
        }

        //判断队列是否为空
        public boolean isEmpty(){
            return rear == front ;
        }

        //添加数据到队列
        public void addCircle(int a){
            if(isFull()){
                throw new RuntimeException("队列已排满啦！");
            }
            rear = (rear+1)%maxSize;
            circleArr[rear] = a;
        }

        //取出数据
        public int getQueue(){
            if(isEmpty()){
                throw new RuntimeException("队列是空的，你咋取数据？");
            }
            front = (front + 1)%maxSize;
            return circleArr[front];
        }

        //显示队列所有数据
        public void showArr(){
            if(isEmpty()){
                throw new RuntimeException("队列数据是空的啊，我给你展示个啥？");
            }
            int count = (rear - front + maxSize)%maxSize;

            for(int i=0 ; i<count  ;i++){
                int index = (front + 1 + i)%maxSize;
                System.out.printf("circleArr[%d]=%d",index,circleArr[index]);
                System.out.println();
            }
        }

        //显示队列的头数据，但不取出数据
        public int headArr(){
            if(isEmpty()){
                throw new RuntimeException("队列数据是空的啊，头数据自然没有啊！");
            }
            return circleArr[(front+1)%maxSize];
        }
    }
}

单链表

背景及定义

链表是有序的列表，但是它在内存中是存储如下


单链表示意图
小结:
  1. 链表是以节点的方式来储存,是链式储存.
  2. 每个节点包含 data 域 , next 域. next域作用: 指向下一节点.
  3. 如图发现, 链表的各个节点不一定是连续储存.
  4. 链表分为带头节点和无头节点的链表, 根据实际开发需要自行选择.

单链表(带头节点)逻辑结构示意图如下:


应用实例1 简单添加

使用带 head 头的单项列表实现 水浒英雄排行榜的管理以及对英雄人物的增删改查操作 .

(1) 新添英雄时,直接添加到链表的尾部



思路分析图

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
public class SingleLinkedListDemo {

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 heroList = new SingleLinkedList();
    heroList.add(hero1);
    heroList.add(hero2);

    heroList.add(hero3);

    heroList.add(hero4);
 
    //显示链表
    heroList.list();
}



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

    public void add(HeroNode heroNode){
        //因为头节点不能动，需要一个变量temp辅助遍历
        HeroNode temp = head;

        //开始遍历，找到链表的最后一个节点
        while(true){
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }

        //当跳出循环时，temp 指向链表的最后一个节点
        //将这个最后节点的next 指向 新的节点，完成节点的新增
        temp.next = heroNode;
    }

    //遍历链表
    public void list(){
        //判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空！");
            return;
        }

        HeroNode temp = head.next;
        while (true) {
            
            System.out.println(temp);
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }
    }
}


//定义  HeroNode , 每个HeroNode 对象就是链表上的一个节点
static class HeroNode{
    public int number;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一节点

    //构造器
    public HeroNode(int num,String name,String nickname){
        this.number = num;
        this.name = name;
        this.nickname = nickname;
    }

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

应用实例2 顺序添加

按英雄编号的顺序插入英雄列表: (若该编号已存在则提示无法插入)

  1. 先找到新节点需要插入的位置. 设置一个temp变量, 当temp 的下一节点的编号大于新节点的编号,则说明找到了该位置.

  2. 问题处理: temp的下一节点的编号与新节点的编号无非存在三种关系, 大于 等于 小于,

    如果 temp.next.number < 新节点.number , 则不用处理, 继续操作temp的下一节点.

    如果 temp.next.number = 新节点.number , 提示无法添加.

    如果 temp.next.number > 新节点.number , 可以添加.

  3. 添加新节点的方法

    (1) 将新节点的 next 指向 temp的下一节点: 新节点.next = temp.next

    (2) 再将temp的 next 指向 新节点: 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
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
public class SingleLinkedListDemo2 {

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 heroList = new SingleLinkedList();
    heroList.add(hero1);
    heroList.add(hero3);
    heroList.add(hero2);
    heroList.add(hero4);
 
    //显示链表
    heroList.list();
}


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

    public void add(HeroNode heroNode){
        //因为头节点不能动，需要一个变量temp辅助遍历
        HeroNode temp = head;
        boolean flag = false;
        //开始遍历，找到链表中需要插入的位置
        while(true){
            if(temp.next == null){
                break;
            }
            else if (temp.next.number > heroNode.number) {
                break;
            }
            else if(temp.next.number == heroNode.number){
                flag = true;//该编号已存在
                break;
            }
            temp = temp.next;
        }
        if(flag){
            //说明
            System.out.printf("编号%d已存在，无法添加",heroNode.number);
        }
        else{
            //当跳出循环时，新节点的next 指向 temp 的下一个节点
            //temp的next 指向新节点
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }

    //遍历链表
    public void list(){
        //判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空！");
            return;
        }

        HeroNode temp = head.next;
        while (true) {
            
            System.out.println(temp);
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }
    }
}


//定义  HeroNode , 每个HeroNode 对象就是链表上的一个节点
static class HeroNode{
    public int number;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一节点

    //构造器
    public HeroNode(int num,String name,String nickname){
        this.number = num;
        this.name = name;
        this.nickname = nickname;
    }

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

应用实例3 修改节点

修改指定编号节点的信息

  1. 遍历链表, 找到对应编号的节点
  2. 直接修改节点的 name 和 nickname 属性
  3. 找到后立即 break
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
//按照英雄编号顺序创建单列表
//修改指定编号英雄信息
public class SingleLinkedListDemo3 {

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 heroList = new SingleLinkedList();
    heroList.add(hero1);
    heroList.add(hero3);
    heroList.add(hero2);
    heroList.add(hero4);
 
    //显示链表
    heroList.list();
    HeroNode newHero = new HeroNode(3,"没有用","智少");
    heroList.change(newHero);
    System.out.println("修改后的列表信息");
    heroList.list();

}
 

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

    public void add(HeroNode heroNode){
        //因为头节点不能动，需要一个变量temp辅助遍历
        HeroNode temp = head;
        boolean flag = false;
        //开始遍历，找到链表中需要插入的位置
        while(true){
            if(temp.next == null){
                break;
            }
            else if (temp.next.number > heroNode.number) {
                break;
            }
            else if(temp.next.number == heroNode.number){
                flag = true;//该编号已存在
                break;
            }
            temp = temp.next;
        }
        if(flag){
            //说明
            System.out.printf("编号%d已存在，无法添加",heroNode.number);
        }
        else{
            //当跳出循环时，新节点的next 指向 temp 的下一个节点
            //temp的next 指向新节点
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }

    //修改信息
    public void change(HeroNode newHeroNode){
        HeroNode temp = head.next;
        boolean flag = false;
        while(true){
            if(temp == null){
                break;
            }
            if(temp.number == newHeroNode.number){
                System.out.println("找到了需要修改的英雄");
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
                flag = true;
            }
            temp = temp.next;
        }
        if (!flag) {
            System.out.printf("你输入的编号%d有误，列表中未找到\n",newHeroNode.number);
        }

    }

    //遍历链表
    public void list(){
        //判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空！");
            return;
        }

        HeroNode temp = head.next;
        while (true) {
            
            System.out.println(temp);
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }
    }
}


//定义  HeroNode , 每个HeroNode 对象就是链表上的一个节点
static class HeroNode{
    public int number;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一节点

    //构造器
    public HeroNode(int num,String name,String nickname){
        this.number = num;
        this.name = name;
        this.nickname = nickname;
    }

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

应用实例4 删除节点

  1. 找到待删除节点的 前驱节点 temp
  2. 删除逻辑: temp.next = temp.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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
//按照英雄编号顺序创建单列表
//修改指定编号英雄信息
//删除指定节点
public class SingleLinkedListDemo4 {

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 heroList = new SingleLinkedList();
    heroList.add(hero1);
    heroList.add(hero3);
    heroList.add(hero2);
    heroList.add(hero4);
 
    //显示链表
    heroList.list();
    HeroNode newHero = new HeroNode(3,"没有用","智少");
    heroList.change(newHero);
    System.out.println("修改后的列表信息");
    heroList.list();
    HeroNode deleteHero = new HeroNode(3,"没有用","智少");
    heroList.delete(deleteHero);
    System.out.println("删除后的列表信息");
    heroList.list();

}
 

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

    //新增节点
    public void add(HeroNode heroNode){
        //因为头节点不能动，需要一个变量temp辅助遍历
        HeroNode temp = head;
        boolean flag = false;
        //开始遍历，找到链表中需要插入的位置
        while(true){
            if(temp.next == null){
                break;
            }
            else if (temp.next.number > heroNode.number) {
                break;
            }
            else if(temp.next.number == heroNode.number){
                flag = true;//该编号已存在
                break;
            }
            temp = temp.next;
        }
        if(flag){
            //说明
            System.out.printf("编号%d已存在，无法添加",heroNode.number);
        }
        else{
            //当跳出循环时，新节点的next 指向 temp 的下一个节点
            //temp的next 指向新节点
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }

    //修改信息
    public void change(HeroNode newHeroNode){
        HeroNode temp = head.next;
        boolean flag = false;
        while(true){
            if(temp == null){
                break;
            }
            if(temp.number == newHeroNode.number){
                System.out.println("找到了需要修改的英雄");
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (!flag) {
            System.out.printf("你输入的编号%d有误，列表中未找到\n",newHeroNode.number);
        }

    }

    //删除节点
    public void delete(HeroNode target){
        HeroNode temp = head;
        boolean flag = false;
        while(true){
            if(temp.next == null){
                System.out.println("链表为空！");
                break;
            }
            if(temp.next.number == target.number){
                System.out.println("找到了需要删除的节点");
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.next = temp.next.next;
        }
        else{
            System.out.println("没有找到你想删除的节点！");
        }
    }
    //遍历链表
    public void list(){
        //判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空！");
            return;
        }

        HeroNode temp = head.next;
        while (true) {
            
            System.out.println(temp);
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }
    }
}


//定义  HeroNode , 每个HeroNode 对象就是链表上的一个节点
static class HeroNode{
    public int number;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一节点

    //构造器
    public HeroNode(int num,String name,String nickname){
        this.number = num;
        this.name = name;
        this.nickname = nickname;
    }

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

应用实例5 获取指定节点

查找单链表中倒数第K个节点

  1. 先获取链表的总长度 length
  2. 然后从头开始遍历链表 length - K 个节点,即可得到倒数第 K 个节点.
  3. 若找到节点,则返回该节点, 否则返回 null
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
//按照英雄编号顺序创建单列表
//修改指定编号英雄信息
//删除指定节点
public class SingleLinkedListDemo4 {

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 heroList = new SingleLinkedList();
    heroList.add(hero1);
    heroList.add(hero3);
    heroList.add(hero2);
    heroList.add(hero4);
 
    //显示链表
    heroList.list();
    HeroNode newHero = new HeroNode(3,"没有用","智少");
    heroList.change(newHero);
    System.out.println("队列长度为："+heroList.length(heroList.getHead()));
    System.out.println("修改后的列表信息");
    heroList.list();
    HeroNode deleteHero = new HeroNode(3,"没有用","智少");
    heroList.delete(deleteHero);
    System.out.println("删除后的列表信息");
    heroList.list();
    System.out.println("队列长度为："+heroList.length(heroList.getHead()));

    //返回倒数第一的节点信息
    HeroNode res = heroList.findLastNode(1);
    System.out.println(res);
}
 

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

    //因为头节点使用了private封装，所以创建一个函数来返回头节点。（受控访问）
    public HeroNode getHead(){
        return head;
    }

    //新增节点
    public void add(HeroNode heroNode){
        //因为头节点不能动，需要一个变量temp辅助遍历
        HeroNode temp = head;
        boolean flag = false;
        //开始遍历，找到链表中需要插入的位置
        while(true){
            if(temp.next == null){
                break;
            }
            else if (temp.next.number > heroNode.number) {
                break;
            }
            else if(temp.next.number == heroNode.number){
                flag = true;//该编号已存在
                break;
            }
            temp = temp.next;
        }
        if(flag){
            //说明
            System.out.printf("编号%d已存在，无法添加",heroNode.number);
        }
        else{
            //当跳出循环时，新节点的next 指向 temp 的下一个节点
            //temp的next 指向新节点
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }

    //修改信息
    public void change(HeroNode newHeroNode){
        HeroNode temp = head.next;
        boolean flag = false;
        while(true){
            if(temp == null){
                break;
            }
            if(temp.number == newHeroNode.number){
                System.out.println("找到了需要修改的英雄");
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (!flag) {
            System.out.printf("你输入的编号%d有误，列表中未找到\n",newHeroNode.number);
        }

    }

    //删除节点
    public void delete(HeroNode target){
        HeroNode temp = head;
        boolean flag = false;
        while(true){
            if(temp.next == null){
                System.out.println("链表为空！");
                break;
            }
            if(temp.next.number == target.number){
                System.out.println("找到了需要删除的节点");
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.next = temp.next.next;
        }
        else{
            System.out.println("没有找到你想删除的节点！");
        }
    }
    
    //返回链表的长度(不计算头节点的长度)
    public int length(HeroNode head){
        if(head.next == null){
            return 0;
        }
        int length = 0 ;
        HeroNode temp = head.next;
        while(temp != null){
            length++;
            temp = temp.next;
        }
        return length;
    }
    
    //获取倒数第K个节点
    public HeroNode findLastNode(int K){
        if(head.next == null){
            System.out.println("链表为空!");
            return null;
        }
        HeroNode temp = head.next;
        int length = length(head);  //获取链表长度
        //排除极端情况
        if(K>length || K<=0){
            System.out.println("K值不合法");
            return null;
        }
        for(int i=0; i < length - K;i++){
            temp = temp.next;
        } 
        return temp;
 
    }

    //遍历链表
    public void list(){
        //判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空！");
            return;
        }

        HeroNode temp = head.next;
        while (true) {
            
            System.out.println(temp);
            if(temp.next == null){
                break;
            }
            temp = temp.next;
        }
    }
}


//定义  HeroNode , 每个HeroNode 对象就是链表上的一个节点
static class HeroNode{
    public int number;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一节点

    //构造器
    public HeroNode(int num,String name,String nickname){
        this.number = num;
        this.name = name;
        this.nickname = nickname;
    }

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

应用实例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
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
public class ReverseList {
    //反转链表
    public static void main(String[] args){
        StudentList myStudentList = new StudentList();
        StudentNode student1 =new StudentNode(1,"张三",14);
        StudentNode student2 =new StudentNode(2,"李四",18);
        StudentNode student3 =new StudentNode(3,"王二",11);
        StudentNode student4 =new StudentNode(4,"麻子",19);

        myStudentList.add(student1);
        myStudentList.add(student3);
        myStudentList.add(student4);
        myStudentList.add(student2);
        System.out.println("初始列表");
        myStudentList.showList();
        System.out.println("反转列表");
        myStudentList.reverseList(myStudentList.getHead());
        myStudentList.showList();



    }

    //定义链表
    static class StudentList{
        //先初始化一个头节点，头节点是不动的，固定的，不存放具体的数据
        private StudentNode head = new StudentNode(0, "null", 0);
        //返回头节点
        public StudentNode getHead(){
            return head;
        }

        //新增节点,按学号从小到大的顺序添加节点
        public void add(StudentNode stu){
            StudentNode temp = head;
            boolean flag = false;
            while(true){
                if(temp.next == null){
                    flag =true;
                    break;
                }
                if(temp.next.number > stu.number){
                    flag = true;
                    break;
                }
                if(temp.next.number == stu.number){
                    break;
                }
                temp = temp.next;
            }

            if(flag){
                stu.next = temp.next;
                temp.next = stu;
            }
            else{
                System.out.println("学号存在相同的，无法添加");
            }

        }


        //反转链表
        public  void reverseList(StudentNode head){
            //如果当前列表为空或者只有一个节点，则无法反转，结束程序。
            if(head.next == null || head.next.next == null){
                return;
            }
            //创建反转链表
            StudentNode rehead = new StudentNode(0,"",0);
            StudentNode current  =  head.next; //当前遍历的节点
            StudentNode nextNode = null;    //保存当前遍历节点的下一个节点
            
            while(true){
                if(current == null){
                    break;
                }
                nextNode = current.next; //1、保存当前遍历节点的下一个节点,防止链表断裂
                current.next = rehead.next; //2、当前节点指向反转列表的第一个有效节点
                rehead.next = current; //3、反转链表头指向当前节点，完成插入
                current = nextNode; //4、移动到原列表的下一个节点
                
            }

            head.next = rehead.next; //将原列表的头节点指向反转后的链表
        }


        //遍历链表
        public void showList(){
            StudentNode temp = head;
            while(true){
                if(temp.next == null){
                    break;
                }
                
                temp = temp.next;
                System.out.println(temp.toString());
            }
        }
    }

    //创建节点
    static class StudentNode{
        private int    number;
        private String name;
        private int    age;

        public StudentNode next; //指向下一节点

        public StudentNode(int number,String name,int age){
            this.age = age;
            this.name = name;
            this.number = number;
        }   

        @Override
        public String toString() {
            return "Student[姓名:" +  name + ", 学号: " + number +", 年龄:" + age +" 岁]";
        }

    }
}

应用实例7 逆序打印

注：需要掌握栈的知识点。

从尾到头打印单链表

应用实例8 合并链表

合并两个有序单链表，合并之后的链表依然有序。

双向链表


双向链表示意图

从示意图可以看出来，双向链表对比单链表只是每个节点都多了一个pre功能，next是指向下一节点，那么以此类推pre就是指向上一节点。

基本操作

分析双向链表的遍历、添加、修改、删除节点的代码实现

  • 遍历

​ 与单链表没啥区别。只不过既可以从前往后遍历也可以从后往前遍历。

  • 添加

​ 若添加的节点是加到链表的尾部，

  1. 先找到链表的最后一个节点

  2. temp.next = newNode;
newNode.pre = temp;

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

       

    - 修改

    ​	与单链表没啥区别。

    - 删除

    1. 因为是双向链表，因此可以直接删除 temp 节点

    2. 找到需要删除的节点 temp

    3. ```java
       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
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
public class DoubleLinkedListDemo {
    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 heroList = new DoubleLinkedList();
        heroList.add(hero1);
        heroList.add(hero2);
        heroList.add(hero3);
        heroList.add(hero4);
        heroList.showList();
        heroList.change(1);
        heroList.showList();
        heroList.delete(4);
        heroList.showList();
    }
    //创建链表管理方法
    public static class DoubleLinkedList{
        private HeroNode head = new HeroNode(0, null);
        //返回头节点
        public HeroNode getHead(){
            return head;
        }
        //遍历节点
        public void showList(){
            HeroNode temp = head;

            while (temp.next != null) {
                temp = temp.next;
                System.out.println(temp.toString());
            }
        }
        //添加节点
        public void add(HeroNode newNode){
            HeroNode temp = head;
            //到达链表尾部
            while(temp.next != null){
                temp = temp.next;
            }

            //将新节点和原链表的最后一个节点建立联系
            temp.next = newNode;
            newNode.pre = temp ;
        }
        //修改节点
        public void change(int a){
            HeroNode temp = head;
            boolean flag = false;
            while (true) {
                
                if(temp.number == a){
                    System.out.println("找到了需要修改的节点");
                    flag = true; 
                    break;
                }
                if(temp.next == null){
                    break;
                }
                temp = temp.next;
            }

            if(flag == true){
                System.out.println("修改之前节点信息为："+temp.toString());
                temp.name = "牛逼" ;
                System.out.println("修改节点信息成功");
                System.out.println("修改后节点信息为："+temp.toString());
            }
            else{
                System.out.println("没找到你想修改的节点");
            }
        }
    
        //删除节点
        public void delete(int a){
            HeroNode temp = head;
            if(a<0){
                System.out.println("请输入正确的节点编号");
            }
            boolean flag = false;
            while (true) {
                if(temp.number == a){
                    flag = true;
                    break;
                }
                if(temp.next == null){
                    System.out.println("你想删除的节点不存在");
                    break;
                }
                temp = temp.next;
            }
            if (flag) {
                temp.pre.next = temp.next;
                if(temp.next != null)//要考虑删除的节点是不是最后一个节点
                {
                    temp.next.pre = temp.pre;
                }
                System.out.println("删除节点成功！");
            }
        }
    }
    //创建节点构造器
    public static class HeroNode{
        private String name;
        private int    number;
        public HeroNode next;
        public HeroNode pre;

        
        //创建构造器
        public HeroNode(int number,String name){
            this.name = name;
            this.number = number;
            
        }

        @Override
        public String toString() {
            return "HeroNode["+number+", name: "+ name  + "]";
        }
    }
}

环形链表

约瑟夫问题 Josepfu

设编号为1、2，… n 的 n 个人围坐在一圈，若约定从编号为 k 的那个人开始从1开始报数，数到 m 的那个人出列，然后从刚刚出列的那个人的下一位继续从1开始报数，数到 m 的那个人又出列，以此类推，直到所有人出列，由此产生一个出队编号的序列。


约瑟夫问题示意图

例如上图有5位小朋友，假设从1号小朋友开始数2个数，来开始游戏。

第一次出列的是2号小朋友，此时继续从3号小朋友开始数2个数；

第二次出列的是4号小朋友，此时继续从5号小朋友开始数2个数；

第三次出列的是1号小朋友，此时继续从3号小朋友开始数2个数；

第四次出列的是5号小朋友，此时只剩下3号一位小朋友了；

第5次出列的是3号小朋友。

代码分析


约瑟夫问题的代码思路1

约瑟夫问题的代码思路2

代码实现

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
//约瑟夫问题
//设编号为1、2，... n 的 n 个人围坐在一圈
//若约定从编号为 k 的那个人开始从1开始报数，数到 m 的那个人出列
//然后从刚刚出列的那个人的下一位继续从1开始报数，数到 m 的那个人又出列
//以此类推，直到所有人出列，由此产生一个出队编号的序列
public class Josepfu {
    public static void main(String[] args){
        CircleSingleLinkedList BoyList = new CircleSingleLinkedList();
        BoyList.addBoy(25);
        BoyList.showList();
        BoyList.start(25, 1, 2);
    }
}
//创建环形单向链表
class CircleSingleLinkedList{
    //创建一个 first 节点
    private Boy first = null;
    //添加小孩,构成环形链表
    public void addBoy(int nums){
        //nums的数据校验
        if(nums < 1){
            System.out.println("nums 的值不正确");
        }
        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 ; //让辅助变量指向first
            }
            curBoy.setNext(boy);
            curBoy = boy;
            curBoy.setNext(first);
        }
    }
    //遍历环形链表
    public void showList(){
        Boy temp = first;
        while (true) {
            System.out.println(temp.toString());
            if(temp.getNext() == first){
                break;
            }
            temp = temp.getNext();
        }
    }
    /**
     * 
     * @param nums 参加游戏的小朋友总数
     * @param k    从第几个小朋友开始数
     * @param n   数几下
     */
    public void start(int nums,int k,int n){
        Boy temp = first;
        //让temp指向最后一个节点
        while (true) {
            if(temp.getNext() == first){
                break;
            }
            temp = temp.getNext();
        }
        //正式开始游戏前，先first 和 temp 移动 K-1 次 
        //表示从第 K 个小朋友开始游戏
        for(int i=0; i<k-1;i++){
            first = first.getNext();
            temp = temp.getNext();
        }
        //开始游戏时，让first和temp同时移动 n-1 下，然后出圈
        while (true) {
            if(temp == first){ //说明此时圈中只有一个节点
                break;
            }
            for(int j=0;j<n-1;j++){
                first = first.getNext();
                temp = temp.getNext();
            }
            //此时first所指的节点，就是要出圈的小朋友节点
            System.out.printf("小孩【 %d 】出圈 \n",first.getNo());
            first = first.getNext();
            temp.setNext(first)  ;
        }
        System.out.println("最后出圈的小孩【" + first + "】"  );
    }
}

//创建 Boy 节点
class Boy{
    private int no;
    private Boy next;
    public Boy(int no){
        this.no = no;
    }
    public int getNo(){
        return no;
    }
    public Boy getNext() {
        return next;
    }
    public void setNext(Boy next) {
        this.next = next;
    }
    @Override
    public String toString() {
        return "Boy[" + this.getNo() +"]";
    }
}

总结对比：数组和链表

特性 数组栈 链表栈
栈满判断 必须（固定容量） 不需要（动态扩容）
栈空判断 必须 必须
内存分配 连续内存，提前分配 分散内存，按需分配
空间效率 可能浪费（固定长度） 更高效（用多少占多少）

总结

  1. 链表栈不需要设置栈满判断，因为链表节点是动态创建的，没有固定容量限制，只要系统内存充足就可以一直入栈。
  2. 数组栈必须设置栈满判断，因为数组长度固定，元素数量达到数组长度后无法继续入栈。
  3. 无论哪种栈，栈空判断都是必须的（出栈 / 遍历前判断），避免空指针异常，提升程序健壮性。

对对对