Java ArrayList 使用和实现原理

我会带着你远行 2024-03-22 14:29 97阅读 0赞

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

![在这里插入图片描述][c31e2d9ff6304e15ab0bef824831710d.png]

### 一、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);
        }
    }

### 二、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
    }

### 三、Java ArrayList 的常用方法 ###

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

#### add(E e)：添加元素 ####

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

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

#### remove(Object o)：删除元素 ####

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

#### get(int index)：获取元素 ####

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

public E get(int index) {
        rangeCheck(index);
    
        return elementData(index);
    }

#### size()：获取列表大小 ####

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

public int size() {
        return size;
    }

### 四、Java ArrayList 的优缺点 ###

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

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

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

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

### 五、总结 ###

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

[c31e2d9ff6304e15ab0bef824831710d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/18a6538f3a1640cd830d7b189126af69.png