【47期】ArrayList中的remove是如何操作的？

架构狂人

发布于 2023-10-04 21:21:45

1480

发布于 2023-10-04 21:21:45

面试题：ArrayList中的remove是如何操作的？我接到面试电话的一刻，以为是骚扰电话打来的，一看显示四川乐山，哦，原来是我投的成都蚂蚁的面试，说简单聊聊吧，上来问了个ArraList热了下身。

ArrayList是个变长的数组集合类，实现是通过Object[]，当向ArrayList添加元素数量大于内部的数组容量时，会进行自动扩容1.5倍，新增和删除我们可以通过下标，指定位置新增和删除，如果是在有值的位置插入和删除数据，则需要移动数据保证数组连续。面试官:嗯，那你谈谈ArrayListdd的扩容机制吧。谈扩容机制前，我们需要对ArrayList的数据结构有个大致了解，下面会结合图片讲述。 构造方法 包含空参构造和带容量构造；

重要属性：初始容量10，当前数组长度

//初始容量：10
private static final int DEFAULT_CAPACITY = 10; 

// 空对象，如果使用默认构造函数创建，则默认对象内容默认是该值
private static final Object[] EMPTY_ELEMENTDATA = {}; 

//无参初始化并不是在无参构造方法的位置执行的，而是在第一次执行add方法的时候执行了容器大小的设置
//简单说，new ArrayList();容器初始化大小为0.
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//当前数据对象存放地方，当前对象不参与序列化
transient Object[] elementData; 

//当前数组长度
private int size;

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

add方法 ①不带下标插入，插入队尾 ②带下标插入，指定位置插入 1. 队尾插入

两个步骤： (1)判断是否需要扩容 (2)插入新元素到队尾

public boolean add(E e) {
        // 1. 判断是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 2. 将新元素插入数组尾部
        elementData[size++] = e;
        return true;
 }

2. 指定位置插入

三个步骤： (1)判断是否需要扩容 (2)数组拷贝，移位 (3)插入指定位置，index

public void add(int index, E element) {
    if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    // 1. 判断是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 2. 将 index及其之后的所有元素都向后移一位
    // arraycopy(被复制的数组, 从第几个元素开始, 复制到哪里, 从第几个元素开始粘贴, 复制的元素个数)
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    // 3. 将新元素插入至 index 处
    elementData[index] = element;
    size++;
}

扩容机制

当空间用完，会调用grow方法将，原数组空间扩容为原来的1.5倍

// 判断是否需要扩容
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

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

//最终执行扩容方法
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // newCapacity = oldCapacity + oldCapacity / 2 = oldCapacity * 1.5
    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);/此处拷进行数组拷贝
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 如果最小容量超过 MAX_ARRAY_SIZE，则扩容至 Integer.MAX_VALUE
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

remove方法 1. 获取指定位置 index 处的元素值 2. 将 index + 1 及之后的元素向前移动一位 3. 将最后一个元素置空，并将 size 值减 1 4. 返回被删除值，完成删除操作

 public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    modCount++;
    // 返回被删除的元素值
    E oldValue = (E) elementData[index];

    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 将 index + 1 并将之后的元素向前移动一位，覆盖被删除值
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 将最后一个元素置空，并将size值减 1     
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
} 
E elementData(int index) {
    return (E) elementData[index];
}

//删除指定元素，若元素重复，则只删除下标最小的元素
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++;
    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
}

本文参与?腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2023-10-02 23:56，如有侵权请联系?cloudcommunity@tencent.com 删除

arraylist