Java——ArrayList的add()原理解析和remove()遇到的坑

淩亂°似流年 2022-02-20 07:16 305阅读 0赞

### **       虽然ArrayList是可变数组，但是为了提高性能我们在使用中应尽量提前估算容量，add()的时间复杂度为O(1),但是扩容会拉低性能，所以定义时应估算容量，减少扩容次数；remove()方法,每次删除要移动后边数组，所以时间复杂度为O(n)，为提高性能，尽可能删除最后的数据。** ###

### 一.Add()源码解析 ###

数组扩容这是对ArrayList效率影响比较大的一个因素，虽然ArrayList可以自己扩容，但是扩容过程的空间复杂度应该是O(2n)，因为需要拷贝一个次旧的数组。

现在看一下源码：

**构造函数**

new ArrayList()返回的是一个空的Object,所以新建的ArrayList初始容量为零。

new ArrayList(K)当K>0时，开辟K个空间；K=0，返回空的Object。

private static final int DEFAULT_CAPACITY = 10;
        private static final Object[] EMPTY_ELEMENTDATA = {};
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
        transient Object[] elementData; 
        private int size;
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
        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);
            }
        }

接下来看一下add()函数。**ArrayList首次扩容，容量为10，以后每次扩容将新开辟空间，容量将会增加为原来的1.5倍，再将原来的数组复制到新的空间。**

public boolean add(E e) {
            ensureCapacityInternal(size + 1);//add，长度+1，增量后调用下边函数
            elementData[size++] = e;
            return true;
        }
    
     private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                //如果数组为空的话，min=Math.max(10,1)=10;
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
             //调用下方函数
            ensureExplicitCapacity(minCapacity);
        }
    
     private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
            //数组长度<10,add后的长度大于现有的数组长度,说明数组应该扩容了，调用下方函数
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    //扩容函数
     private void grow(int minCapacity) {
            // overflow-conscious code
            //获取旧数组长度
            int oldCapacity = elementData.length;
            //新数组长度=原来的1.5倍；通过右移1位，即oldCapacity/2
            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:
            //拷贝，new 新的长度的数组，赋值 
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

### 二.remove()的注意问题 ###

**每次删除一个数，后边的元素会往前移动**，所以remove()方法有一些坑大家会忽略掉。

比如下面的代码，想要将偶数删除，输出结果是？

@Test
    public void testRemove2(){
        List<Integer> integers = new ArrayList<>(5);
        integers.add(1);
        integers.add(2);
        integers.add(2);
        integers.add(4);
        integers.add(5);
    
        for (int i = 0; i < integers.size(); i++) {
            if (integers.get(i)%2==0){
                integers.remove(i);
            }
        }
    
        System.out.println(integers);
    }

结果是：

[1,2,5]

显然，结果和需求是不相符的。因为在删除第一个 2 的时候，后边的数字统一往前移动，但是下标 i 会继续+1，所以下一次循环 i 指向的是 4 ，所以第二个2根本没有执行 if 代码块，自然没有删除。

下面的代码也是很常见的错误写法：

@Test
    public void testRemove5(){
        List<String> strings = new ArrayList<>();
        strings.add("a");
        strings.add("b");
        strings.add("c");
        strings.add("d");
    
        int size = strings.size();
        for (int i = 0; i < size; i++) {
            strings.remove(i);
        }
    
    }

数组size是变化的，用遍历size长度肯定是不对的，所以运行结果会报错。

正确写法如下：使用Iterator遍历删除是最安全的。

@Test
    public void testRemove7(){
        List<String> strings = new ArrayList<>();
        strings.add("a");
        strings.add("b");
        strings.add("c");
        strings.add("d");
    
        Iterator<String> iterator = strings.iterator();
        while (iterator.hasNext()){
            String next = iterator.next();
            iterator.remove();
        }
    
        System.out.println(strings);
    }