【源码面经】Java源码系列-ArrayList与LinkedList

  1. ArrayList的大小是如何自动增加的
  2. 什么情况下你会使用ArrayList?什么时候你会选择LinkedList
  3. 如何复制某个ArrayList到另一个ArrayList中去
  4. 索引中ArrayList的增加或者删除某个对象的运行过程?效率很低吗?解释一下为什么?
  5. ArrayList插入删除一定慢么?
  6. ArrayList的遍历和LinkedList遍历性能比较如何?
  7. ArrayList是线程安全的么?
  8. ArrayList如何remove

不想看源码解析的同学,可以直接去最下方查看答案

源码解析

List是最简单的线性数据结构,Java在最上层提供了List接口,然后通过AbstractList实现了List接口。

ArrayList和LinkedList是Java中最常用的List实现类。

ArrayList底层是由数组实现的,相当于动态数组。LinkedList底层相当于链表的实现方式。

下面我们开始分析源码

ArrayList

底层数据结构

/**
     * 默认初始化的数组大小
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 所有ArrayList实例共享的空list实例
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA与EMPTY_ELEMENTDATA区分,标识
     * elementData数组是通过默认构造方法创建的空数组,并且还没有向其中添加
     * 元素
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 底层用来真实存储数据的数组,在调用ArrayList默认构造方法时,该数组会被
     * 赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA。直到第一次向数组中添加元素时,
     * 会被扩容为DEFAULT_CAPACITY
     */
    transient Object[] elementData;

    /**
     * 数组中元素的数量
     */
    private int size;
    
    /**
     * 可以分配的最大数组大小。某些VM在数组中保留一些header words。
     * 尝试分配更大的数组可能会导致OutOfMemoryError
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

复制代码

构造方法

/**
     * 通过给定的初始容量创建一个空list
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            // 如果指定的容量大于0,就新建一个数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            // 如果指定的容量等于0,那么就是一个空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: " +
                    initialCapacity);
        }
    }

    /**
     * 不指定初始容量,创建一个容量为10的空数组
     */
    public ArrayList() {
        // 使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA标识elementData数组
        // 是通过默认构造方法创建的,在第一向ArrayList添加元素时,会进行
        // 扩容,而扩充的容量为DEFAULT_CAPACITY(10)
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 创建一个ArrayList,包含给定集合c中的所有元素,顺序即为c迭代器遍历的顺序。
     *
     * @throws NullPointerException 如果c为null,抛出NPE
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // 如果给定集合c的size不为0
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                // c.toArray()并不一定返回Object[]类型,如果返回的不是
                // Object[]类型,就调用Arrays的复制方法变为Object类型
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 如果给定集合c的size为0,那么就构造一个空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
复制代码

动态扩容

/**
     * 修剪elementData多余的槽,使ArrayList的capacity修剪为当前的size
     */
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
                    ? EMPTY_ELEMENTDATA
                    : Arrays.copyOf(elementData, size);
        }
    }

    /**
     * 增加ArrayList的capacity,确保elementData的容量最少能支持
     * minCapacity
     *
     * @param minCapacity 需要的最小容量
     */
    public void ensureCapacity(int minCapacity) {
        // 1. 如果ArrayList不是通过默认构造方式构造的,或者
        //    ArrayList中已经添加过元素了,则minExpand为0,
        // 2. 如果ArrayList是通过默认构造方式构造的,且从未
        //    添加过任何元素,那么minExpand就为默认的初始化
        //    容量DEFAULT_CAPACITY(10)
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                ? 0 : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            // 如果需要扩容
            ensureExplicitCapacity(minCapacity);
        }
    }

    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);
    }
    
    /**
     * @param minCapacity 需要的最小容量
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // newCapacity = 1.5 * oldCapacity
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 对elementData进行扩容,然后将elementData原有的内容,
        // 复制到扩容后的数组中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }
复制代码

插入/替换

/**
     * 添加元素e到list尾部
     */
    public boolean add(E e) {
        // 检查是否需要扩容,并将modCount + 1
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }

    /**
     * 在指定index插入元素element,并将原先在index位置及右方元素向右移动一位
     */
    public void add(int index, E element) {
        // 检查index是否有效
        rangeCheckForAdd(index);

        // 检查是否需要扩容,并将modCount + 1
        ensureCapacityInternal(size + 1);
        // 把index及index右面的元素全部向右移动一位
        System.arraycopy(elementData, index, elementData, index + 1,
                size - index);
        elementData[index] = element;
        size++;
    }
    
    /**
     * 将给定的集合c中的所有元素按照c迭代器的顺序添加到list的末尾。
     * <p>
     * 在遍历集合c的过程中,如果对c进行了修改,那么会产生未定义的现象。
     */
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        // 扩容,并修改modCount
        ensureCapacityInternal(size + numNew);
        // 将数组a复制到数组elementData尾部
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

    /**
     * 将给定的集合c中的所有元素按照c迭代器的顺序添加到list的index位置。
     * 并把index及index之后的元素的位置向后移动n个位置,n为集合c的大小。
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        // 扩容并修改modCount
        ensureCapacityInternal(size + numNew);

        int numMoved = size - index;
        if (numMoved > 0)
            // 如果index小于size,即为在之前的元素中间插入,所以要把index及之后的
            // 元素向右移动numNew位
            System.arraycopy(elementData, index, elementData, index + numNew,
                    numMoved);

        // 将数组a的元素,复制到elementData数组中
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }
    
    /**
     * 用element替换下标为index的元素,并返回之前的元素
     */
    public E set(int index, E element) {
        // 检查index是否超过限制
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
复制代码

删除

/**
     * 删除指定下标的元素,并将该下标右边的元素全部向左移动一位
     */
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 将index+1及之后的元素全部向左移动一位
            System.arraycopy(elementData, index + 1, elementData, index,
                    numMoved);
        elementData[--size] = null;
        return oldValue;
    }

    /**
     * 如果list中包含一个或多个元素o,那么删除第一个o(下标最小的),并将第一个o对应
     * 下标右边的元素全部向左移动一位。
     * <p>
     * 如果list中不包含元素o,那么不做任何改变
     */
    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;
    }

    /**
     * 快速删除index对应的元素,不需要进行范围检查,因为调用该方法时
     * 已经可以保证index绝对有效
     */
    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
    }

    /**
     * 清空elementData中的所有元素的引用
     */
    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            // 帮助GC
            elementData[i] = null;

        size = 0;
    }

    

    /**
     * 移除下标在 [fromIndex, toIndex) 之间的元素,并将toIndex和之后
     * 的元素全部向左移动至fromIndex的位置
     */
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        // 将toIndex和之后的元素向左移动至fromIndex的位置
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                numMoved);

        // 计算新的数组的大小
        int newSize = size - (toIndex - fromIndex);
        // 将多余的元素引用置为null,帮助GC
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }
    
    /**
     * 从list中删除指定集合c中包含的所有元素。
     */
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

    /**
     * 保留在list中且在指定集合c中包含的所有元素
     */
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }

    /**
     * @param complement false-remove,true-retain
     */
    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            // 双指针遍历list
            for (; r < size; r++)
                // c.contains(elementData[r])判断给定集合c中是否存
                // 在r指针对应的元素。
                // 如果complement为false,代表remove集合c中的元素。
                // 如果complement为true,代表retain集合c中的元素。
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // 如果c.contains抛出异常,仍能保证与AbstractCollection相同的兼容性
            if (r != size) {
                // 如果r指针没有遍历完数组,就把r指针未遍历的元素,复制到r指针
                // 之后,因为r指针-w指针之间的元素应该被移除
                System.arraycopy(elementData, r, elementData, w, size - r);
                w += size - r;
            }
            if (w != size) {
                // 清空不用的元素引用,帮助GC
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }
复制代码

遍历

/**
     * 返回list中第一次出现给定元素o的下标,如果不存在元素o
     * 则返回-1
     */
    public int indexOf(Object o) {
        // 将o为null和非null的情况分开做处理
        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;
    }

    /**
     * 返回list中最后一次出现给定元素o的下标,如果不存在元素o
     * 则返回-1
     */
    public int lastIndexOf(Object o) {
        // 与indexOf实现方式相同,只是把遍历的方向
        // 改为从后向前遍历
        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;
    }
    
    /**
     * 返回下标为index的元素
     */
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

    /**
     * 返回下标为index的元素
     */
    public E get(int index) {
        // 检查index是否超过限制
        rangeCheck(index);

        return elementData(index);
    }
    
    @Override
    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked") final E[] elementData = (E[]) this.elementData;
        final int size = this.size;
        // forEach的内部实现其实就是遍历内部elementData数组,
        // 然后对每个元素进行action.accept操作。
        // 遍历过程中要比较modCount是否发生变化,如果发生了变化,
        // 会抛出ConcurrentModificationException,快速失败
        for (int i = 0; modCount == expectedModCount && i < size; i++) {
            action.accept(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
复制代码

迭代器

private class Itr implements Iterator<E> {
        int cursor;       // 下一个要访问的元素的下标
        int lastRet = -1; // 上一次访问的元素的下标,如果没有则为-1
        int expectedModCount = modCount;

        // 是否包含下一个元素
        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            // 如果要访问的下标大于最大长度,则抛出异常
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            // cursor后移
            cursor = i + 1;
            // 返回下标为i的元素,并将lastRet置为i
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            // 如果上一个访问的元素不存在,则抛出异常
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                // 删除上一个访问的元素
                ArrayList.this.remove(lastRet);
                // 重置下标
                cursor = lastRet;
                // 因为上一个访问的元素已经删除了,所以不存在了
                // 要把lastRet置为-1
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        // 防止并发冲突
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
    
    /**
     * 在Iterator的基础上,支持了双向遍历
     */
    private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        /**
         * 与Iterator的next方法一样,只不过改成了向前遍历
         */
        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                // 向list添加元素后,上一次访问的元素就发生了变化,
                // 所以要将lastRet置为-1
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }
复制代码

其他

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 返回ArrayList的浅拷贝
     */
    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

    /**
     * 以数组的形式返回list中的所有元素
     */
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    /**
     * 以数组的形式返回list中的所有元素, 数组的类型为T
     */
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

    /**
     * 检查index是否超出限制,需要检查index的原因是当list动态扩容时,会分配出
     * 未使用的空间,访问时并不会报错。而size记录了当前真实使用的空间,所以
     * 需要将index与size比较。
     * <p>
     * 不检查index为负的情况,因为当index为负时,访问数组会抛出ArrayIndexOutOfBoundsException
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * add and addAll 时检查是否index是否有效
     */
    private void rangeCheckForAdd(int index) {
        // 与rangeCheck版本不同,这里index是可以等于size的,因为size的值
        // 就是下一个要插入的下标值,所以index==size就相当于在list尾插入
        //
        // 不知道为什么这里还判断了index < 0 的情况
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }
}
复制代码

LinkedList

// 待定
复制代码

面试题解答

  1. ArrayList的大小是如何自动增加的

    当调用ArrayList的add, addAll等方法时,会调用ensureCapacityInternal方法检查底层数组容量是否满足所需容量,如果容量不够大,就调用grow方法将容量扩展至原来的1.5倍(一般情况下)

  2. 什么情况下你会使用ArrayList?什么时候你会选择LinkedList?

    待定

  3. 如何复制某个ArrayList到另一个ArrayList中去

    public class Node implements Cloneable {
        public Node() {}
    
        public Object clone() {
            Node node = null;
            try {
                node = (Node) super.clone();
            } catch (CloneNotSupportedException e) {
                e.printStackTrace();
            }
            return node;
        }
    }
    public static void main(String[] args) {
        ArrayList<Node> srcList = new ArrayList<>();
        srcList.add(new Node());
        srcList.add(new Node());
    
        for (Node node : srcList) {
            System.out.println("srcList: " + node);
        }
    
        /* --------------------- 浅复制 --------------------- */
        
        System.out.println("浅复制");
        
        // 循环遍历
        List<Node> destList1 = new ArrayList<>();
        srcList.forEach(src -> destList1.add(src));
        System.out.println("循环遍历");
        for (Node node : destList1) {
            System.out.println("descList: " + node);
        }
    
        // 构造方法
        List<Node> destList2 = new ArrayList<>(srcList);
        System.out.println("构造方法");
        for (Node node : destList2) {
            System.out.println("descList: " + node);
        }
    
        // addAll方法
        List<Node> destList3 = new ArrayList<>();
        destList3.addAll(srcList);
        System.out.println("addAll方法");
        for (Node node : destList3) {
            System.out.println("descList: " + node);
        }
    
        // clone方法
        List<Node> destList4 = (List<Node>) srcList.clone();
        System.out.println("clone方法");
        for (Node node : destList4) {
            System.out.println("descList: " + node);
        }
    
        // System.arraycopy
        Node[] destArray = new Node[srcList.size()];
        System.arraycopy(srcList.toArray(), 0, destArray, 0, srcList.size());
        System.out.println("System.arraycopy方法");
        for (Node node : destArray) {
            System.out.println("descList: " + node);
        }
        
        /* --------------------- 深复制 --------------------- */
        
        System.out.println("深复制");
        
        // 改造后的clone方法
        List<Node> destList5 = (List<Node>) srcList.clone();
        System.out.println("改造后的clone方法");
        for (Node node : destList5) {
            System.out.println("descList: " + node.clone());
        }
    }
    复制代码

    返回结果

    srcList: Node@71bc1ae4
    srcList: Node@6ed3ef1
    ---------- 浅复制 ---------- 
    循环遍历
    descList: Node@71bc1ae4
    descList: Node@6ed3ef1
    构造方法
    descList: Node@71bc1ae4
    descList: Node@6ed3ef1
    addAll方法
    descList: Node@71bc1ae4
    descList: Node@6ed3ef1
    clone方法
    descList: Node@71bc1ae4
    descList: Node@6ed3ef1
    System.arraycopy方法
    descList: Node@71bc1ae4
    descList: Node@6ed3ef1
    ---------- 深复制 ---------- 
    改造后的clone方法
    descList: Node@17d99928
    descList: Node@3834d63f
    复制代码
  4. ArrayList插入/删除一定慢吗

    取决于插入与删除的位置

    插入:在插入过程中会将index及之后的元素向后移动,如果插入的位置是数组靠后的位置。那么要移动的元素并不多,通过index直接访问的,操作并不会很慢。

    删除:与插入相同,插入过程中会将index及之后的元素向前移动,如果位置靠后,移动的元素也不多。

  5. ArrayList的遍历和LinkedList遍历性能比较如何?

    待定

  6. ArrayList是线程安全的么?

    不是。对ArrayList的操作并没有做任何同步或者加的行为。可以看到对ArrayList的结构性操作中,都会对modCount值进行修改。这样在操作时,通过比较modCount可以实现fail-fast机制,在并发冲突时,抛出ConcurrentModificationException

  7. ArrayList如何remove

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(1);
        list.add(2);
        list.add(2);
        list.add(3);
        list.add(3);
    
    
        List<Integer> list2 = new ArrayList<>(list);
        for (int i = 0; i < list2.size(); i++) {
            if ((list2.get(i) % 2) == 0) {
                list2.remove(i);
            }
        }
        System.out.println(list2); // [1, 1, 2, 3, 3]
        
        list2 = new ArrayList<>(list);
        Iterator<Integer> iterator = list2.iterator();
        while (iterator.hasNext()) {
            if ((iterator.next() % 2) == 0) {
                iterator.remove();
            }
        }
        System.out.println(list2); // [1, 1, 3, 3]
    
        list2 = new ArrayList<>(list);
        for (Integer data : list2) { // ConcurrentModificationException
            if ((data % 2) == 0) {
                list2.remove(data);
            }
        }
        System.out.println(list2); 
    }
    复制代码
    1. 通过遍历下标的方式删除(×):

      这种方式是错误的,有可能会遗漏元素。比如数组中的元素为[1, 1, 2, 2, 3, 3],当下标index为2时,对应的元素为第一个[2],满足条件删除后,数组中的元素变为[1, 1, 2, 3, 3],因为[2]被删除后,之后的[2, 3, 3]向左移动。在遍历中,index++ 变为3,对应的元素为[3],所以数组中第二个[2]被遗漏了,没有遍历到。

    2. 通过迭代器进行迭代(√):

      这种方式是删除的正确方式

    3. 在forEach中进行删除(×):

      这种方式是错误的,会抛出ConcurrentModificationException。原因在于ArrayList中的forEach方法:

      1. final int expectedModCount = modCount; 
           在整个遍历之前会先记录modCount。
        复制代码
      2. 在调用ArrayList的remove方法时,会通过modCount++对modCount值进行修改,
           这时modCount与遍历前记录的modCount已经不一致了。
        复制代码
      3. for (int i = 0; modCount == expectedModCount && i < size; i++) {
               action.accept(elementData[i]);
           }
           遍历每个元素时,会检查modCount是否与之前一致。而在remove方法中,
           已经进行了修改,所以在删除元素后的下次遍历时会退出循环。
        复制代码
      4. if (modCount != expectedModCount) { 
            throw new ConcurrentModificationException(); 
        }
        如果modCount与之前不一致了,就抛出ConcurrentModificationException
        复制代码

原文 

https://juejin.im/post/5ea545cf6fb9a03c832b27dd

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 【源码面经】Java源码系列-ArrayList与LinkedList

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址