每一秒钟的时间都值得铭记

0%

数据结构之什么是数组？

发表于 分类于
本文字数： 6.4k 阅读时长 ≈ 6 分钟

什么是数组？

数组对应的英文是array，是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。数组是最为简单、最为常用的数据结构。

  • 数组的每一个元素都有自己的下标，该下标从0开始，一直到数组长度-1结束。
  • 数组在内容中是顺序存储，在内存中的表现形式为一整块完整的内存空间。
  • 数组的特点，有限个数，相同类型，有序。

数组的基本操作

数组的基本操作，无非就是增、删、改、查四种情况。

查——读取元素

对于数组来说，读取元素是最为简单的操作。由于数组在内存中顺序存储，所以只需要给出一个数组下标，就可以读取到对应的数组元素。

这种通过数组下标读取元素的方式叫做随机读取

1
2
3
int[] arr = new int[]{1, 5, 4, 6, 1, 3, 5, 3};
// 输出下标为2的数组元素，即数组的第三个元素，4
System.out.println(arr[2]);

改——更新元素

把数组的某一个元素替换为一个新值，也是非常简单的事情，直接利用数组的下标，就可以把新值赋给该元素。

1
2
3
4
5
6
7
int[] arr = new int[]{1, 5, 4, 6, 1, 3, 5, 3};
// 输出赋值前，下标为4的数组元素，值为：1
System.out.println(arr[4]);
// 赋值，改变数组元素的值
arr[4] = 10;
// 输出赋值后，下标为4的数组元素，值为：10
System.out.println(arr[4]);

增——插入元素

数组的插入元素操作是一个比较复杂的操作，因为涉及数组元素个数的变动，所以在介绍插入元素操作之前，需要先介绍一下数组的长度和数组的实际元素个数。

数组的长度：即数组初始化时开辟的内存空间大小。

1
2
// 开辟了一个数组长度为5的数组内存空间
int[] arr = new int[5];

数组的实际元素个数：即数组中存在的元素个数。

1
2
3
4
5
6
7
8
// 开辟了一个数组长度为5的数组内存空间
int[] arr = new int[5];
arr[0] = 2;
arr[1] = 8;
for (int i : arr) {
    // 输出：2 8 0 0 0，数组的实际元素个数为2
    System.out.print(i + "\t");
}

上述的数组中，实际的元素个数只有两个，即下标为0、1的两个元素，其他元素之所以输出为0，是因为在Java中，int类型的初始化值为0，所以输出的数组为2 8 0 0 0，如果使用Integer类型的数组，则可以通过null值进行更直观的判断。

1
2
3
4
5
6
7
8
// 开辟了一个数组长度为5，类型为Integer的数组内存空间
Integer[] array = new Integer[5];
array[0] = 2;
array[1] = 8;
for (Integer integer : array) {
    // 输出：2	8	null	null	null，数组的实际元素个数为2
    System.out.print(integer + "\t");
}

正是因为存在数组的长度和实际元素个数不同的情况，所以在一般情况下，我们会使用一个变量来记录数组的实际元素个数。

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
public class Array {
    /**
     * 数组
     */
    private int[] array;
    /**
     * 数组的最大元素个数，即为数组的长度
     */
    private int maxSize;
    /**
     * 数组的实际元素个数
     */
    private int size;

    /**
     * 构造函数
     *
     * @param capacity 初始化数组的容量大小，即maxSize大小
     */
    public Array(int capacity) {
        // 初始化数组长度
        this.maxSize = capacity;
        // 初始化数组，开辟数组空间
        this.array = new int[maxSize];
        // 初始化数组实际元素个数，为0
        this.size = 0;
    }

    /**
     * 获取数组的实际元素个数
     *
     * @return 数组的实际元素个数
     */
    public int size() {
        return this.size;
    }

    /**
     * 获取数组的长度
     *
     * @return 数组的长度
     */
    public int length() {
        return this.maxSize;
    }

}

我们只需要通过创建Array类的对象的方式，即可完成一个数组的初始化。

1
2
3
4
5
Array array = new Array(5);
// 数组的实际元素个数为：0
System.out.println(array.size());
// 数组长度为：5
System.out.println(array.length());

这个时候，数组的插入插入操作即可以开始了。

数组的插入操作也分为三种，分别为：

  • 尾部插入
  • 中间插入，头部插入本质上也属于中间插入的一种
  • 超范围插入

尾部插入最为简单，只需要将元素放置在数组尾部的空闲元素的位置上即可。

中间插入较为复杂，因为在数组中间位置插入元素，需要先将插入位置及插入位置后面的元素向后移动，空出一个数组下标给插入的元素。

超范围插入最为复杂，因为超范围插入涉及到了数组的扩容。

数组扩容

为什么需要数组扩容？

我们不断往一个数组中插入元素，最终数组实际元素个数等于，甚至大于数组长度，这个时候数组已经无法容纳更多的元素了，所以我们需要通过扩容在扩大数组的容量。

怎么扩容？

数组的长度在初始化的时候就已经固定了，这也是数组有限个数的特点，如果如果想要对数组进行扩容，就需要创建一个容量比原数组更大的新数组，并将原数组的元素复制到新数组中，实现原数组的替换操作。

所以数组的插入操作的具体代码为：

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
/**
 * 直接在数组尾部插入元素
 *
 * @param element 需要插入的元素
 */
public void add(int element) {
    add(this.size, element);
}

/**
 * 在数组指定位置插入元素
 *
 * @param index   数组指定的下标位置
 * @param element 需要插入的元素
 */
public void add(int index, int element) {
    // 这样操作的目的是为了保证数组的元素全部都可以从0开始，并且中间不会出现空闲元素
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("插入元素的位置超出数组的实际元素范围");
    }
    // 如果当前数组实际元素个数大于等于数组长度，进行扩容操作
    if (size >= maxSize) {
        resize();
    }
    // 从下标index开始将元素向后移动一位
    for (int i = size; i > index; i--) {
        this.array[i] = this.array[i - 1];
    }
    // 在index位置插入需要插入的元素
    this.array[index] = element;
    // 数组实际元素个数+1
    size++;
}

/**
 * 扩容操作，每次扩容，新数组的长度为原数组的2倍
 */
private void resize() {
    // 新数组的长度为原数组的2倍
    this.maxSize = this.maxSize * 2;
    // 初始化新数组
    int[] newArray = new int[maxSize];
    // 将原数组的元素复制到新数组中
    System.arraycopy(this.array, 0, newArray, 0, this.size);
    // 使用新数组替换原数组
    this.array = newArray;
}

删——删除元素

数组的删除操作比起插入元素来，比较简单一些，因为不涉及数组扩容的问题，我们只需要将数组被删除位置后面的元素向前移动即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 删除数组元素
 *
 * @param index 需要删除的数组元素下标位置
 * @return 删除的元素
 */
public int delete(int index) {
    // 判断需要删除的数组下标是否在数组实际元素范围之内
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("删除元素的位置超出数组的实际元素范围");
    }
    int deleteElement = this.array[index];
    for (int i = index; i < size - 1; i++) {
        this.array[index] = this.array[index + 1];
    }
    size--;
    return deleteElement;
}

数组操作的时间复杂度

数组操作 时间复杂度
读取元素 O(1)
更新元素 O(1)
插入元素 O(n)
删除元素 O(n)

数组的优势和劣势

优势：数组拥有非常高效的随机访问能力，只需要通过下标，就可以用常量时间找到对应的元素。

劣势：数组在插入和删除的时候，需要移动大量元素，导致效率低下。

总结：数组适用于读操作多，写操作少的场景。

数组的完整代码（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
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
public class Array {
    /**
     * 数组
     */
    private int[] array;
    /**
     * 数组的最大元素个数，即为数组的长度
     */
    private int maxSize;
    /**
     * 数组的实际元素个数
     */
    private int size;

    /**
     * 构造函数
     *
     * @param capacity 初始化数组的容量大小，即maxSize大小
     */
    public Array(int capacity) {
        // 初始化数组长度
        this.maxSize = capacity;
        // 初始化数组，开辟数组空间
        this.array = new int[maxSize];
        // 初始化数组实际元素个数，为0
        this.size = 0;
    }

    /**
     * 获取数组的实际元素个数
     *
     * @return 数组的实际元素个数
     */
    public int size() {
        return this.size;
    }

    /**
     * 获取数组的长度
     *
     * @return 数组的长度
     */
    public int length() {
        return this.maxSize;
    }

    /**
     * 获取下标对应的元素
     *
     * @param index 数组下标
     * @return 下标对应的元素
     */
    public int get(int index) {
        // 判断需要删除的数组下标是否在数组实际元素范围之内
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("删除元素的位置超出数组的实际元素范围");
        }
        return this.array[index];
    }

    /**
     * 更新下标对应的元素
     *
     * @param index   数组下标
     * @param element 需要更新的元素
     */
    public void update(int index, int element) {
        // 判断需要删除的数组下标是否在数组实际元素范围之内
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("删除元素的位置超出数组的实际元素范围");
        }
        this.array[index] = element;
    }

    /**
     * 直接在数组尾部插入元素
     *
     * @param element 需要插入的元素
     */
    public void add(int element) {
        add(this.size, element);
    }

    /**
     * 在数组指定位置插入元素
     *
     * @param index   数组指定的下标位置
     * @param element 需要插入的元素
     */
    public void add(int index, int element) {
        // 这样操作的目的是为了保证数组的元素全部都可以从0开始，并且中间不会出现空闲元素
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("插入元素的位置超出数组的实际元素范围");
        }
        // 如果当前数组实际元素个数大于等于数组长度，进行扩容操作
        if (size >= maxSize) {
            resize();
        }
        // 从下标index开始将元素向后移动一位
        for (int i = size; i > index; i--) {
            this.array[i] = this.array[i - 1];
        }
        // 在index位置插入需要插入的元素
        this.array[index] = element;
        // 数组实际元素个数+1
        size++;
    }

    /**
     * 扩容操作，每次扩容，新数组的长度为原数组的2倍
     */
    private void resize() {
        // 新数组的长度为原数组的2倍
        this.maxSize = this.maxSize * 2;
        // 初始化新数组
        int[] newArray = new int[maxSize];
        // 将原数组的元素复制到新数组中
        System.arraycopy(this.array, 0, newArray, 0, this.size);
        // 使用新数组替换原数组
        this.array = newArray;
    }

    /**
     * 删除数组元素
     *
     * @param index 需要删除的数组元素下标位置
     * @return 删除的元素
     */
    public int delete(int index) {
        // 判断需要删除的数组下标是否在数组实际元素范围之内
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("删除元素的位置超出数组的实际元素范围");
        }
        int deleteElement = this.array[index];
        for (int i = index; i < size - 1; i++) {
            this.array[index] = this.array[index + 1];
        }
        size--;
        return deleteElement;
    }
}

最后

本文Github https://github.com/herenpeng/code-learn 已收录，欢迎Star。

坚持原创技术分享，您的支持将鼓励我继续创作！
-------------这是我的底线^_^-------------