动态数组

发表于 | 分类于 ， | | 本文总阅读数 次
| 字数统计: 3.4k | 阅读时长 ≈ 14
动态数组

动态数组

动态数组介绍

  动态数组(Dynamic array):动态数组是一种非常基础的数据结构，指的是大小可以变化的数组。之前在讲语言基础的时候，Python中的list、C++中的vector、以及Java中的ArrayList，都是动态数组，当时只是讲解了动态数组的使用，并没有讲解实现和源码。我们今天从增、删、改、查入手，详细讲解一下动态数组的源码。

构造器

我们直接看源码吧，看一下Java 11中的ArrayList是如何构造的。

ArrayList有三个构造方法，我们看一下最常用的两个。

1

无参构造器

先看下我最喜欢用的无参构造，就一行代码

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

我们可以看出elementData是一个Object[]类型的变量，因此可以才想到，它就是保存元素的数组。让它初始化为一个默认的空数组。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];

这也就表示我们创建的是一个长度为0的Object的数组。

一个int参数的构造器

下面是有一个int参数的构造器

写法也很简单，当参数大于0时，就创建一个参数大小的数组，说明传入的参数表示初始化数组的长度。当参数小于0时，抛出异常，说明不能创建负数容量的数组。当参数等于0时，让数组初始化为一个空数组。

1
2
private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
this.elementData = EMPTY_ELEMENTDATA;

注意了，为什么无参构造器中，数组赋值是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，而传入0构造器中，数组赋值是EMPTY_ELEMENTDATA，而且两个都是长度为0的Object[]类型，有什么区别呢？

难道是开发Java的程序员们写了这么冗余的代码？这里先卖个关子，后面会给小伙伴们解析。

增加元素

我们下面将介绍动态数组最最重要的一个操作，增加元素，只有数组的元素可以增加，才能被称为动态数组。因此如何高效的添加元素，才是动态数组的关键。

一个泛型参数的add方法

1
1
1

我们不关心这个modCount，我们关心如何增加元素和扩容。

在一个参数的add方法中首先调用三个参数的add方法，在三参的add方法中

1
2
3
if (s == elementData.length) {
    elementData = this.grow();
}

s表示当前的元素个数，注意在动态数组中，当前的元素个数是指我们add的元素数量，即可见的元素数量。elementData.length表示数组的容量，容量是大于等于元素数量的。

举个例子，我们初始化长度为10的动态数组，因为new Object[10]，所以数组的容量是10，但是并没有添加元素，说明元素的个数为0。

理解上面的两段话，我们就很容易理解这个代码，当元素的个数等于元素的容量时，此时增加元素会超过数组的索引，因此需要进行扩容。因此会调用grow方法，在grow方法中又会调用一参的grow方法，参数传入元素数量+1，表示最小需要的容量。

在一参的grow方法中，我们会创建一个newCapacity(minCapacity)大小的数组，将原数组中的内容拷贝到新数组中。

因此可以理解为newCapacity(minCapacity)就是扩容后数组的大小，我们用for循环可以实现上面的一段话。

1
2
3
4
5
int k = newCapacity(minCapacity);
Object[] newElementData = new Object[k];
for (int i = 0; i < elementData.length; i++) {
    newElementData[i] = elementData[i];
}

因此对于扩容来说，最重要的方法就是看明白newCapacity是在做什么？

先让oldCapacity表示原数组的容量，让新的容量 = 原容量 x 1.5，并向下取整。oldCapacity >> 1等于oldCapacity x 0.5并向下取整。

当扩容后的容量小于等于原容量时，说明原容量是0或者1。

  • 如果数组等于默认的数组，则扩容到10。
  • 如果最小需要的容量小于0，抛出异常。
  • 否则扩容到最小的容量

当扩容后的容量大于原容量时，此时直接返回扩容后的容量。这里就不讨论hugeCapacity的可能性了，也比较简单。

因此这里就可以解释初始化时的DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA。

注意：
当初始化时使用无参构造器，扩容时会直接扩容到10。再扩容到15、22、33…
当初始化时使用有参构造器，传入的容量是0，扩容时会先扩容到最小容量1，再扩容到最小容量2，然后扩容到3、4、6、9…

一个int参数和一个泛型参数的add方法

1
1

第一个参数表示插入的位置，第二个参数表示插入的元素。因为数据本质上是存放在数组里，因此如果想在某个地方插入元素，那么后面的元素必然需要向后移动。我们先看源码是如何实现的吧。

首先先检查了插入的索引是否满足条件，如果大于元素数量，或者说小于0，都会抛出异常。

然后和一个泛型参数的add方法一样，检查是否需要扩容，扩容的方式也相同。

差异的点在于扩容后，将该索引后面的元素均向后移动一个位置，并且将参数插入到该索引的位置上。

注意：ArrayList一旦扩容后，里面的元素可以删除，数组的长度不会再变小。

追溯到源码后，我们会发现这个数据结构虽然可以动态增删元素，但是效率并不是非常高，因为一旦扩容或者从某个位置插入元素，均需要拷贝大量的元素。

删除元素

一个int参数的remove方法

1
1

一个int参数表示删除该索引对应的元素，首先要坚持索引是否越界。然后取出对应索引的元素，用于返回值。最后要移除元素，并且将数组中的元素向前移动一个位置。

一个泛型参数的remove方法

1

一个泛型参数的remove方法表示从数组中删除某个元素。

实现是遍历这个数组，如果找到则返回true，按照一个int参数的方法将后面的元素均向前移动一个位置，如果没找到则返回false。

注意：

  1. remove数据时，从源码里可以看出，如果发现相等则会break，因此只移除第一个相等的元素，如果有多个值相等的元素，也只会移除一个。
  2. 如果ArrayList保存的是Integer类型的数据，add一个int的数据会进行自动装箱，变成一个Integer，然后add进去。如果remove传入int类型，并不会进行自动装箱，而是会匹配最适合的方法，将传入的值表示为索引，移除该索引对应的元素。如果想移除Integer类型，则需要手动进行装箱。remove(Integer.valueOf(i));

我们可以看出，删除元素时，也会牵扯到大量的元素拷贝，因此效率也不是很高。

修改元素

一个int和一个泛型参数的set方法

1

set方法没啥好说的，不涉及容量的变化，因此不需要扩容和移动。

第一个参数表示索引，第二个参数表示要修改的元素，对数组进行赋值即可。直接看上图源码就可以理解，这里不赘述。

源码中this.elementData(index)，里面的实现就是
return this.elementData[index];
取出索引的值并返回。

查找元素

一个int参数的get方法

1

get方法更简单，也不涉及容量的变化，不需要扩容和移动。

参数表示索引，直接取出数组该索引中的元素。

一个参数的indexOf方法

1

上面是根据索引查找元素，下面介绍一下根据元素查找索引，也非常简单，也就是从开始向后遍历，找到相等时返回，如果遍历结束都没找到则返回-1。

一个参数的lastIndexOf方法

1

顾名思义，这个方法是从后向前查找元素对应的索引，找到相等时返回，如果遍历结束都没找到则返回-1。

代码实现

讲解完毕后，要求不看源码，实现简单的Integer类型的增删改查数据结构，要求扩容机制也要一样。

这一步是非常重要的，如果只是学习并不练习，会很快被遗忘，小伙伴们一定要注意，计算机不是理科而是工科，一定要亲手敲出来，才是真正的学会了。

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
class IntegerArrayList {
    private int[] elementData;

    private int size;

    private boolean isNoneParams;

    public IntegerArrayList() {
        this.elementData = new int[0];
        this.size = 0;
        this.isNoneParams = true;
    }

    public IntegerArrayList(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("Illegal Capacity: " + capacity);
        }
        this.elementData = new int[capacity];
        this.size = 0;
        this.isNoneParams = false;
    }

    public void add(int x) {
        if (elementData.length == size) {
            grow();
        }
        elementData[size++] = x;
    }

    public void add(int index, int x) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + " Out Of Bounds [0, " + size + "]");
        }
        if (elementData.length == size) {
            grow();
        }
        for (int i = size - 1; i >= index; i--) {
            elementData[i + 1] = elementData[i];
        }
        elementData[index] = x;
        size++;
    }

    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + " Out Of Bounds [0, " + (size - 1) + "]");
        }
        int oldValue = elementData[index];
        for (int i = index; i < size - 1; i++) {
            elementData[i] = elementData[i + 1];
        }
        elementData[size--] = 0;
        return oldValue;
    }

    public boolean remove(Integer x) {
        if (x == null) {
            return false;
        }
        int idx = 0;
        while (idx < size) {
            if (elementData[idx] == x) {
                break;
            }
            idx++;
        }
        remove(idx);
        return true;
    }

    public int set(int index, int x) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + " Out Of Bounds [0, " + (size - 1) + "]");
        }
        int oldValue = elementData[index];
        elementData[index] = x;
        return oldValue;
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + " Out Of Bounds [0, " + (size - 1) + "]");
        }
        return elementData[index];
    }

    public int indexOf(int x) {
        for (int i = 0; i < size; i++) {
            if (elementData[i] == x) {
                return i;
            }
        }
        return -1;
    }

    public int lastIndexOf(int x) {
        for (int i = size - 1; i >= 0; i--) {
            if (elementData[i] == x) {
                return i;
            }
        }
        return -1;
    }

    private void grow() {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (isNoneParams) {
            newCapacity = 10;
            isNoneParams = false;
        } else {
            if (newCapacity <= oldCapacity) {
                newCapacity = oldCapacity + 1;
            }
        }
        int[] tmp = new int[newCapacity];
        for (int i = 0; i < size; i++) {
            tmp[i] = elementData[i];
        }
        elementData = tmp;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("array = [");
        for (int i = 0; i < size - 1; i++) {
            builder.append(elementData[i]).append(", ");
        }
        if (size >= 1) {
            builder.append(elementData[size - 1]);
        }
        return builder.append("], capacity = ").append(elementData.length).toString();
    }
}

下面写一下测试代码

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
public class Solution {
    public static void main(String[] args) {
        IntegerArrayList arrayList1 = new IntegerArrayList(0);
        System.out.println(arrayList1);
        arrayList1.add(10);
        System.out.println(arrayList1);
        arrayList1.add(30);
        System.out.println(arrayList1);
        arrayList1.add(40);
        System.out.println(arrayList1);
        arrayList1.add(50);
        System.out.println(arrayList1);
        arrayList1.add(60);
        System.out.println(arrayList1);
        arrayList1.add(70);
        System.out.println(arrayList1);
        arrayList1.add(1, 20);
        System.out.println(arrayList1);
        System.out.println(arrayList1.remove(2));
        System.out.println(arrayList1);
        System.out.println(arrayList1.remove(Integer.valueOf(50)));
        System.out.println(arrayList1);
        System.out.println(arrayList1.get(4));
        System.out.println(arrayList1.set(3, 80));
        System.out.println(arrayList1);
        System.out.println(arrayList1.indexOf(30));
        System.out.println(arrayList1.lastIndexOf(80));

        System.out.println("----------------------------------");

        IntegerArrayList arrayList2 = new IntegerArrayList();
        System.out.println(arrayList2);
        for (int i = 0; i < 23; i++) {
            arrayList2.add(i);
            System.out.println(arrayList2);
        }
    }
}

输出结果为

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
array = [], capacity = 0
array = [10], capacity = 1
array = [10, 30], capacity = 2
array = [10, 30, 40], capacity = 3
array = [10, 30, 40, 50], capacity = 4
array = [10, 30, 40, 50, 60], capacity = 6
array = [10, 30, 40, 50, 60, 70], capacity = 6
array = [10, 20, 30, 40, 50, 60, 70], capacity = 9
30
array = [10, 20, 40, 50, 60, 70], capacity = 9
true
array = [10, 20, 40, 60, 70], capacity = 9
70
60
array = [10, 20, 40, 80, 70], capacity = 9
-1
3
----------------------------------
array = [], capacity = 0
array = [0], capacity = 10
array = [0, 1], capacity = 10
array = [0, 1, 2], capacity = 10
array = [0, 1, 2, 3], capacity = 10
array = [0, 1, 2, 3, 4], capacity = 10
array = [0, 1, 2, 3, 4, 5], capacity = 10
array = [0, 1, 2, 3, 4, 5, 6], capacity = 10
array = [0, 1, 2, 3, 4, 5, 6, 7], capacity = 10
array = [0, 1, 2, 3, 4, 5, 6, 7, 8], capacity = 10
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], capacity = 10
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], capacity = 15
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], capacity = 15
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], capacity = 15
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], capacity = 15
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14], capacity = 15
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], capacity = 22
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16], capacity = 22
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17], capacity = 22
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18], capacity = 22
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19], capacity = 22
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20], capacity = 22
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21], capacity = 22
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22], capacity = 33

小结

  到目前为止，动态数组已经讲解完毕，小伙伴们有没有手写出来动态数组呢？在我的代码中，为了更直观的展示DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA的差异，我直接使用了一个boolean进行区分。Java源码中的ArrayList类还有许多有趣的实现，可以添加一个集合、删除一个集合(求差集)等等，这里不做过多赘述，只讲解最重要的增删改查，感兴趣的小伙伴们可以作为扩展阅读去探寻源码。

-------------本文结束感谢您的阅读-------------
0%