ArrayList(附源码)

字数: 0 字时长: 0 分钟

1. ArrayList 概述

从名字就可以看出来，ArrayList 实现了 List 接口，并且底层基于数组实现。

普通数组的大小是固定的，一旦创建时指定了长度，就不能再动态调整：

java

String[] array =
        new String[10];

而 ArrayList 在数组的基础上实现了：

text

自动扩容

增删改查

动态调整容量

可以简单理解：

text

普通数组
    ↓
长度固定


ArrayList
    ↓
动态数组
    ↓
容量不足时自动扩容

如果使用 C 语言，这类动态数组通常需要自己实现，而 Java 已经在集合框架中提供了完整实现。

2. 创建 ArrayList

最基本的创建方式：

java

ArrayList<String> list =
        new ArrayList<String>();

尖括号：

java

<String>

用于限定 ArrayList 中元素的类型。

如果添加其他类型：

java

// 编译错误
// list.add(100);

现代 Java 一般简写：

java

List<String> list =
        new ArrayList<>();

因为：

text

ArrayList
    ↓
实现 List 接口

所以变量类型可以声明为：

java

List

右侧：

java

new ArrayList<>();

中的类型参数也可以由编译器自动推断。

2.1 无参构造方法

无参创建：

java

List<String> list =
        new ArrayList<>();

会调用：

java

public ArrayList() {

    this.elementData =
            DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

此时：

java

DEFAULTCAPACITY_EMPTY_ELEMENTDATA

对应一个空数组：

text

{}

也就是说：

text

new ArrayList<>()
    ↓
先创建一个空的 ArrayList
    ↓
第一次真正添加元素时再进行容量处理

2.2 指定初始容量

如果比较确定集合中大概会保存多少个元素，可以在创建时指定初始容量：

java

List<String> list =
        new ArrayList<>(20);

这样可以减少后续：

text

扩容

数组复制

的次数。

3. 向 ArrayList 中添加元素

可以通过：

java

add()

向 ArrayList 中添加元素。

例如：

java

list.add(
        "张无忌"
);

先看一下添加元素的大致过程：

text

add(element)
    ↓
判断容量是否足够
    ↓
容量不足
    ↓
grow()
    ↓
计算新的数组容量
    ↓
Arrays.copyOf()
    ↓
创建更大的数组
    ↓
elementData[size++] = element
    ↓
添加元素

原来的过程可以概括为：

text

add(element)
└── 判断是否需要扩容
    ├── grow(minCapacity)
    │   ├── oldCapacity + (oldCapacity >> 1)
    │   └── Arrays.copyOf(elementData, newCapacity)
    │
    ├── elementData[size++] = element
    └── return true

3.1 add() 源码

java

/**
 * 将指定元素添加到 ArrayList 的末尾
 *
 * @param e 要添加的元素
 * @return 添加成功返回 true
 */
public boolean add(E e) {

    // 确保能够容纳新的元素
    ensureCapacityInternal(
            size + 1
    );

    // 将元素添加到数组末尾
    elementData[size++] = e;

    return true;
}

假设：

java

list.add(
        "张无忌"
);

第一次执行时：

text

e
    ↓
"张无忌"


size
    ↓
0

首先执行：

java

ensureCapacityInternal(
        size + 1
);

也就是：

java

ensureCapacityInternal(1);

3.2 ensureCapacityInternal()

源码：

java

/**
 * 确保 ArrayList 能够容纳指定容量的元素
 *
 * @param minCapacity 所需的最小容量
 */
private void ensureCapacityInternal(
        int minCapacity) {

    if (
            elementData
                    == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    ) {

        minCapacity =
                Math.max(
                        DEFAULT_CAPACITY,
                        minCapacity
                );
    }

    ensureExplicitCapacity(
            minCapacity
    );
}

第一次添加元素时：

text

minCapacity = 1

elementData = {}

DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}

所以：

java

elementData
        == DEFAULTCAPACITY_EMPTY_ELEMENTDATA

成立。

继续执行：

java

minCapacity =
        Math.max(
                DEFAULT_CAPACITY,
                minCapacity
        );

其中：

java

private static final int
        DEFAULT_CAPACITY = 10;

于是：

text

Math.max(10, 1)
    ↓
10

最终：

text

minCapacity = 10

3.3 ensureExplicitCapacity()

接下来调用：

java

ensureExplicitCapacity(
        minCapacity
);

源码：

java

/**
 * 检查当前数组容量是否足够
 *
 * @param minCapacity 所需最小容量
 */
private void ensureExplicitCapacity(
        int minCapacity) {

    if (
            minCapacity
                    - elementData.length
                    > 0
    ) {

        grow(
                minCapacity
        );
    }
}

此时：

text

minCapacity = 10

elementData.length = 0

所以：

text

10 - 0 > 0

条件成立。

于是进入：

java

grow(
        minCapacity
);

3.4 grow()

源码：

java

/**
 * 扩容 ArrayList
 *
 * @param minCapacity 所需最小容量
 */
private void grow(
        int minCapacity) {

    // 当前数组容量
    int oldCapacity =
            elementData.length;

    // 新容量 = 原容量 + 原容量的一半
    int newCapacity =
            oldCapacity
                    + (
                    oldCapacity
                            >> 1
            );

    if (
            newCapacity
                    - minCapacity
                    < 0
    ) {

        newCapacity =
                minCapacity;
    }

    if (
            newCapacity
                    - MAX_ARRAY_SIZE
                    > 0
    ) {

        newCapacity =
                hugeCapacity(
                        minCapacity
                );
    }

    // 创建新数组并复制原数组内容
    elementData =
            Arrays.copyOf(
                    elementData,
                    newCapacity
            );
}

第一次扩容时：

text

oldCapacity = 0

minCapacity = 10

计算：

java

int newCapacity =
        oldCapacity
                + (
                oldCapacity
                        >> 1
        );

得到：

text

newCapacity = 0

然后：

java

newCapacity - minCapacity
    ↓
0 - 10
    ↓
-10

条件成立：

java

newCapacity =
        minCapacity;

于是：

text

newCapacity = 10

最后执行：

java

elementData =
        Arrays.copyOf(
                elementData,
                newCapacity
        );

完成第一次扩容：

text

0
    ↓
10

3.5 第一次 add() 完成

扩容完成以后回到：

java

add()

java

public boolean add(E e) {

    ensureCapacityInternal(
            size + 1
    );

    elementData[size++] = e;

    return true;
}

执行：

java

elementData[size++] = e;

此时：

text

size = 0

e = "张无忌"

所以：

text

elementData[0]
    ↓
"张无忌"

然后：

text

size
    ↓
1

第一次：

java

add()

执行完成。

4. 右移操作符

扩容源码中有一句：

java

oldCapacity
        >> 1

这里：

java

>>

是 Java 的：

text

右移运算符

例如：

text

oldCapacity = 10

那么：

java

oldCapacity >> 1

结果是多少？

4.1 十进制与二进制

十进制：

text

写成：

text

0 × 10⁰
+
1 × 10¹
=
10

十进制的基数是：

text

而二进制的基数是：

text

十进制：

text

对应的二进制：

text

计算：

text

0 × 2⁰
+
1 × 2¹
+
0 × 2²
+
1 × 2³

=
0 + 2 + 0 + 8

=
10

这里涉及：

text

位权

例如二进制：

text

第 1 位
    ↓
2⁰


第 2 位
    ↓
2¹


第 3 位
    ↓
2²


第 4 位
    ↓
2³

4.2 右移

Java 中：

text

<<
    ↓
左移


>>
    ↓
右移

对于：

java

10 >> 1

首先：

text

10
    ↓
1010

向右移动一位：

text

1010
    ↓
0101

0101 转换成十进制：

text

1 × 2⁰
+
0 × 2¹
+
1 × 2²
+
0 × 2³

=
1 + 0 + 4 + 0

=
5

所以：

java

10 >> 1

结果：

text

对于正数来说，可以简单理解：

text

右移 1 位
    ↓
除以 2


右移 2 位
    ↓
除以 4

因此：

java

oldCapacity
        + (
        oldCapacity >> 1
)

相当于：

text

原容量
+
原容量 / 2

也就是：

text

约 1.5 倍

所以容量为：

text

时，下一次扩容计算：

text

10 + 5
    ↓
15

添加第 11 个元素时，可以通过 Debug 观察扩容过程：

5. 向指定位置添加元素

除了：

java

add(E e)

还可以通过：

java

add(
        int index,
        E element
)

向指定位置插入元素。

例如：

java

list.add(
        0,
        "赵敏"
);

源码：

java

/**
 * 在指定位置插入一个元素
 *
 * @param index 要插入的位置
 * @param element 要插入的元素
 * @throws IndexOutOfBoundsException
 *         如果索引越界
 */
public void add(
        int index,
        E element) {

    // 检查索引是否合法
    rangeCheckForAdd(
            index
    );

    // 确保容量足够
    ensureCapacityInternal(
            size + 1
    );

    // 将 index 以及后面的元素向后移动
    System.arraycopy(
            elementData,
            index,
            elementData,
            index + 1,
            size - index
    );

    // 插入新元素
    elementData[index] =
            element;

    size++;
}

这里会调用一个非常重要的本地方法：

java

System.arraycopy()

它负责：

text

复制数组元素

移动数组元素

5.1 System.arraycopy()

基本语法：

java

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

在：

java

ArrayList.add(
        int index,
        E element
)

中：

java

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

参数分别表示：

text

elementData
    ↓
源数组


index
    ↓
从源数组哪个位置开始复制


elementData
    ↓
目标数组


index + 1
    ↓
复制到目标数组哪个位置


size - index
    ↓
需要复制多少个元素

也就是：

text

index 及其后面的元素
    ↓
整体向后移动一位
    ↓
腾出 index 位置
    ↓
插入新元素

示意图：

6. 更新 ArrayList 中的元素

可以使用：

java

set()

修改指定位置上的元素。

例如：

java

list.set(
        0,
        "张三丰"
);

假设：

text

index = 0

原元素 = 张无忌

执行以后：

text

张无忌
    ↓
张三丰

源码：

java

/**
 * 用指定元素替换指定位置的元素
 *
 * @param index 要替换的位置
 * @param element 新元素
 * @return 原来位于该位置的元素
 * @throws IndexOutOfBoundsException
 *         如果索引越界
 */
public E set(
        int index,
        E element) {

    // 检查索引是否越界
    rangeCheck(
            index
    );

    // 保存旧值
    E oldValue =
            elementData(
                    index
            );

    // 设置新值
    elementData[index] =
            element;

    // 返回旧值
    return oldValue;
}

整个过程：

text

检查 index
    ↓
获取旧值
    ↓
写入新值
    ↓
返回旧值

7. 删除 ArrayList 中的元素

ArrayList 有两种常见删除方式：

java

remove(int index)

remove(Object o)

例如：

java

list.remove(0);

或者：

java

list.remove(
        "张无忌"
);

7.1 remove(int index)

根据下标删除：

java

/**
 * 删除指定位置的元素
 *
 * @param index 要删除的位置
 * @return 被删除的元素
 * @throws IndexOutOfBoundsException
 *         如果索引越界
 */
public E remove(
        int index) {

    // 检查索引是否越界
    rangeCheck(
            index
    );

    // 保存被删除的元素
    E oldValue =
            elementData(
                    index
            );

    // 计算需要移动多少个元素
    int numMoved =
            size
                    - index
                    - 1;

    if (numMoved > 0) {

        // 将后面的元素整体向前移动
        System.arraycopy(
                elementData,
                index + 1,
                elementData,
                index,
                numMoved
        );
    }

    // 将数组最后一个有效位置置为 null
    elementData[--size] =
            null;

    return oldValue;
}

删除中间元素时：

text

删除目标元素
    ↓
后面的元素向前移动一位
    ↓
最后一个位置置为 null

把最后一个位置设为：

java

null

是为了让原来保存的对象引用能够被垃圾回收机制正常回收。

7.2 remove(Object o)

根据元素值删除：

java

/**
 * 删除列表中第一次出现的指定元素
 *
 * @param o 要删除的元素
 * @return 删除成功返回 true
 */
public boolean remove(
        Object o) {

    if (o == null) {

        for (
                int index = 0;
                index < size;
                index++
        ) {

            if (
                    elementData[index]
                            == null
            ) {

                fastRemove(
                        index
                );

                return true;
            }
        }

    } else {

        for (
                int index = 0;
                index < size;
                index++
        ) {

            if (
                    o.equals(
                            elementData[index]
                    )
            ) {

                fastRemove(
                        index
                );

                return true;
            }
        }
    }

    return false;
}

判断方式：

text

元素是 null
    ↓
==


元素不是 null
    ↓
equals()

找到目标以后：

java

fastRemove(
        index
);

需要注意：

如果存在多个相同元素，只会删除第一次出现的那个元素。

7.3 fastRemove()

源码：

java

/**
 * 快速删除指定位置的元素
 *
 * @param index 要删除的位置
 */
private void fastRemove(
        int index) {

    int numMoved =
            size
                    - index
                    - 1;

    if (numMoved > 0) {

        System.arraycopy(
                elementData,
                index + 1,
                elementData,
                index,
                numMoved
        );
    }

    elementData[--size] =
            null;
}

本质仍然是：

text

System.arraycopy()
    ↓
移动后面的元素
    ↓
最后一个位置置为 null

删除过程示意图：

8. 查找 ArrayList 中的元素

常用方法：

text

indexOf()
    ↓
从前往后查找


lastIndexOf()
    ↓
从后往前查找


contains()
    ↓
判断元素是否存在

8.1 indexOf()

例如：

java

list.indexOf(
        "张无忌"
);

源码：

java

/**
 * 返回指定元素第一次出现的位置
 * 如果不存在则返回 -1
 */
public int indexOf(
        Object o) {

    if (o == null) {

        for (
                int i = 0;
                i < size;
                i++
        ) {

            if (
                    elementData[i]
                            == null
            ) {

                return i;
            }
        }

    } else {

        for (
                int i = 0;
                i < size;
                i++
        ) {

            if (
                    o.equals(
                            elementData[i]
                    )
            ) {

                return i;
            }
        }
    }

    return -1;
}

判断逻辑：

text

null
    ↓
==


非 null
    ↓
equals()

如果找到：

text

返回下标

找不到：

text

-1

8.2 lastIndexOf()

倒序查找：

java

list.lastIndexOf(
        "张无忌"
);

源码：

java

/**
 * 返回指定元素最后一次出现的位置
 * 如果不存在则返回 -1
 */
public int lastIndexOf(
        Object o) {

    if (o == null) {

        for (
                int i =
                        size - 1;
                i >= 0;
                i--
        ) {

            if (
                    elementData[i]
                            == null
            ) {

                return i;
            }
        }

    } else {

        for (
                int i =
                        size - 1;
                i >= 0;
                i--
        ) {

            if (
                    o.equals(
                            elementData[i]
                    )
            ) {

                return i;
            }
        }
    }

    return -1;
}

与：

java

indexOf()

基本一致。

区别只是：

text

indexOf()
    ↓
从前向后


lastIndexOf()
    ↓
从后向前

8.3 contains()

判断是否包含某个元素：

java

public boolean contains(
        Object o) {

    return indexOf(o)
            >= 0;
}

所以：

java

contains()

底层实际上就是通过：

java

indexOf()

判断。

9. 二分查找

如果 ArrayList 中的元素已经经过排序，就可以使用：

text

二分查找

例如先准备数据：

java

List<String> copy =
        new ArrayList<>(
                list
        );

copy.add("a");
copy.add("c");
copy.add("b");
copy.add("d");

使用：

java

Collections.sort(
        copy
);

排序以后：

text

[a, b, c, d]

然后进行二分查找：

java

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

所以：

text

未排序
    ↓
Collections.sort()


排序完成
    ↓
Collections.binarySearch()

对于自定义类型，也可以通过：

text

Comparator

指定排序规则。

10. ArrayList 增删改查的时间复杂度

10.1 查询

根据下标查询：

java

get(index)

时间复杂度：

text

O(1)

因为底层是数组，可以直接通过下标访问。

源码：

java

/**
 * 返回列表中指定位置的元素
 */
public E get(
        int index) {

    // 检查索引是否合法
    rangeCheck(
            index
    );

    return elementData(
            index
    );
}

真正读取：

java

E elementData(
        int index) {

    return (E)
            elementData[index];
}

核心就是：

java

elementData[index]

所以：

text

随机访问
    ↓
O(1)

10.2 插入

添加元素：

java

add()

最好情况：

text

O(1)

最坏情况：

text

O(n)

如果直接添加到尾部，而且容量足够：

text

直接写入数组末尾
    ↓
O(1)

如果：

text

容量不足

需要：

text

扩容

复制数组

或者在：

text

开头 / 中间位置插入

需要移动后面的元素：

text

O(n)

所以：

text

尾部添加
    ↓
通常 O(1)


中间 / 开头插入
    ↓
O(n)

10.3 删除

删除元素：

java

remove()

最好情况：

text

O(1)

最坏情况：

text

O(n)

删除最后一个元素时：

text

不需要移动后续元素

效率较高。

删除：

text

开头

中间

位置的元素，需要：

java

System.arraycopy()

将后面的元素整体向前移动：

text

O(n)

10.4 修改

修改：

java

set(index, element)

时间复杂度：

text

O(1)

因为可以通过数组下标直接定位元素。

源码：

java

/**
 * 用指定元素替换列表中指定位置的元素
 */
public E set(
        int index,
        E element) {

    // 检查索引
    rangeCheck(
            index
    );

    // 保存旧值
    E oldValue =
            elementData(
                    index
            );

    // 写入新值
    elementData[index] =
            element;

    return oldValue;
}

最终可以简单总结：

操作	时间复杂度
`get(index)`	`O(1)`
`set(index, element)`	`O(1)`
尾部 `add()`	最好 `O(1)`
指定位置插入	`O(n)`
删除中间元素	`O(n)`
查找元素	`O(n)`

11. 总结

ArrayList 可以简单理解成：

能够自动扩容的动态数组。

普通数组：

text

创建数组
    ↓
长度固定
    ↓
无法动态改变

而：

text

ArrayList
    ↓
底层数组
    ↓
容量不足
    ↓
自动扩容
    ↓
复制到更大的数组

ArrayList 中比较重要的几个点：

text

底层基于数组

支持随机访问

get / set 很快

中间插入删除需要移动元素

容量不足时自动扩容

扩容过程中的核心计算：

java

oldCapacity
        + (
        oldCapacity >> 1
)

也就是：

text

原容量
+
原容量的一半

约等于：

text

1.5 倍

插入和删除时经常会看到：

java

System.arraycopy()

用于：

text

批量复制

移动数组元素

所以理解 ArrayList，核心就是理解：

text

动态数组

扩容

数组复制

随机访问

网站公告

数据结构与算法

操作系统

计算机网络

计算机组成原理

Git

Docker

ArrayList(附源码)

1. ArrayList 概述

2. 创建 ArrayList

2.1 无参构造方法

2.2 指定初始容量

3. 向 ArrayList 中添加元素

3.1 add() 源码

3.2 ensureCapacityInternal()

3.3 ensureExplicitCapacity()

3.4 grow()

3.5 第一次 add() 完成

4. 右移操作符

4.1 十进制与二进制

4.2 右移

5. 向指定位置添加元素

5.1 System.arraycopy()

6. 更新 ArrayList 中的元素

7. 删除 ArrayList 中的元素

7.1 remove(int index)

7.2 remove(Object o)

7.3 fastRemove()

8. 查找 ArrayList 中的元素

8.1 indexOf()

8.2 lastIndexOf()

8.3 contains()

9. 二分查找

10. ArrayList 增删改查的时间复杂度

10.1 查询

10.2 插入

10.3 删除

10.4 修改

11. 总结

网站公告

ArrayList(附源码) ​

1. ArrayList 概述 ​

2. 创建 ArrayList ​

2.1 无参构造方法 ​

2.2 指定初始容量 ​

3. 向 ArrayList 中添加元素 ​

3.1 add() 源码 ​

3.2 ensureCapacityInternal() ​

3.3 ensureExplicitCapacity() ​

3.4 grow() ​

3.5 第一次 add() 完成 ​

4. 右移操作符 ​

4.1 十进制与二进制 ​

4.2 右移 ​

5. 向指定位置添加元素 ​

5.1 System.arraycopy() ​

6. 更新 ArrayList 中的元素 ​

7. 删除 ArrayList 中的元素 ​

7.1 remove(int index) ​

7.2 remove(Object o) ​

7.3 fastRemove() ​

8. 查找 ArrayList 中的元素 ​

8.1 indexOf() ​

8.2 lastIndexOf() ​

8.3 contains() ​

9. 二分查找 ​

10. ArrayList 增删改查的时间复杂度 ​

10.1 查询 ​

10.2 插入 ​

10.3 删除 ​

10.4 修改 ​

11. 总结 ​

ArrayList(附源码)

1. ArrayList 概述

2. 创建 ArrayList

2.1 无参构造方法

2.2 指定初始容量

3. 向 ArrayList 中添加元素

3.1 add() 源码

3.2 ensureCapacityInternal()

3.3 ensureExplicitCapacity()

3.4 grow()

3.5 第一次 add() 完成

4. 右移操作符

4.1 十进制与二进制

4.2 右移

5. 向指定位置添加元素

5.1 System.arraycopy()

6. 更新 ArrayList 中的元素

7. 删除 ArrayList 中的元素

7.1 remove(int index)

7.2 remove(Object o)

7.3 fastRemove()

8. 查找 ArrayList 中的元素

8.1 indexOf()

8.2 lastIndexOf()

8.3 contains()

9. 二分查找

10. ArrayList 增删改查的时间复杂度

10.1 查询

10.2 插入

10.3 删除

10.4 修改

11. 总结