数据结构-基于ArrayList的源码模拟

作者：AllinToyou | 2024-04-27 23:36:11

踩

文章目录

继承关系 :

在这里插入图片描述

1. 构造方法的模拟

源码中我们的ArrayList的构造方法给出了三种实现
分别是不带参数的,带一个参数的,还有一个参数是类的
模拟实现如下

 /**
     * 在我们ArrayList源码里面,提供了三种构造方法(简单模拟一下)
     */
    public MyArrayList() {
        elementData = EMPTY_ELEMENTDATA;
    }

    public MyArrayList(int ininCapacity) {
        if (ininCapacity < 0) {
            throw new RuntimeException("不是哥们,大小不能是负数啊");
        }
        this.elementData = new Object[ininCapacity];
    }

    public MyArrayList(MyArrayList<? extends T> c) {
        Object[] cArr = c.toArray();
        this.elementData = new Object[cArr.length];
        System.arraycopy(cArr, 0, this.elementData, 0, cArr.length);
        this.size = cArr.length;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2. 扩容机制的分析

有些人很好奇,为什么我创建对象的时候没有容量,但却可以添加元素呢,下面就是我们扩容方法模拟,其实源码底层基于的是grow()函数,其实JDK17关于扩容这一块是比较复杂的(底层又去调用了ArraySupport类中的相关方法),如果想了解的话还是自行查看源码吧
代码实现如下

/**
* 扩容机制解析
* 这个方法getNewLength我们解释一下到底是咋回事,我们想要获得一个最适合的扩容机制
* 第一个参数是原有的容量,第二个参数是最小的容量增长量,第三个参数是最合适的增长量(1.5倍率)
* 那就有问题了,为什么不直接用这个最合适的1.5倍率呢?
* 思考,当我的oldCapacity很小的时候,比如1 , 1>>1 == 0
* 那就意味着此时如果直接用1.5倍率增长是无法完成的
*/

public void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newLength = getNewLength(oldCapacity, minCapacity - oldCapacity, oldCapacity >> 1);
        this.elementData = Arrays.copyOf(this.elementData, newLength);
    }

    public void grow() {
        grow(size + 1);
    }

    private int getNewLength(int oldCapacity, int minGrowCapacity, int preferCpacity) {
        int newLength = oldCapacity + Math.max(minGrowCapacity, preferCpacity);
        return newLength;
    }

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

3. 查找方法的模拟

这个就没什么可说的了,注意一点就是引用类型比较的时候是要用我们的equals方法进行比较的,还有就是源码这里实现的时候是通过先进行null的查找
代码实现如下
从前向后查找和从后向前查找

public int indexOf(Object o) {
        return indexOfRange(o, 0, size);
    }

    private int indexOfRange(Object o, int fromIndex, int toIndex) {
        Object[] es = elementData;
        //为什么要把这二者区分开的原因就是,引用数据类型不可以直接相等
        if (es == null) {
            for (int i = fromIndex; i < toIndex; i++) {
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = fromIndex; i < toIndex; i++) {
                if (es[i].equals(o)) {
                    return i;
                }
            }
        }
        return -1;
    }

    public int lastIndexOf(Object o) {
        return lastIndexOfRange(o, size, 0);
    }

    public int lastIndexOfRange(Object o, int fromIndex, int toIndex) {
        Object[] es = elementData;
        if (o == null) {
            for (int i = fromIndex - 1; i >= toIndex; --i) {
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = fromIndex - 1; i >= toIndex; --i) {
                if (es[i].equals(o)) {
                    return i;
                }
            }
        }
        return -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

4. 获取,修改元素的方法模拟

代码实现如下

/**
     * 获取元素,修改元素的方法
     */
    private void checkIndexRange(int index) {
        if (index < 0 || index > size) {
            throw new RuntimeException("下标不合法");
        }
    }

    public T get(int index) {
        checkIndexRange(index);
        return (T) elementData[index];
    }

    public void set(int index, T elem) {
        checkIndexRange(index);
        elementData[index] = elem;
    }

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

5. 添加元素的模拟

这个有一个比较坑的点就是我们在进行Array.copyOf调用的时候,会修改源数组空间的指向,也就是如果在这之前进行过数组指向的约定,要重写修改指向

/**
     * 添加元素的方法
     * 请注意这里有一个小点是比较坑的,就是数组完成扩容之后,原来的数组指向是要进行修改的
     */
    private void add(T elem, Object[] elementData, int sz) {
        if (elementData.length == sz) {
            grow();
        }
        this.elementData[size] = elem;
        size++;
    }

    public boolean add(T elem) {
        add(elem, this.elementData, this.size);
        return true;
    }

    public boolean add(int index, T elem) {
        checkIndexRange(index);
        if (this.elementData.length == this.size) {
            grow();
        }
        //这里我们源代码的移动元素的操作是借助System.arraycopy完成的(final不会修改数组指向)
        final Object[] es = this.elementData;
        System.arraycopy(es, index, es, index + 1, this.size - index);
        es[index] = elem;
        this.size++;
        return true;
    }

    public boolean addAll(MyArrayList<? extends T> c) {
        Object[] arr = c.toArray();
        int numsLength = arr.length;
        if (numsLength == 0) {
            return false;
        }
        Object[] es = this.elementData;
        grow(c.size + this.size);
        //重新改变es的指向
        es = this.elementData;
        System.arraycopy(arr, 0, es, this.size, arr.length);
        this.size = this.size + arr.length;
        return true;
    }
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

6. 删除元素的模拟

源码的这里使用一个fastRemove方法进行操作的,其实也就是System.arraycopy,这个方法底层是cpp/c代码(其实我怀疑是memmove)…
代码实现如下

/**
     * 删除元素的操作(源码里面是借助一个fastRemove的方法完成的,其实也就是arraycopy)
     */
    public T remove(int index) {
        checkIndexRange(index);
        final Object[] es = elementData;
        int newSize = size - 1;
        T oldVal = (T) es[index];
        //这里主要考虑的是尾删除的弊端(尾部删除无法直接进行覆盖)
        if (newSize > index) {
            System.arraycopy(es, index + 1, es, index, newSize - index);
        }
        es[size = newSize] = null;
        return oldVal;
    }

    public boolean remove(Object o) {
        final Object[] es = elementData;
        int index = -1;
        if (o == null) {
            for (int i = 0; i < size; ++i) {
                if (es[i] == null) {
                    index = i;
                    break;
                }
            }
        } else {
            for (int i = 0; i < size; ++i) {
                if (o.equals(es[i])) {
                    index = i;
                    break;
                }
            }
        }
        if (index == -1) {
            return false;
        }
        //到这里说明已经找到了
        int newSize = size - 1;
        if (newSize > index) {
            System.arraycopy(es, index + 1, es, index, newSize - index);
        }
        es[size = newSize] = null;
        return true;
    }

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

7. removeAll与retainAll的模拟

这两个方法比较特殊所以单拎出来

/**
* 源码中关于下面两个方法的解释可以自己去看,机制相对复杂,但是跟我下面模拟的思路是差不多的
* 这个题的最坑的点就是,切记! ! !,不要在一遍删除元素的同时去改变我们的空间大小界限(一般都会出错)
* 这两个方法就是第一个removeAll是清除掉c中含有的元素
* 第二个方法就是保留下来c中的元素,其他都进行删除
*/
代码实现如下

 public void removeAll(MyArrayList<? extends T> c) {
        final Object[] es = this.elementData;
        int sz = this.size;
        for (int i = 0; i < this.size; ++i) {
            while (c.contains(es[i])) {
                System.arraycopy(es, i + 1, es, i, this.size - 1 - i);
                sz--;
                if (sz < 0) {
                    break;
                }
                es[sz] = null;
            }
        }
        this.size = sz;
    }

    public void retainAll(MyArrayList<? extends T> c) {
        Object[] temp = Arrays.copyOf(c.elementData, c.elementData.length);
        final Object[] es = c.elementData;
        int sz = c.size;
        for (int i = 0; i < c.size; ++i) {
            while (c.contains(es[i])) {
                System.arraycopy(c, i + 1, c, i, this.size - 1 - i);
                sz--;
                if (sz < 0) {
                    break;
                }
                c.elementData[sz] = null;
            }
        }
        this.size = sz;
        this.elementData = c.elementData;
        c.elementData = temp;
    }
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

总结: 边缘方法以及总代码

边缘方法都夹在总代码实现里面了,自己查看即可


class MyArrayList<T> {
    private Object[] elementData;
    private int size;
    private static final int DEAFULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 在我们ArrayList源码里面,提供了三种构造方法(简单模拟一下)
     */
    public MyArrayList() {
        elementData = EMPTY_ELEMENTDATA;
    }

    public MyArrayList(int ininCapacity) {
        if (ininCapacity < 0) {
            throw new RuntimeException("不是哥们,大小不能是负数啊");
        }
        this.elementData = new Object[ininCapacity];
    }

    public MyArrayList(MyArrayList<? extends T> c) {
        Object[] cArr = c.toArray();
        this.elementData = new Object[cArr.length];
        System.arraycopy(cArr, 0, this.elementData, 0, cArr.length);
        this.size = cArr.length;
    }

    public void trimToSize() {
        //注意,通过System.arraycopy拷贝是不能直接改变空间大小的
        if (size < elementData.length) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

    /**
     * 扩容机制解析
     * 这个方法getNewLength我们解释一下到底是咋回事,我们想要获得一个最适合的扩容机制
     * 第一个参数是原有的容量,第二个参数是最小的容量增长量,第三个参数是最合适的增长量(1.5倍率)
     * 那就有问题了,为什么不直接用这个最合适的1.5倍率呢?
     * 思考,当我的oldCapacity很小的时候,比如1 , 1>>1 == 0
     * 那就意味着此时如果直接用1.5倍率增长是无法完成的
     */
    public void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newLength = getNewLength(oldCapacity, minCapacity - oldCapacity, oldCapacity >> 1);
        this.elementData = Arrays.copyOf(this.elementData, newLength);
    }

    public void grow() {
        grow(size + 1);
    }

    private int getNewLength(int oldCapacity, int minGrowCapacity, int preferCpacity) {
        int newLength = oldCapacity + Math.max(minGrowCapacity, preferCpacity);
        return newLength;
    }

    public int getSize() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 查找方法的分析
     * 查找方法就是找到从前或者从后开始的第一个满足查找条件的数据类型的下标
     */
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    public int indexOf(Object o) {
        return indexOfRange(o, 0, size);
    }

    private int indexOfRange(Object o, int fromIndex, int toIndex) {
        Object[] es = elementData;
        //为什么要把这二者区分开的原因就是,引用数据类型不可以直接相等
        if (es == null) {
            for (int i = fromIndex; i < toIndex; i++) {
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = fromIndex; i < toIndex; i++) {
                if (es[i].equals(o)) {
                    return i;
                }
            }
        }
        return -1;
    }

    public int lastIndexOf(Object o) {
        return lastIndexOfRange(o, size, 0);
    }

    public int lastIndexOfRange(Object o, int fromIndex, int toIndex) {
        Object[] es = elementData;
        if (o == null) {
            for (int i = fromIndex - 1; i >= toIndex; --i) {
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = fromIndex - 1; i >= toIndex; --i) {
                if (es[i].equals(o)) {
                    return i;
                }
            }
        }
        return -1;
    }

    //toArray方法就是将这个东西转换为数组
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    /**
     * 获取元素,修改元素的方法
     */
    private void checkIndexRange(int index) {
        if (index < 0 || index > size) {
            throw new RuntimeException("下标不合法");
        }
    }

    public T get(int index) {
        checkIndexRange(index);
        return (T) elementData[index];
    }

    public void set(int index, T elem) {
        checkIndexRange(index);
        elementData[index] = elem;
    }

    /**
     * 添加元素的方法
     * 请注意这里有一个小点是比较坑的,就是数组完成扩容之后,原来的数组指向是要进行修改的
     */
    private void add(T elem, Object[] elementData, int sz) {
        if (elementData.length == sz) {
            grow();
        }
        this.elementData[size] = elem;
        size++;
    }

    public boolean add(T elem) {
        add(elem, this.elementData, this.size);
        return true;
    }

    public boolean add(int index, T elem) {
        checkIndexRange(index);
        if (this.elementData.length == this.size) {
            grow();
        }
        //这里我们源代码的移动元素的操作是借助System.arraycopy完成的(final不会修改数组指向)
        final Object[] es = this.elementData;
        System.arraycopy(es, index, es, index + 1, this.size - index);
        es[index] = elem;
        this.size++;
        return true;
    }

    public boolean addAll(MyArrayList<? extends T> c) {
        Object[] arr = c.toArray();
        int numsLength = arr.length;
        if (numsLength == 0) {
            return false;
        }
        Object[] es = this.elementData;
        grow(c.size + this.size);
        //重新改变es的指向
        es = this.elementData;
        System.arraycopy(arr, 0, es, this.size, arr.length);
        this.size = this.size + arr.length;
        return true;
    }

    /**
     * 删除元素的操作(源码里面是借助一个fastRemove的方法完成的,其实也就是arraycopy)
     */
    public T remove(int index) {
        checkIndexRange(index);
        final Object[] es = elementData;
        int newSize = size - 1;
        T oldVal = (T) es[index];
        //这里主要考虑的是尾删除的弊端(尾部删除无法直接进行覆盖)
        if (newSize > index) {
            System.arraycopy(es, index + 1, es, index, newSize - index);
        }
        es[size = newSize] = null;
        return oldVal;
    }

    public boolean remove(Object o) {
        final Object[] es = elementData;
        int index = -1;
        if (o == null) {
            for (int i = 0; i < size; ++i) {
                if (es[i] == null) {
                    index = i;
                    break;
                }
            }
        } else {
            for (int i = 0; i < size; ++i) {
                if (o.equals(es[i])) {
                    index = i;
                    break;
                }
            }
        }
        if (index == -1) {
            return false;
        }
        //到这里说明已经找到了
        int newSize = size - 1;
        if (newSize > index) {
            System.arraycopy(es, index + 1, es, index, newSize - index);
        }
        es[size = newSize] = null;
        return true;
    }

    /**
     * 源码中关于下面两个方法的解释可以自己去看,机制相对复杂,但是跟我下面模拟的思路是差不多的
     * 这个题的最坑的点就是,切记! ! !,不要在一遍删除元素的同时去改变我们的空间大小界限(一般都会出错)
     * 这两个方法就是第一个removeAll是清除掉c中含有的元素
     * 第二个方法就是保留下来c中的元素,其他都进行删除
     */
    public void removeAll(MyArrayList<? extends T> c) {
        final Object[] es = this.elementData;
        int sz = this.size;
        for (int i = 0; i < this.size; ++i) {
            while (c.contains(es[i])) {
                System.arraycopy(es, i + 1, es, i, this.size - 1 - i);
                sz--;
                if (sz < 0) {
                    break;
                }
                es[sz] = null;
            }
        }
        this.size = sz;
    }

    public void retainAll(MyArrayList<? extends T> c) {
        Object[] temp = Arrays.copyOf(c.elementData, c.elementData.length);
        final Object[] es = c.elementData;
        int sz = c.size;
        for (int i = 0; i < c.size; ++i) {
            while (c.contains(es[i])) {
                System.arraycopy(c, i + 1, c, i, this.size - 1 - i);
                sz--;
                if (sz < 0) {
                    break;
                }
                c.elementData[sz] = null;
            }
        }
        this.size = sz;
        this.elementData = c.elementData;
        c.elementData = temp;
    }
}
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
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/499294