在Java中，ArrayList是一个动态数组的实现，提供了对元素的动态增删改查操作。理解ArrayList的插入和删除操作的时间复杂度对优化代码性能至关重要。

插入操作的时间复杂度

头部插入

在ArrayList的头部插入元素时，需要将所有现有元素向后移动一个位置，以腾出空间给新元素。这意味着每次插入操作都需要移动n个元素（假设当前数组中有n个元素），因此时间复杂度为 O(n)。

java

ArrayList<Integer> list = new ArrayList<>();
list.add(0, 1); // 插入到头部

尾部插入

当在ArrayList的尾部插入元素时，如果当前数组的容量还未达到最大值，只需要将新元素添加到数组的末尾即可，时间复杂度为 O(1)。

java

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // 插入到尾部

但是，当数组容量已满时，需要进行扩容操作。扩容操作通常会将数组的容量增加到当前容量的1.5倍或2倍，并将原数组中的所有元素复制到新的更大的数组中。这一过程的时间复杂度为 O(n)。因此，在最坏的情况下，尾部插入的时间复杂度也是 O(n)。

java

ArrayList<Integer> list = new ArrayList<>(2);
list.add(1);
list.add(2);
list.add(3); // 触发扩容

指定位置插入

在ArrayList的指定位置插入元素时，需要将目标位置之后的所有元素向后移动一个位置，然后将新元素插入到指定位置。平均情况下，需要移动n/2个元素，因此时间复杂度为 O(n)。

java

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(1, 4); // 在索引1位置插入元素4

删除操作的时间复杂度

头部删除

在ArrayList的头部删除元素时，需要将所有剩余元素依次向前移动一个位置，以填补被删除元素的位置。因此时间复杂度为 O(n)。

java

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.remove(0); // 删除头部元素

尾部删除

当删除的元素位于列表末尾时，只需要将末尾元素移除即可，时间复杂度为 O(1)。

java

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.remove(list.size() - 1); // 删除尾部元素

指定位置删除

在ArrayList的指定位置删除元素时，需要将目标位置之后的所有元素依次向前移动一个位置，以填补被删除元素的位置。平均情况下，需要移动n/2个元素，因此时间复杂度为 O(n)。

java

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.remove(1); // 删除索引1位置的元素

源码解析

插入操作源码分析

以下是ArrayList中add(int index, E element)方法的源码：

java

public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

• rangeCheckForAdd(index)：检查索引是否在合法范围内。
• ensureCapacityInternal(size + 1)：确保数组有足够的容量来容纳新元素，如果不够则进行扩容。
• System.arraycopy(elementData, index, elementData, index + 1, size - index)：将索引index之后的所有元素向后移动一个位置。
• elementData[index] = element：将新元素插入到指定位置。
• size++：更新数组大小。

删除操作源码分析

以下是ArrayList中remove(int index)方法的源码：

java

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    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
    return oldValue;
}

• rangeCheck(index)：检查索引是否在合法范围内。
• modCount++：修改计数，用于快速失败机制。
• E oldValue = elementData(index)：保存被删除的元素。
• int numMoved = size - index - 1：计算需要移动的元素数量。
• System.arraycopy(elementData, index+1, elementData, index, numMoved)：将索引index之后的所有元素向前移动一个位置。
• elementData[--size] = null：将最后一个元素置为null，以便垃圾回收。
• return oldValue：返回被删除的元素。

实际案例及应用场景

在实际开发中，了解ArrayList的插入和删除操作的时间复杂度可以帮助我们选择合适的数据结构。例如：

• 如果需要频繁在头部插入或删除元素，LinkedList比ArrayList更合适，因为LinkedList的头部操作时间复杂度为O(1)。
• 如果需要频繁在尾部插入元素且不考虑扩容，ArrayList是一个不错的选择，因为其尾部插入操作的时间复杂度为O(1)。

通过对比不同数据结构的性能，可以在实际项目中做出更明智的选择，从而提升代码的运行效率。

?