线性表

无论是一维数组也好，二维、三维数组也好，本质都是一张表：都是一堆数据元素的排列，只不过二维的每一个元素都是一个一维数组（三维以此类推），那么如何运用好数组呢？也是一门学问——见稀疏数组，就是数组压缩的例子之一。

链表也是线性表，只不过存储方式是链式的，即在计算机中不是连续存储的。

队列和栈，都是操作受限的线性表，可以有顺序存储结构和链式存储结构。队列强调先进先出，只允许队首元素deQueue、队尾元素enQueue（双向除外）；栈强调后进先出，只允许在栈顶push和pop，不允许操作、访问栈底元素（双向除外）。

哈希表融数组+链表 或 未来的 数组+二叉树 于一体，严格意义上应该不能在这个概论里说吧……不过数组+链表的结合还是可以放在这里说，它通过键值对的形式存放和快速查找某元素，主要体现了查询的迅速。

稀疏数组

思路分析:

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

稀疏数组的处理方式是：

记录数组的行数、列数、有多少个不同的值(或称:非零值(仅大部分元素为0的稀疏数组可称))。

把这些不同值的元素的行、列、值三个为一组记录下来。

代码实现

SparseArray

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
package com.yukinoshita.sparseArray;

import java.lang.reflect.Array;

public class SparseArray {
    //创建一个原始的二维数组   11*11
    public static void main(String[] args) {
        System.out.println("原数组：");
        int[][] chessArray = new int[11][11];
        chessArray[1][2] = 1;
        chessArray[2][3] = 2;
        for (int i = 0; i < chessArray.length; i++) {
            for (int j = 0; j < chessArray[i].length; j++) {
                System.out.print(chessArray[i][j] + " ");
            }
            System.out.println();
        }
        int sum = 0;
        for (int i = 0; i < chessArray.length; i++) {
            for (int j = 0; j < chessArray[i].length; j++) {
                if (chessArray[i][j] != 0) sum++;
            }
        }

        System.out.println("稀疏数组：");
        int[][] spareArray = new int[sum + 1][3];
        spareArray[0][0] = 11;
        spareArray[0][1] = 11;
        spareArray[0][2] = sum;

        int k = 0;
        for (int i = 0; i < chessArray.length; i++) {
            for (int j = 0; j < chessArray[i].length; j++) {
                if (chessArray[i][j] != 0) {
                    k++;
                    spareArray[k][0] = i;
                    spareArray[k][1] = j;
                    spareArray[k][2] = chessArray[i][j];
                }
            }
        }

        for (int i = 0; i < spareArray.length; i++) {
            for (int j = 0; j < spareArray[i].length; j++) {
                System.out.print(spareArray[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("还原为二维数组：");
        int[][] array = new int[spareArray[0][0]][spareArray[0][1]];
        for (int i = 1; i <= spareArray[0][2]; i++) {
            array[spareArray[i][0]][spareArray[i][1]] = spareArray[i][2];
        }

        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }
}

链表

单向链表

思路分析

  1. 链表是以节点的形式链式存储
  2. 每个节点包含data域、next域
  3. 链表分带头节点的链表和不带头节点的链表
  4. initList初始化一个空的单链表
  5. insertList插入操作有头插法和尾插法，还可以根据需求在插入时是否按照顺序进行插入
    • 先给新节点连接好他的尾部newNode.setNext(head.getNext())
    • 再把新节点插入head.setNext(newNode)
  6. deleteList删除操作，要注意判断能否删，可选择传入参数，来对删除元素作限制（例如根据index删、根据data域来删）
  7. traveseList遍历操作，while(p!=null)作为条件，p=p->next;作为迭代条件实现遍历操作。
  8. reverseList单链表的反转-面试题，使用p,next,prev三个指针可实现反转操作。关键步骤为：
    • 初始化p=head或者p=head->next(带头节点写法)，总之p为第一个有值的节点；prev=NULL；
    • 循环条件while(p!=NULL)
      • 保存下一个节点位置信息next=p->next
      • 反转当前节点指向p->next=prev
      • 将前一节点更新，为下次反转做准备prev=p。并且更新p=next否则死循环。
    • 退出循环时，将头节点位置更新head=prev或者head->next=prev(带头节点的写法)

代码实现

SingleLinkedList

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
package com.yukinoshita.linkedList;

public class SingleLinkedList {
    Node head = null;//带头节点

    //注意，在使用SingleLinkedList类前，必须执行init操作
    public void initList() {
        head = new Node();
    }

    /**
     * 演示头插法
     * 注意头插法和尾插法的唯一区别是，执行遍历打印操作时，元素顺序会不同
     * 实际开发中，传入参数为Node类型更加合理(因为以后这个Node中的data域可能会存放很多数据！)
     *
     * @param newNode 要往链表中新增的节点
     */
    public void insertList(Node newNode) {
        newNode.setNext(head.getNext());
        head.setNext(newNode);
    }

    public void traverseList() {
        Node p = head.getNext();
        while (p != null) {
            System.out.printf("%d\t", p.getData());
            p = p.getNext();
        }
        System.out.println();
    }

    public void deleteList() {
        //默认删除最后插入的那个元素（作为演示）
        if (head.getNext() != null) {
            head = head.getNext();
        }
    }

    public void reverseList() {
        Node p = head.getNext();
        Node prev = null;
        while (p != null) {
            Node next = p.getNext();
            p.setNext(prev);
            prev = p;
            p = next;
        }
        head.setNext(prev);
    }

    public boolean isEmpty() {
        return head.getNext() == null;
    }
}

class Node {
    private int data;
    private Node next;

    public Node() {
        this.data = 0;
        this.next = null;
    }

    public Node(int data) {
        this.data = data;
        this.next = null;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

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

    /**
     * 提示：以后可以考虑重写toString()方法，以便了解节点内数据。
     *
     * @return 虽然本次演示不涉及到toString方法
     */
    @Override
    public String toString() {
        return "data=" + data;
    }
}

SingleLinkedListDemo

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
package com.yukinoshita.linkedList;

import java.util.Scanner;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList list = new SingleLinkedList();

        int operate = -1;
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("""
                    -------------------------------------
                    0：退出程序
                    1：initList初始化链表操作
                    2：traverseList遍历并打印链表操作
                    3：insertList插入链表新节点
                    4：deleteList删除节点
                    5：reverseList反转链表
                    -------------------------------------
                    """);
            System.out.print("Enter your choice: ");
            operate = scanner.nextInt();
            switch (operate) {
                case 0 -> {
                    System.out.println("程序退出");
                    scanner.close();
                    System.exit(0);
                }
                case 1 -> {
                    System.out.println("链表初始化");
                    list.initList();
                }
                case 2 -> {
                    if (list.isEmpty()) {
                        System.out.println("当前链表为空，请先初始化");
                    } else {
                        System.out.println("链表元素为:");
                        list.traverseList();
                    }
                }
                case 3 -> {
                    if (list.isEmpty()) {
                        System.out.println("当前链表为空，请先初始化");
                    } else {
                        System.out.print("建立节点(先输入data):");
                        Node newNode = new Node(scanner.nextInt());
                        list.insertList(newNode);
                    }
                }
                case 4 -> {
                    if (list.isEmpty()) {
                        System.out.println("当前链表为空，请先初始化");
                    } else {
                        System.out.println("删除节点:");
                        list.deleteList();
                    }
                }
                case 5 -> {
                    if (list.isEmpty()) {
                        System.out.println("当前链表为空，请先初始化");
                    } else {
                        System.out.println("反转链表:");
                        list.reverseList();
                    }
                }
            }
        }
    }
}

双向链表

思路分析

对比单向链表：

  1. 查找更自由，可以从头或尾找起
  2. 删除更自由，可以实现自我删除，而单链表必须是找到待删除节点的前一个节点。
  3. 双向链表的节点中除了data域、next域，还有prev域
  4. traverseList遍历操作与单向链表一致，只是更加自由（可以额外接受参数，实现从前OR后查找）
  5. insertList无非是新增了prev域，但是具体实现还是要仔细！
  6. deleteList无非是新涉及了prev域的操作，并且删除时可以自我删除。

总体来说双向链表的实现很简单，在单向的基础上多考虑一个prev域就行。

代码实现

DoubleLinkedList

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
package com.yukinoshita.doubleLinkedList;


public class DoubleLinkedList {
    Node head = null;//定义为首个节点
    Node tail = null;

    public void initList() {
        head = new Node();
        tail = head;
    }

    /**
     * 添加到最后面（可以进一步修改为添加到第k个位置）
     *
     * @param newNode 新节点
     */
    public void insertList(Node newNode) {
        newNode.setNext(tail.getNext());
        newNode.setPrev(tail);
        tail.setNext(newNode);
        tail = newNode;
    }

    public void traverseList() {
        Node p = head.getNext();
        while (p != null) {
            System.out.printf("%d\t", p.getData());
            p = p.getNext();
        }
        System.out.println();
    }

    //从头开始删除元素（此处可以进一步改为删除第k个元素）
    public void deleteList() {
        if (head.getNext() != null) {
            head.getNext().setPrev(null);
            head = head.getNext();
        }
    }

    public boolean isEmpty() {
        return head == null;//因为此时规定head是首个节点
    }
}

class Node {
    private int data;
    private Node next;
    private Node prev;

    public Node() {
        this.data = 0;
        this.next = null;
        this.prev = null;
    }

    public Node(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getPrev() {
        return prev;
    }

    public void setPrev(Node prev) {
        this.prev = prev;
    }

    public Node getNext() {
        return next;
    }

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

}

DoubleLinkedListDemo

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
package com.yukinoshita.doubleLinkedList;



import java.util.Scanner;

public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        DoubleLinkedList list = new DoubleLinkedList();

        int operate = -1;
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("""
                    -------------------------------------
                    0：退出程序
                    1：initList初始化链表操作
                    2：traverseList遍历并打印链表操作
                    3：insertList插入链表新节点
                    4：deleteList删除节点
                    -------------------------------------
                    """);
            System.out.print("Enter your choice: ");
            operate = scanner.nextInt();
            switch (operate) {
                case 0 -> {
                    System.out.println("程序退出");
                    scanner.close();
                    System.exit(0);
                }
                case 1 -> {
                    System.out.println("链表初始化");
                    list.initList();
                }
                case 2 -> {
                    if (list.isEmpty()) {
                        System.out.println("当前链表为空，请先初始化");
                    } else {
                        System.out.println("链表元素为:");
                        list.traverseList();
                    }
                }
                case 3 -> {
                    if (list.isEmpty()) {
                        System.out.println("当前链表为空，请先初始化");
                    } else {
                        System.out.print("建立节点(先输入data):");
                        Node newNode = new Node(scanner.nextInt());
                        list.insertList(newNode);
                    }
                }
                case 4 -> {
                    if (list.isEmpty()) {
                        System.out.println("当前链表为空，请先初始化");
                    } else {
                        System.out.println("删除节点:");
                        list.deleteList();
                    }
                }
            }
        }
    }
}

单向环形/循环链表

思路分析

有助于解决约瑟夫问题

构建一个单向环形链表的思路：

  1. 先创建第一个节点，让first指向该节点，并形成环形。
  2. 后面每创建一个新的节点，就加入到已有的环形链表（画图理解）
  3. traverseList当p.getNext() == first说明已完成遍历

代码实现

这里的单向环形链表的部分方法(deleteList操作)是针对于约瑟夫问题特化的

JosephuSolved

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 com.yukinoshita.dataStructure.singleCircleLinkedList;

public class JosephuSolved {
    //Josephu:有5个人，编号从1-5，从第一个人开始报数，每次报到3的人出圈，直到所有人出圈
    //按照出圈顺序打印
    public static void main(String[] args) {
        SingleCircleLinkedList list = new SingleCircleLinkedList();
        list.initList();

        for(int i=0;i<5;i++){
            list.insertList(i+1);
        }

        list.traverseList();

        //在约瑟夫问题中，出去一个后，从下一个接着开始报数
        //也就意味着要修改数据结构中的first、last以适应该问题
        while(!list.isEmpty()){
            System.out.printf("%d\t",list.deleteList(3));
        }
    }

}

SingleCircleLinkedList

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
package com.yukinoshita.dataStructure.singleCircleLinkedList;

public class SingleCircleLinkedList {
    private Node first;
    private Node last;
    public void initList(){
        first = null;
        last = null;
    }

    public boolean isEmpty(){
        return first == null;
    }

    public void insertList(int data){
        if(isEmpty()){
            first = new Node(data,first);//自己与自己构成环形
            last = first;
            return;
        }
        Node newNode = new Node(data,first);
        last.setNext(newNode);
        last = newNode;
    }

    /**
     * 从p节点开始，删除第index个节点，但是针对JosePose问题做了特化
     * @param index 索引(大于等于1！)
     * @return 返回被删除节点的编号
     */
    public int deleteList(int index){
        Node prev = last;
        Node p = first;
        if(first.getNext() == first){
            first = null;
            last = null;
            return p.getNum();
        }
        for (int i = 0; i < index - 1; i++) {
            prev = p;
            p=p.getNext();
        }

        //执行删除
        prev.setNext(p.getNext());
        last = prev;
        first = p.getNext();

        return p.getNum();
    }

    public void traverseList(){
        if(isEmpty()){
            System.out.println("链表为空");
            return;
        }
        Node p = first;
        do{
            System.out.printf("%d\t",p.getNum());
            p=p.getNext();
        }while(p!=first);
        System.out.println();
    }
}

class Node{
    private int num;//编号
    private Node next;

    public Node(int num,Node next){
        this.num = num;
        this.next = next;
    }

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public Node getNext() {
        return next;
    }

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

链表题目

查找单链表的倒数第k个节点

  1. 编写一个方法，接收head节点，同时接收一个index
  2. index表示倒数第index个节点
  3. 若index<0或者index>length，则查找不到。
  4. 如果在设计单链表时，携带length属性（insert时++、delete时–、有get方法），直接获取总长度，遍历后即可到达第length-index+1个节点，即到时第k个节点。若没有length，则需要先遍历一遍获得单链表总长度。(毕竟是单链表，只能从前往后遍历，所以需要预先知道总长才能查询到倒数第k个)

单链表的反转

见单向链表的思路分析部分reverseList。

从尾到头打印单链表

  1. 方式一：先reverse，再打印，但是破坏了原来的结构（不推荐）
  2. 方式二：把节点压入栈中，利用栈后进先出的的特点，实现逆序打印

合并两个有序的单链表，合并后仍保持有序

  1. 两个单链表都还没遍历完，就比大小后再插入
  2. 有一个为空了，剩下的那个直接接入到最后即可