菜狗学数据结构——数组和链表

发表于 更新于 分类于 ，

数据结构的存储方式只有两种：数组和链表，这两个是其他数据结构实现的基础。

在编写程序的过程中，我们常常需要「找到」一个位置来存放「中间数据」。此时，我们常常定义变量来存储他们。当创建变量时，计算机会为其创建一个单独的「空间」来存放特定类型的数据。

如下所示，我们创建了一个score变量来存放一位同学的成绩。

1
var score = 80;

计算机会在内存中单独开辟一片空间来存放数据，并且告诉程序相应的内存地址。如图所示，该变量的内存地址是0x00000005。

当我们需要存储多个相同类型的数据时，似乎使用变量就显得不太「靠谱」了

1
2
3
4
5
6
7
8
var score1 = 80;
var score2 = 90;
var score3 = 59;
var score4 = 66;
var score5 = 11;
var score6 = 99;
var score7 = 55;
var score8 = 73;

如果有 200 个学生，难不成定义 200 个变量来存储学生成绩？这时可以使用数组和链表来存储。

数组

使用数组时，计算机会在内存中开辟一整段连续的空间用于存放数据。依然以学生成绩为例。

1
var scores = new int[]{80, 90, 59, 66, 11, 99, 55, 73};

如图所示，计算机为学生成绩分别开辟了 8 份空间用来分别存放 8 位学生的考试成绩。然而这里又出现了一个问题，如果想要添加第 9 位学生成绩时会怎么样？

答案就是，计算机会重新在内存中找一份空间用于存放这 9 位学生成绩。这也是为什么数组一旦创建就不可变。

数组的操作

在数组中，针对一个元素的位置有一个专业术语称为索引（又称下标）。我们通常通过索引（下标）来获取、修改数组元素

数组的索引由 0 开始，最大值为数组元素总数 - 1。

数组元素数据的获取

数组元素数据通过数组名[索引]来获取。如以下代码展示了如何遍历一个数组。

1
2
3
4
var scores = new int[]{80, 90, 59, 66, 11, 99, 55, 73};
for(var i = 0; i < scores.length; i++){
    System.out.println(scores[i]);
}

数组元素数据的修改

数组元素数据可以通过数组名[索引] = 新数据来修改。如以下代码展示了将scores数组中第 4 号元素（11分）修改为81分。

1
2
var scores = new int[]{80, 90, 59, 66, 11, 99, 55, 73};
scores[4] = 81;

数组元素的插入

如果需要在数组之间的某个位置插入一个元素，则需要将其后面的元素整体向后挪一位。当数组空间不足时，你需要重新创建一个空间来存放新的数组。

数组元素的删除

数组中一个元素删除时，通常使得其右边的元素向左挪一位。

链表

与数组不同，链表中的元素可以在任意的内存位置中。

依然以上面的学生成绩为例，其在内存中如图所示。

一个简易链表的实现如下：

链表的操作

在链表中，我们通常将元素称为一个节点(node)，一个节点保存了其上下节点的地址。

通常节点的设计如下：

1
2
3
4
5
6
7
8
9
class Node {
    int score;
    Node prev;
    Node next;

    public Node(int score) {
        this.score = score;
    }
}

链表元素数据的获取

在链表中，一个元素数据需要由上一个元素逐步向下寻找。具体代码实现可以参照下面的get(int index)方法。

链表元素数据的修改

在链表中，想要修改一个元素的数据首先要找到该元素，然后对其进行修改。具体代码实现可以参照下面的update(int index, int newData)方法。

链表元素的插入

在链表中，想要插入一个元素可以将上一个节点的next对象以及下一个节点的prev对象指向新的元素。具体代码实现可以参照下面的insert(int index, int data)方法。

链表元素的删除

在链表中，想要删除一个元素只需要确保没有任何一个元素指向该节点即可。具体代码实现可以参照下面的remove(int index)方法。

简易链表的实现

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
public class MyLinkedList {
    /**
     * 头节点指针
     */
    private Node head;
    /**
     * 尾节点指针
     */
    private Node last;
    /**
     * 链表实际长度
     */
    private int size;

    /**
     * 链表插入元素
     *
     * @param data  插入元素
     * @param index 插入位置
     */
    public void insert(int index, int data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        final var insertedNode = new Node(data);
        insertedNode.prev = last;
        if (size == 0) {
            // 空链表
            head = insertedNode;
            last = insertedNode;
        } else if (index == 0) {
            // 插入头部
            insertedNode.next = head;
            head = insertedNode;
        } else if (size == index) {
            // 插入尾部
            last.next = insertedNode;
            last = insertedNode;
        } else {
            // 插入中间
            final var prevNode = get(index - 1);
            insertedNode.next = prevNode.next;
            prevNode.next = insertedNode;
        }
        size++;
    }

    /**
     * 修改数据元素
     *
     * @param index    修改元素索引
     * @param newData  修改值
     */
    public void update(int index, int newData) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        final var node = get(index);
        node.data = newData;
    }

    /**
     * 链表删除元素
     *
     * @param index 删除位置
     */
    public Node remove(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        Node removedNode = null;
        if (index == 0) {
            // 删除头节点
            removedNode = head;
            head = head.next;
            head.prev = null;
        } else if (index == size - 1) {
            // 删除尾节点
            final var prevNode = get(index - 1);
            removedNode = prevNode.next;
            prevNode.next = null;
            last = prevNode;
        } else {
            // 删除中间节点
            final var prevNode = get(index - 1);
            final var nextNode = prevNode.next.next;
            removedNode = prevNode.next;
            nextNode.prev = prevNode;
            prevNode.next = nextNode;
        }
        size--;
        return removedNode;
    }

    /**
     * 链表查找元素
     *
     * @param index 查找位置
     */
    public Node get(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        var temp = this.head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 输出链表
     */
    public void output() {
        var temp = this.head;
        while (temp != null) {
            System.out.println(temp.data);
            temp = temp.next;
        }
    }

    /**
     * 链表节点
     */
    private static class Node {
        Node prev;
        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) throws Exception {
        final var myLinkedList = new MyLinkedList();
        myLinkedList.insert(0, 3);
        myLinkedList.insert(1, 7);
        myLinkedList.insert(2, 9);
        myLinkedList.insert(3, 5);
        myLinkedList.output();
        System.out.println("--------------");
        myLinkedList.update(3, 8);
        myLinkedList.remove(0);
        myLinkedList.output();
    }
}

数组和链表的优劣

如下是数组和链表操作运行所需的时间：

数组链表
读取O(1)O(n)
插入O(n)O(1)
删除O(n)O(1)

参考资料