image.png

1. 增

boolean add（E e）源码执行流程图

boolean add（E e）

boolean addAll(int index,Collection<? extends E> c )源码执行流程图

boolean addAll(int index,Collection<? extends E> c )

2. 删

boolean removeAll(Collection<? extends E> c)批量删除

public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
}

removeAll()方法实际上调用的是batchRemove()方法

/**
     * ArrayList中的元素实际上保存在一个Object[]中，
     * 从该数组中删除object[] 和Collection<?> C的公共元素
     * 
     * @param c
     * @param complement
     * @return
     */
    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int w = 0, r = 0;
        boolean modified = false;
        try {

            for (; r < size; r++) {
                // 遍历elementData中的元素
                if (c.contains(elementData[r]) == complement) {
                    // c中不包含当前元素，则该元素需要保留在elementData中
                    elementData[w++] = elementData[r];
                }
            }
        } finally {
            /*
             * 如果上述遍历过程发生异常的话(出现异常会导致r!=size)，
             * 则将异常处到size-1位置的元素全部保留在elementData中，不做删除
             */
            if (r != size) {
                System.arraycopy(elementData, r, elementData, w, size - r);
                w += size - r;// 修改 w数量
            }
            // 把[w,size-1]索引处的元素设置为null，防止内存泄漏
            if (w != size) {
                for (int i = w; i < size; i++) {
                    elementData[i] = null;
                    modCount += size - w;// 修改modCount
                    size = w;// 修改size
                    modified = true;
                }
            }

        }
        return complement;
    }

代码，高效寻找两个集合中公共元素

3. 改

4. 查

查实际上都是遍历Object[] 数组

public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

5. 排序

public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

相关知识点

1. Arrays.sort() // 对传入的数组进行排序
2. Arrays.copyOf()

// 创建一个长度为newLength的新数组，
//   若newLength>原数组长度：将多出来元素控件用false补齐
//   若newLength>原数组长度：将原数组多出来的元素截断
static boolean[] copyOf(boolean[] original, int newLength)

// 把原数组中[from,to]范围内的数拷贝到一个新数组中，返回新数组
static copyOfRange (boolean[] original, int from, int to)

参考文献

面试必备：ArrayList源码解析（JDK8）