arraylist.md 24.7 KB
Newer Older
沉默王二's avatar
沉默王二 已提交
1
---
沉默王二's avatar
沉默王二 已提交
2
title: Java ArrayList详解(附源码分析)
沉默王二's avatar
沉默王二 已提交
3
shortTitle: ArrayList详解(附源码)
沉默王二's avatar
沉默王二 已提交
4 5 6
category:
  - Java核心
tag:
沉默王二's avatar
沉默王二 已提交
7 8 9 10 11
  - 集合框架(容器)
description: Java程序员进阶之路,小白的零基础Java教程,Java ArrayList详解
head:
  - - meta
    - name: keywords
沉默王二's avatar
沉默王二 已提交
12
      content: Java,Java SE,Java基础,Java教程,Java程序员进阶之路,Java进阶之路,Java入门,教程,ArrayList,ArrayList源码,java arraylist
沉默王二's avatar
沉默王二 已提交
13
---
沉默王二's avatar
沉默王二 已提交
14

沉默王二's avatar
沉默王二 已提交
15
# 6.3 ArrayList详解(附源码)
沉默王二's avatar
沉默王二 已提交
16

沉默王二's avatar
沉默王二 已提交
17 18 19 20 21 22 23 24
“二哥,听说今天我们开讲 ArrayList 了?好期待哦!”三妹明知故问,这个托配合得依然天衣无缝。

“是的呀,三妹。”我肯定地点了点头,继续说道,“ArrayList 可以称得上是集合框架方面最常用的类了,可以和 HashMap 一较高下。”

从名字就可以看得出来,ArrayList 实现了 List 接口,并且是基于数组实现的。

数组的大小是固定的,一旦创建的时候指定了大小,就不能再调整了。也就是说,如果数组满了,就不能再添加任何元素了。ArrayList 在数组的基础上实现了自动扩容,并且提供了比数组更丰富的预定义方法(各种增删改查),非常灵活。

沉默王二's avatar
沉默王二 已提交
25
Java 这门编程语言和别的编程语言,比如说 C语言的不同之处就在这里,如果是 C语言的话,你就必须得动手实现自己的 ArrayList,原生的库函数里面是没有的。
沉默王二's avatar
沉默王二 已提交
26

沉默王二's avatar
沉默王二 已提交
27
### 01、创建 ArrayList
沉默王二's avatar
沉默王二 已提交
28

沉默王二's avatar
沉默王二 已提交
29 30 31 32 33 34 35 36 37 38 39 40 41 42
“二哥,**如何创建一个 ArrayList 啊**?”三妹问。

```java
ArrayList<String> alist = new ArrayList<String>();
```

可以通过上面的语句来创建一个字符串类型的 ArrayList(通过尖括号来限定 ArrayList 中元素的类型,如果尝试添加其他类型的元素,将会产生编译错误),更简化的写法如下:

```java
List<String> alist = new ArrayList<>();
```

由于 ArrayList 实现了 List 接口,所以 alist 变量的类型可以是 List 类型;new 关键字声明后的尖括号中可以不再指定元素的类型,因为编译器可以通过前面尖括号中的类型进行智能推断。

沉默王二's avatar
沉默王二 已提交
43 44 45 46 47 48 49 50
此时会调用无参构造方法(见下面的代码)创建一个空的数组,常量DEFAULTCAPACITY_EMPTY_ELEMENTDATA的值为 `{}`

```java
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
```

沉默王二's avatar
沉默王二 已提交
51 52 53 54 55 56
如果非常确定 ArrayList 中元素的个数,在创建的时候还可以指定初始大小。

```java
List<String> alist = new ArrayList<>(20);
```

沉默王二's avatar
沉默王二 已提交
57
这样做的好处是,可以有效地避免在添加新的元素时进行不必要的扩容。
沉默王二's avatar
沉默王二 已提交
58

沉默王二's avatar
沉默王二 已提交
59
### 02、向 ArrayList 中添加元素
沉默王二's avatar
沉默王二 已提交
60

沉默王二's avatar
沉默王二 已提交
61 62
“二哥,**那怎么向 ArrayList 中添加一个元素呢**?”三妹继续问。

沉默王二's avatar
沉默王二 已提交
63
可以通过 `add()` 方法向 ArrayList 中添加一个元素。
沉默王二's avatar
沉默王二 已提交
64 65 66 67 68

```java
alist.add("沉默王二");
```

沉默王二's avatar
沉默王二 已提交
69 70 71 72 73 74 75 76 77 78 79 80 81 82
我们来跟一下源码,看看 add 方法到底执行了哪些操作。跟的过程中,我们也可以偷师到 Java 源码的作者(大师级程序员)是如何优雅地写代码的。

我先给个结论,全当抛砖引玉。

```
堆栈过程图示:
add(element)
└── if (size == elementData.length) // 判断是否需要扩容
    ├── grow(minCapacity) // 扩容
    │   └── newCapacity = oldCapacity + (oldCapacity >> 1) // 计算新的数组容量
    │   └── Arrays.copyOf(elementData, newCapacity) // 创建新的数组
    ├── elementData[size++] = element; // 添加新元素
    └── return true; // 添加成功
```
沉默王二's avatar
沉默王二 已提交
83

沉默王二's avatar
沉默王二 已提交
84
来具体看一下,先是 `add()` 方法的源码(已添加好详细地注释)
沉默王二's avatar
沉默王二 已提交
85 86

```java
沉默王二's avatar
沉默王二 已提交
87 88 89 90 91
/**
 * 将指定元素添加到 ArrayList 的末尾
 * @param e 要添加的元素
 * @return 添加成功返回 true
 */
沉默王二's avatar
沉默王二 已提交
92
public boolean add(E e) {
沉默王二's avatar
沉默王二 已提交
93 94
    ensureCapacityInternal(size + 1);  // 确保 ArrayList 能够容纳新的元素
    elementData[size++] = e; // 在 ArrayList 的末尾添加指定元素
沉默王二's avatar
沉默王二 已提交
95 96 97 98
    return true;
}
```

沉默王二's avatar
沉默王二 已提交
99 100 101
参数 e 为要添加的元素,此时的值为“沉默王二”,size 为 ArrayList 的长度,此时为 0。

继续跟下去,来看看 `ensureCapacityInternal()`方法:
沉默王二's avatar
沉默王二 已提交
102 103

```java
沉默王二's avatar
沉默王二 已提交
104 105 106 107
/**
 * 确保 ArrayList 能够容纳指定容量的元素
 * @param minCapacity 指定容量的最小值
 */
沉默王二's avatar
沉默王二 已提交
108
private void ensureCapacityInternal(int minCapacity) {
沉默王二's avatar
沉默王二 已提交
109 110
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 如果 elementData 还是默认的空数组
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 使用 DEFAULT_CAPACITY 和指定容量的最小值中的较大值
沉默王二's avatar
沉默王二 已提交
111 112
    }

沉默王二's avatar
沉默王二 已提交
113
    ensureExplicitCapacity(minCapacity); // 确保容量能够容纳指定容量的元素
沉默王二's avatar
沉默王二 已提交
114 115 116
}
```

沉默王二's avatar
沉默王二 已提交
117
此时:
沉默王二's avatar
沉默王二 已提交
118

沉默王二's avatar
沉默王二 已提交
119 120 121 122 123 124 125
- 参数 minCapacity 为 1(size+1 传过来的)
- elementData 为存放 ArrayList 元素的底层数组,前面声明 ArrayList 的时候讲过了,此时为空 `{}`
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA 前面也讲过了,为 `{}`

所以,if 条件此时为 true,if 语句`minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity)`要执行。

DEFAULT_CAPACITY 为 10(见下面的代码),所以执行完这行代码后,minCapacity 为 10,`Math.max()` 方法的作用是取两个当中最大的那个。
沉默王二's avatar
沉默王二 已提交
126 127 128 129 130

```java
private static final int DEFAULT_CAPACITY = 10;
```

沉默王二's avatar
沉默王二 已提交
131
接下来执行 `ensureExplicitCapacity()` 方法,来看一下源码:
沉默王二's avatar
沉默王二 已提交
132 133

```java
沉默王二's avatar
沉默王二 已提交
134 135 136 137 138
/**
 * 检查并确保集合容量足够,如果需要则增加集合容量。
 *
 * @param minCapacity 所需最小容量
 */
沉默王二's avatar
沉默王二 已提交
139
private void ensureExplicitCapacity(int minCapacity) {
沉默王二's avatar
沉默王二 已提交
140
    // 检查是否超出了数组范围,确保不会溢出
沉默王二's avatar
沉默王二 已提交
141
    if (minCapacity - elementData.length > 0)
沉默王二's avatar
沉默王二 已提交
142
        // 如果需要增加容量,则调用 grow 方法
沉默王二's avatar
沉默王二 已提交
143 144 145 146
        grow(minCapacity);
}
```

沉默王二's avatar
沉默王二 已提交
147 148 149 150 151 152
此时:

- 参数 minCapacity 为 10
- elementData.length 为 0(数组为空)

所以 10-0>0,if 条件为 true,进入 if 语句执行 `grow()` 方法,来看源码:
沉默王二's avatar
沉默王二 已提交
153 154

```java
沉默王二's avatar
沉默王二 已提交
155 156 157 158
/**
 * 扩容 ArrayList 的方法,确保能够容纳指定容量的元素
 * @param minCapacity 指定容量的最小值
 */
沉默王二's avatar
沉默王二 已提交
159
private void grow(int minCapacity) {
沉默王二's avatar
沉默王二 已提交
160
    // 检查是否会导致溢出,oldCapacity 为当前数组长度
沉默王二's avatar
沉默王二 已提交
161
    int oldCapacity = elementData.length;
沉默王二's avatar
沉默王二 已提交
162 163 164 165 166 167
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容至原来的1.5倍
    if (newCapacity - minCapacity < 0) // 如果还是小于指定容量的最小值
        newCapacity = minCapacity; // 直接扩容至指定容量的最小值
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 如果超出了数组的最大长度
        newCapacity = hugeCapacity(minCapacity); // 扩容至数组的最大长度
    // 将当前数组复制到一个新数组中,长度为 newCapacity
沉默王二's avatar
沉默王二 已提交
168 169 170 171
    elementData = Arrays.copyOf(elementData, newCapacity);
}
```

沉默王二's avatar
沉默王二 已提交
172
此时:
沉默王二's avatar
沉默王二 已提交
173

沉默王二's avatar
沉默王二 已提交
174 175
- 参数 minCapacity 为 10
- 变量 oldCapacity 为 0
沉默王二's avatar
沉默王二 已提交
176

沉默王二's avatar
沉默王二 已提交
177
所以 newCapacity 也为 0,于是 `newCapacity - minCapacity` 等于 -10 小于 0,于是第一个 if 条件为 true,执行第一个 if 语句 `newCapacity = minCapacity`,然后 newCapacity 为 10。
沉默王二's avatar
沉默王二 已提交
178

沉默王二's avatar
沉默王二 已提交
179
紧接着执行 `elementData = Arrays.copyOf(elementData, newCapacity);`,也就是进行数组的第一次扩容,长度为 10。
沉默王二's avatar
沉默王二 已提交
180

沉默王二's avatar
沉默王二 已提交
181
回到 `add()` 方法:
沉默王二's avatar
沉默王二 已提交
182 183

```java
沉默王二's avatar
沉默王二 已提交
184 185 186 187
public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
沉默王二's avatar
沉默王二 已提交
188 189 190
}
```

沉默王二's avatar
沉默王二 已提交
191 192 193 194 195 196 197 198 199 200 201 202 203 204 205
执行 `elementData[size++] = e`

此时:

- size 为 0
- e 为 “沉默王二”

所以数组的第一个元素(下标为 0) 被赋值为“沉默王二”,接着返回 true,第一次 add 方法执行完毕。

PS:add 过程中会遇到一个令新手感到困惑的右移操作符 `>>`,借这个机会来解释一下。

ArrayList 在第一次执行 add 后会扩容为 10,那 ArrayList 第二次扩容发生在什么时候呢?

答案是添加第 11 个元素时,大家可以尝试分析一下这个过程。

沉默王二's avatar
沉默王二 已提交
206
### 03、右移操作符
沉默王二's avatar
沉默王二 已提交
207

沉默王二's avatar
沉默王二 已提交
208 209 210 211 212 213 214 215 216 217
“oldCapacity 等于 10,`oldCapacity >> 1` 这个表达式等于多少呢?三妹你知道吗?”我问三妹。

“不知道啊,`>>` 是什么意思呢?”三妹很疑惑。

`>>` 是右移运算符,`oldCapacity >> 1` 相当于 oldCapacity 除以 2。”我给三妹解释道,“在计算机内部,都是按照二进制存储的,10 的二进制就是 1010,也就是 `0*2^0 + 1*2^1 + 0*2^2 + 1*2^3`=0+2+0+8=10 。。。。。。”

还没等我解释完,三妹就打断了我,“二哥,能再详细解释一下到底为什么吗?”

“当然可以啊。”我拍着胸脯对三妹说。

沉默王二's avatar
沉默王二 已提交
218
先从位权的含义说起吧。
沉默王二's avatar
沉默王二 已提交
219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239

平常我们使用的是十进制数,比如说 39,并不是简单的 3 和 9,3 表示的是 `3*10 = 30`,9 表示的是 `9*1 = 9`,和 3 相乘的 10,和 9 相乘的 1,就是**位权**。位数不同,位权就不同,第 1 位是 10 的 0 次方(也就是 `10^0=1`),第 2 位是 10 的 1 次方(`10^1=10`),第 3 位是 10 的 2 次方(`10^2=100`),最右边的是第一位,依次类推。

位权这个概念同样适用于二进制,第 1 位是 2 的 0 次方(也就是 `2^0=1`),第 2 位是 2 的 1 次方(`2^1=2`),第 3 位是 2 的 2 次方(`2^2=4`),第 34 位是 2 的 3 次方(`2^3=8`)。

十进制的情况下,10 是基数,二进制的情况下,2 是基数。

10 在十进制的表示法是 `0*10^0+1*10^1`=0+10=10。

10 的二进制数是 1010,也就是 `0*2^0 + 1*2^1 + 0*2^2 + 1*2^3`=0+2+0+8=10。

然后是**移位运算**,移位分为左移和右移,在 Java 中,左移的运算符是 `<<`,右移的运算符 `>>`

`oldCapacity >> 1` 来说吧,`>>` 左边的是被移位的值,此时是 10,也就是二进制 `1010``>>` 右边的是要移位的位数,此时是 1。

1010 向右移一位就是 101,空出来的最高位此时要补 0,也就是 0101。

“那为什么不补 1 呢?”三妹这个问题很尖锐。

“因为是算术右移,并且是正数,所以最高位补 0;如果表示的是负数,就需要补 1。”我慢吞吞地回答道,“0101 的十进制就刚好是 `1*2^0 + 0*2^1 + 1*2^2 + 0*2^3`=1+0+4+0=5,如果多移几个数来找规律的话,就会发现,右移 1 位是原来的 1/2,右移 2 位是原来的 1/4,诸如此类。”

沉默王二's avatar
沉默王二 已提交
240 241 242 243 244
也就是说,ArrayList 的大小会扩容为原来的大小+原来大小/2,也就是 1.5 倍。

这下明白了吧?

你可以通过在 ArrayList 中添加第 11 个元素来 debug 验证一下。
沉默王二's avatar
沉默王二 已提交
245

沉默王二's avatar
沉默王二 已提交
246
![](http://cdn.tobebetterjavaer.com/tobebetterjavaer/images/collection//arraylist-d01f248c-114f-47e3-af18-7135feac2a5e.png)
沉默王二's avatar
沉默王二 已提交
247

沉默王二's avatar
沉默王二 已提交
248
### 04、向 ArrayList 的指定位置添加元素
沉默王二's avatar
沉默王二 已提交
249 250

除了 `add(E e)` 方法,还可以通过 `add(int index, E element)` 方法把元素添加到 ArrayList 的指定位置:
沉默王二's avatar
沉默王二 已提交
251 252 253 254 255

```java
alist.add(0, "沉默王三");
```

沉默王二's avatar
沉默王二 已提交
256
`add(int index, E element)` 方法的源码如下:
沉默王二's avatar
沉默王二 已提交
257 258

```java
沉默王二's avatar
沉默王二 已提交
259 260 261 262 263 264 265
/**
 * 在指定位置插入一个元素。
 *
 * @param index   要插入元素的位置
 * @param element 要插入的元素
 * @throws IndexOutOfBoundsException 如果索引超出范围,则抛出此异常
 */
沉默王二's avatar
沉默王二 已提交
266
public void add(int index, E element) {
沉默王二's avatar
沉默王二 已提交
267
    rangeCheckForAdd(index); // 检查索引是否越界
沉默王二's avatar
沉默王二 已提交
268

沉默王二's avatar
沉默王二 已提交
269
    ensureCapacityInternal(size + 1);  // 确保容量足够,如果需要扩容就扩容
沉默王二's avatar
沉默王二 已提交
270
    System.arraycopy(elementData, index, elementData, index + 1,
沉默王二's avatar
沉默王二 已提交
271 272 273
            size - index); // 将 index 及其后面的元素向后移动一位
    elementData[index] = element; // 将元素插入到指定位置
    size++; // 元素个数加一
沉默王二's avatar
沉默王二 已提交
274 275 276
}
```

沉默王二's avatar
沉默王二 已提交
277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298
`add(int index, E element)`方法会调用到一个非常重要的[本地方法](https://tobebetterjavaer.com/oo/native-method.html) `System.arraycopy()`,它会对数组进行复制(要插入位置上的元素往后复制)。

来细品一下。

这是 arraycopy() 的语法:

```java
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
```

`ArrayList.add(int index, E element)` 方法中,具体用法如下:

```java
System.arraycopy(elementData, index, elementData, index + 1, size - index);
```

- elementData:表示要复制的源数组,即 ArrayList 中的元素数组。
- index:表示源数组中要复制的起始位置,即需要将 index 及其后面的元素向后移动一位。
- elementData:表示要复制到的目标数组,即 ArrayList 中的元素数组。
- index + 1:表示目标数组中复制的起始位置,即将 index 及其后面的元素向后移动一位后,应该插入到的位置。
- size - index:表示要复制的元素个数,即需要将 index 及其后面的元素向后移动一位,需要移动的元素个数为 size - index。

沉默王二's avatar
沉默王二 已提交
299 300 301

“三妹,注意看,我画幅图来表示下。”我认真地做起了图。

沉默王二's avatar
沉默王二 已提交
302
![](https://cdn.tobebetterjavaer.com/tobebetterjavaer/images/collection/arraylist-01.png)
沉默王二's avatar
沉默王二 已提交
303

沉默王二's avatar
沉默王二 已提交
304
### 05、更新 ArrayList 中的元素
沉默王二's avatar
沉默王二 已提交
305 306 307 308 309 310 311 312 313 314 315 316 317 318

“二哥,那怎么**更新 ArrayList 中的元素**呢?”三妹继续问。

可以使用 `set()` 方法来更改 ArrayList 中的元素,需要提供下标和新元素。

```java
alist.set(0, "沉默王四");
```

假设原来 0 位置上的元素为“沉默王三”,现在可以将其更新为“沉默王四”。

来看一下 `set()` 方法的源码:

```java
沉默王二's avatar
沉默王二 已提交
319 320 321 322 323 324 325 326
/**
 * 用指定元素替换指定位置的元素。
 *
 * @param index   要替换的元素的索引
 * @param element 要存储在指定位置的元素
 * @return 先前在指定位置的元素
 * @throws IndexOutOfBoundsException 如果索引超出范围,则抛出此异常
 */
沉默王二's avatar
沉默王二 已提交
327
public E set(int index, E element) {
沉默王二's avatar
沉默王二 已提交
328
    rangeCheck(index); // 检查索引是否越界
沉默王二's avatar
沉默王二 已提交
329

沉默王二's avatar
沉默王二 已提交
330 331 332
    E oldValue = elementData(index); // 获取原来在指定位置上的元素
    elementData[index] = element; // 将新元素替换到指定位置上
    return oldValue; // 返回原来在指定位置上的元素
沉默王二's avatar
沉默王二 已提交
333 334 335 336 337
}
```

该方法会先对指定的下标进行检查,看是否越界,然后替换新值并返回旧值。

沉默王二's avatar
沉默王二 已提交
338
### 06、删除 ArrayList 中的元素
沉默王二's avatar
沉默王二 已提交
339

沉默王二's avatar
沉默王二 已提交
340 341 342 343 344 345 346 347 348 349 350 351
“二哥,那怎么**删除 ArrayList 中的元素**呢?”三妹继续问。

`remove(int index)` 方法用于删除指定下标位置上的元素,`remove(Object o)` 方法用于删除指定值的元素。

```java
alist.remove(1);
alist.remove("沉默王四");
```

先来看 `remove(int index)` 方法的源码:

```java
沉默王二's avatar
沉默王二 已提交
352 353 354 355 356 357 358
/**
 * 删除指定位置的元素。
 *
 * @param index 要删除的元素的索引
 * @return 先前在指定位置的元素
 * @throws IndexOutOfBoundsException 如果索引超出范围,则抛出此异常
 */
沉默王二's avatar
沉默王二 已提交
359
public E remove(int index) {
沉默王二's avatar
沉默王二 已提交
360
    rangeCheck(index); // 检查索引是否越界
沉默王二's avatar
沉默王二 已提交
361

沉默王二's avatar
沉默王二 已提交
362
    E oldValue = elementData(index); // 获取要删除的元素
沉默王二's avatar
沉默王二 已提交
363

沉默王二's avatar
沉默王二 已提交
364 365
    int numMoved = size - index - 1; // 计算需要移动的元素个数
    if (numMoved > 0) // 如果需要移动元素,就用 System.arraycopy 方法实现
沉默王二's avatar
沉默王二 已提交
366 367
        System.arraycopy(elementData, index+1, elementData, index,
                numMoved);
沉默王二's avatar
沉默王二 已提交
368
    elementData[--size] = null; // 将数组末尾的元素置为 null,让 GC 回收该元素占用的空间
沉默王二's avatar
沉默王二 已提交
369

沉默王二's avatar
沉默王二 已提交
370
    return oldValue; // 返回被删除的元素
沉默王二's avatar
沉默王二 已提交
371 372 373
}
```

沉默王二's avatar
沉默王二 已提交
374
需要注意的是,在 ArrayList 中,删除元素时,需要将删除位置后面的元素向前移动一位,以填补删除位置留下的空缺。如果需要移动元素,则需要使用 System.arraycopy 方法将删除位置后面的元素向前移动一位。最后,将数组末尾的元素置为 null,以便让垃圾回收机制回收该元素占用的空间。
沉默王二's avatar
沉默王二 已提交
375 376 377 378

再来看 `remove(Object o)` 方法的源码:

```java
沉默王二's avatar
沉默王二 已提交
379 380 381 382 383 384
/**
 * 删除列表中第一次出现的指定元素(如果存在)。
 *
 * @param o 要删除的元素
 * @return 如果列表包含指定元素,则返回 true;否则返回 false
 */
沉默王二's avatar
沉默王二 已提交
385
public boolean remove(Object o) {
沉默王二's avatar
沉默王二 已提交
386 387 388 389 390
    if (o == null) { // 如果要删除的元素是 null
        for (int index = 0; index < size; index++) // 遍历列表
            if (elementData[index] == null) { // 如果找到了 null 元素
                fastRemove(index); // 调用 fastRemove 方法快速删除元素
                return true; // 返回 true,表示成功删除元素
沉默王二's avatar
沉默王二 已提交
391
            }
沉默王二's avatar
沉默王二 已提交
392 393 394 395 396
    } else { // 如果要删除的元素不是 null
        for (int index = 0; index < size; index++) // 遍历列表
            if (o.equals(elementData[index])) { // 如果找到了要删除的元素
                fastRemove(index); // 调用 fastRemove 方法快速删除元素
                return true; // 返回 true,表示成功删除元素
沉默王二's avatar
沉默王二 已提交
397 398
            }
    }
沉默王二's avatar
沉默王二 已提交
399
    return false; // 如果找不到要删除的元素,则返回 false
沉默王二's avatar
沉默王二 已提交
400 401 402
}
```

沉默王二's avatar
沉默王二 已提交
403 404 405 406 407 408
该方法通过遍历的方式找到要删除的元素,null 的时候使用 == 操作符判断,非 null 的时候使用 `equals()` 方法,然后调用 `fastRemove()` 方法。

注意:

- 有相同元素时,只会删除第一个。
- 判断两个元素是否相等,可以参考[Java如何判断两个字符串是否相等](https://tobebetterjavaer.com/string/equals.html)
沉默王二's avatar
沉默王二 已提交
409

沉默王二's avatar
沉默王二 已提交
410
继续往后面跟,来看一下 `fastRemove()` 方法:
沉默王二's avatar
沉默王二 已提交
411 412

```java
沉默王二's avatar
沉默王二 已提交
413 414 415 416 417
/**
 * 快速删除指定位置的元素。
 *
 * @param index 要删除的元素的索引
 */
沉默王二's avatar
沉默王二 已提交
418
private void fastRemove(int index) {
沉默王二's avatar
沉默王二 已提交
419 420
    int numMoved = size - index - 1; // 计算需要移动的元素个数
    if (numMoved > 0) // 如果需要移动元素,就用 System.arraycopy 方法实现
沉默王二's avatar
沉默王二 已提交
421 422
        System.arraycopy(elementData, index+1, elementData, index,
                numMoved);
沉默王二's avatar
沉默王二 已提交
423
    elementData[--size] = null; // 将数组末尾的元素置为 null,让 GC 回收该元素占用的空间
沉默王二's avatar
沉默王二 已提交
424 425 426 427 428 429 430
}
```

同样是调用 `System.arraycopy()` 方法对数组进行复制和移动。

“三妹,注意看,我画幅图来表示下。”我认真地做起了图。

沉默王二's avatar
沉默王二 已提交
431
![](https://cdn.tobebetterjavaer.com/tobebetterjavaer/images/collection/arraylist-02.png)
沉默王二's avatar
沉默王二 已提交
432

沉默王二's avatar
沉默王二 已提交
433
### 07、查找 ArrayList 中的元素
沉默王二's avatar
沉默王二 已提交
434 435 436 437 438 439 440 441 442 443 444 445 446

“二哥,那怎么**查找 ArrayList 中的元素**呢?”三妹继续问。

如果要正序查找一个元素,可以使用 `indexOf()` 方法;如果要倒序查找一个元素,可以使用 `lastIndexOf()` 方法。

```java
alist.indexOf("沉默王二");
alist.lastIndexOf("沉默王二");
```

来看一下 `indexOf()` 方法的源码:

```java
沉默王二's avatar
沉默王二 已提交
447 448 449 450 451 452 453
/**
 * 返回指定元素在列表中第一次出现的位置。
 * 如果列表不包含该元素,则返回 -1。
 *
 * @param o 要查找的元素
 * @return 指定元素在列表中第一次出现的位置;如果列表不包含该元素,则返回 -1
 */
沉默王二's avatar
沉默王二 已提交
454
public int indexOf(Object o) {
沉默王二's avatar
沉默王二 已提交
455 456 457 458 459 460 461 462
    if (o == null) { // 如果要查找的元素是 null
        for (int i = 0; i < size; i++) // 遍历列表
            if (elementData[i]==null) // 如果找到了 null 元素
                return i; // 返回元素的索引
    } else { // 如果要查找的元素不是 null
        for (int i = 0; i < size; i++) // 遍历列表
            if (o.equals(elementData[i])) // 如果找到了要查找的元素
                return i; // 返回元素的索引
沉默王二's avatar
沉默王二 已提交
463
    }
沉默王二's avatar
沉默王二 已提交
464
    return -1; // 如果找不到要查找的元素,则返回 -1
沉默王二's avatar
沉默王二 已提交
465 466 467 468 469 470 471
}
```

如果元素为 null 的时候使用“==”操作符,否则使用 `equals()` 方法。

`lastIndexOf()` 方法和 `indexOf()` 方法类似,不过遍历的时候从最后开始。

沉默王二's avatar
沉默王二 已提交
472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494
```java
/**
 * 返回指定元素在列表中最后一次出现的位置。
 * 如果列表不包含该元素,则返回 -1。
 *
 * @param o 要查找的元素
 * @return 指定元素在列表中最后一次出现的位置;如果列表不包含该元素,则返回 -1
 */
public int lastIndexOf(Object o) {
    if (o == null) { // 如果要查找的元素是 null
        for (int i = size-1; i >= 0; i--) // 从后往前遍历列表
            if (elementData[i]==null) // 如果找到了 null 元素
                return i; // 返回元素的索引
    } else { // 如果要查找的元素不是 null
        for (int i = size-1; i >= 0; i--) // 从后往前遍历列表
            if (o.equals(elementData[i])) // 如果找到了要查找的元素
                return i; // 返回元素的索引
    }
    return -1; // 如果找不到要查找的元素,则返回 -1
}
```

`contains()` 方法可以判断 ArrayList 中是否包含某个元素,其内部就是通过 `indexOf()` 方法实现的:
沉默王二's avatar
沉默王二 已提交
495 496 497 498 499 500 501

```java
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
```

沉默王二's avatar
沉默王二 已提交
502
### 08、二分查找法
沉默王二's avatar
沉默王二 已提交
503

沉默王二's avatar
沉默王二 已提交
504 505
如果 ArrayList 中的元素是经过排序的,就可以使用二分查找法,效率更快。

沉默王二's avatar
沉默王二 已提交
506 507 508
[`Collections`](https://tobebetterjavaer.com/common-tool/collections.html) 类的 `sort()` 方法可以对 ArrayList 进行排序,该方法会按照字母顺序对 String 类型的列表进行排序。如果是自定义类型的列表,还可以指定 Comparator 进行排序。

这里先简单地了解一下,后面会详细地讲。
沉默王二's avatar
沉默王二 已提交
509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532

```java
List<String> copy = new ArrayList<>(alist);
copy.add("a");
copy.add("c");
copy.add("b");
copy.add("d");

Collections.sort(copy);
System.out.println(copy);
```

输出结果如下所示:

```
[a, b, c, d]
```

排序后就可以使用二分查找法了:

```java
int index = Collections.binarySearch(copy, "b");
```

沉默王二's avatar
沉默王二 已提交
533
### 09、ArrayList增删改查时的时间复杂度
沉默王二's avatar
沉默王二 已提交
534

沉默王二's avatar
沉默王二 已提交
535
“最后,三妹,我们来简单总结一下 ArrayList 的时间复杂度吧,方便后面学习 LinkedList 时对比。”我喝了一口水后补充道。
沉默王二's avatar
沉默王二 已提交
536

沉默王二's avatar
沉默王二 已提交
537 538 539
#### 1)查询

时间复杂度为 O(1),因为 ArrayList 内部使用数组来存储元素,所以可以直接根据索引来访问元素。
沉默王二's avatar
沉默王二 已提交
540 541

```java
沉默王二's avatar
沉默王二 已提交
542 543 544 545 546 547 548
/**
 * 返回列表中指定位置的元素。
 *
 * @param index 要返回的元素的索引
 * @return 列表中指定位置的元素
 * @throws IndexOutOfBoundsException 如果索引超出范围(index < 0 || index >= size())
 */
沉默王二's avatar
沉默王二 已提交
549
public E get(int index) {
沉默王二's avatar
沉默王二 已提交
550 551 552
    rangeCheck(index); // 检查索引是否合法
    return elementData(index); // 调用 elementData 方法获取元素
}
沉默王二's avatar
沉默王二 已提交
553

沉默王二's avatar
沉默王二 已提交
554 555 556 557 558 559 560 561 562
/**
 * 返回列表中指定位置的元素。
 * 此方法不进行边界检查,因此只应由内部方法和迭代器调用。
 *
 * @param index 要返回的元素的索引
 * @return 列表中指定位置的元素
 */
E elementData(int index) {
    return (E) elementData[index]; // 返回指定索引位置上的元素
沉默王二's avatar
沉默王二 已提交
563 564 565
}
```

沉默王二's avatar
沉默王二 已提交
566 567 568 569 570 571 572 573 574 575 576 577 578
#### 2)插入

添加一个元素(调用 `add()` 方法时)的时间复杂度最好情况为 O(1),最坏情况为 O(n)。

- 如果在列表末尾添加元素,时间复杂度为 O(1)。
- 如果要在列表的中间或开头插入元素,则需要将插入位置之后的元素全部向后移动一位,时间复杂度为 O(n)。

#### 3)删除

删除一个元素(调用 `remove(Object)` 方法时)的时间复杂度最好情况 O(1),最坏情况 O(n)。

- 如果要删除列表末尾的元素,时间复杂度为 O(1)。
- 如果要删除列表中间或开头的元素,则需要将删除位置之后的元素全部向前移动一位,时间复杂度为 O(n)。
沉默王二's avatar
沉默王二 已提交
579 580


沉默王二's avatar
沉默王二 已提交
581
#### 4)修改
沉默王二's avatar
沉默王二 已提交
582

沉默王二's avatar
沉默王二 已提交
583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603
修改一个元素(调用 `set()`方法时)与查询操作类似,可以直接根据索引来访问元素,时间复杂度为 O(1)。

```java
/**
 * 用指定元素替换列表中指定位置的元素。
 *
 * @param index 要替换元素的索引
 * @param element 要放入列表中的元素
 * @return 原来在指定位置上的元素
 * @throws IndexOutOfBoundsException 如果索引超出范围(index < 0 || index >= size())
 */
public E set(int index, E element) {
    rangeCheck(index); // 检查索引是否合法

    E oldValue = elementData(index); // 获取原来在指定位置上的元素
    elementData[index] = element; // 将指定位置上的元素替换为新元素
    return oldValue; // 返回原来在指定位置上的元素
}
```

### 10、总结
沉默王二's avatar
沉默王二 已提交
604 605 606 607 608 609 610

ArrayList,如果有个中文名的话,应该叫动态数组,也就是可增长的数组,可调整大小的数组。动态数组克服了静态数组的限制,静态数组的容量是固定的,只能在首次创建的时候指定。而动态数组会随着元素的增加自动调整大小,更符合实际的开发需求。

学习集合框架,ArrayList 是第一课,也是新手进阶的重要一课。要想完全掌握 ArrayList,扩容这个机制是必须得掌握,也是面试中经常考察的一个点。

要想掌握扩容机制,就必须得读源码,也就肯定会遇到 `oldCapacity >> 1`,有些初学者会选择跳过,虽然不影响整体上的学习,但也错过了一个精进的机会。

沉默王二's avatar
jvm  
沉默王二 已提交
611 612
计算机内部是如何表示十进制数的,右移时又发生了什么,静下心来去研究一下,你就会发现,哦,原来这么有趣呢?

沉默王二's avatar
沉默王二 已提交
613 614
“好了,三妹,这一节我们就学到这里,收工!”

沉默王二's avatar
沉默王二 已提交
615 616 617 618
----

最近整理了一份牛逼的学习资料,包括但不限于Java基础部分(JVM、Java集合框架、多线程),还囊括了 **数据库、计算机网络、算法与数据结构、设计模式、框架类Spring、Netty、微服务(Dubbo,消息队列) 网关** 等等等等……详情戳:[可以说是2022年全网最全的学习和找工作的PDF资源了](https://tobebetterjavaer.com/pdf/programmer-111.html)

沉默王二's avatar
沉默王二 已提交
619
微信搜 **沉默王二** 或扫描下方二维码关注二哥的原创公众号沉默王二,回复 **111** 即可免费领取。
沉默王二's avatar
沉默王二 已提交
620

沉默王二's avatar
沉默王二 已提交
621
![](https://cdn.tobebetterjavaer.com/tobebetterjavaer/images/gongzhonghao.png)