Java ArrayList 使用和实现原理_arraylist是随机插入和获取吗

Java ArrayList 是 Java 标准类库中的一个常用数据结构，它是基于数组实现的可变长度的动态数组。相比于传统的数组，它具有动态扩容、随机访问、快速插入和删除等优势，因此在 Java 开发中被广泛应用。本文将深入探讨 Java ArrayList 的原理，包括实现方式、内部结构、常用方法等，并附上代码和图示说明。

一、Java ArrayList 的实现方式

Java ArrayList 的实现方式是基于数组的动态扩容机制，它在内部维护了一个 Object 类型的数组 elementData，用于存储列表中的元素。在初始化时，ArrayList 会创建一个容量为 10 的数组，当添加元素时，如果数组已满，则会扩容为原来的 1.5 倍大小。这个扩容因子是可以通过构造函数中的参数进行设置的。

public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;

    // 存储元素的数组
    transient Object[] elementData;

    // 列表中元素的数量
    private int size;

    // 构造函数
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = new Object[DEFAULT_CAPACITY];
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    // 默认构造函数
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    // 添加元素
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }

    // 扩容方法
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}
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

二、Java ArrayList 的内部结构

Java ArrayList 内部维护了一个 Object 类型的数组 elementData，用于存储列表中的元素。在添加元素时，ArrayList 会先检查数组是否已满，如果已满则会调用扩容方法 grow() 进行数组的扩容。扩容会创建一个新的更大的数组，并将原数组中的元素复制到新数组中。扩容后，ArrayList 会将新数组赋值给 elementData，从而完成扩容。

在删除元素时，ArrayList 会将指定位置之后的元素向前移动一位，覆盖被删除的元素，然后将数组的长度减 1，从而完成元素的删除。

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;
}

private void fastRemove(int index) {
    // modCount 记录修改次数，用于 fail-fast 机制
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}
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

三、Java ArrayList 的常用方法

Java ArrayList 提供了许多常用方法，如添加元素、删除元素、获取元素等。下面将介绍其中的几个重要的方法。

add(E e)：添加元素

add() 方法用于在列表的末尾添加元素。如果数组已满，则会自动扩容。该方法返回一个 boolean 类型的值，表示是否添加成功。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}
1
2
3
4
5

remove(Object o)：删除元素

remove() 方法用于从列表中删除指定的元素。如果列表中不存在该元素，则不会进行任何操作。该方法返回一个 boolean 类型的值，表示是否删除成功。

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

get(int index)：获取元素

get() 方法用于获取列表中指定位置的元素。如果索引超出了列表的范围，则会抛出 IndexOutOfBoundsException 异常。

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}
1
2
3
4
5

size()：获取列表大小

size() 方法用于获取列表中元素的数量。

public int size() {
    return size;
}
1
2
3

四、Java ArrayList 的优缺点

Java ArrayList 作为一种动态数组，具有以下优点：

1. 可以快速地随机访问元素，因为它是基于数组实现的。
2. 可以快速地在列表末尾添加元素，因为它的添加操作只需要在数组末尾插入元素即可。
3. 可以快速地删除元素，因为它的删除操作只需要将指定位置之后的元素向前移动一位，并将数组长度减 1 即可。
4. 可以动态扩容，因此可以避免数组长度不足的问题。
5. 支持泛型，可以存储不同类型的元素。

但是，Java ArrayList 也有以下缺点：

1. 在插入和删除元素时，可能需要移动大量元素，导致性能下降。
2. 在数组扩容时，需要重新创建一个更大的数组，并将原数组中的元素复制到新数组中，这样会消耗更多的内存。
3. 在多线程环境下，可能存在并发修改的问题。

五、总结

Java ArrayList 是一种基于数组实现的动态数组，它具有快速随机访问、快速插入和删除、动态扩容等优点，在 Java 开发中被广泛应用。本文从 Java ArrayList 的实现方式、内部结构、常用方法和优缺点等方面进行了深入的讲解，并附上了代码和图示说明。在使用 Java ArrayList 时，需要根据具体的场景选择合适的容量、扩容因子等参数，以及注意并发修改的问题。