ArrayList源码解析(基于JDK1.7)

以你之姓@ 2022-06-09 00:14 173阅读 0赞

## 一、ArrayList简介 ##

ArrayList是可以动态增长和缩减的索引序列，它是基于数组实现的List类。ArrayList的用法和Vector向类似，但是Vector是一个较老的集合，具有很多缺点，不建议使用。另外，ArrayList和Vector的区别是：ArrayList是线程不安全的，当多条线程访问同一个ArrayList集合时，程序需要手动保证该集合的同步性，而Vector则是线程安全的。  
ArrayList的声明如下：

public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable

与Collection关系如下图：  
![这里写图片描述][20170822194019784]

ArrayList的常用操作有：

*  ArrayList的创建：即构造器方法
 *  往ArrayList中添加对象：即add(E)方法
 *  获取ArrayList中的单个对象：即get(int index)方法
 *  删除ArrayList中的对象：即remove(E)方法
 *  遍历ArrayList中的对象：即iterator，在实际中更常用的是增强型的for循环去做遍历
 *  判断对象是否存在于ArrayList中：即contain(E)方法  
    ArrayList中对象的排序：主要取决于所采取的排序算法

## 二、ArrayList的动态扩容 ##

### 1、ArrayList的创建（指定大小和默认大小） ###

List<String> strList = new ArrayList<String>();
    List<String> strList2 = new ArrayList<String>(2);

下面来看一下ArrayList源代码：

*  基本属性：

//序列化和反序列化时比较的标号
    private static final long serialVersionUID = 8683452581122892189L;
    
    //对象数组：ArrayList的底层数据结构，注意是Object类型
    private transient Object[] elementData;
    
    //elementData中已存放的元素的个数，注意：size不是elementData的容量，其容量是ArrayList初始化时指定的。
    private int size;

注意到elementData被transient关键字修饰，那么该关键字有什么作用呢？  
在采用Java默认的序列化机制的时候，被transient关键字修饰的属性不会被序列化。上面的elementData属性采用了transient来修饰，表明其不使用Java默认的序列化机制来实例化，但是该属性是ArrayList的底层数据结构，在网络传输中一定需要将其序列化，之后使用的时候还需要反序列化，那不采用Java默认的序列化机制，那采用什么呢？直接翻到源码的最下边有两个方法，发现ArrayList自己实现了序列化和反序列化的方法，如下：

/**
         * Save the state of the <tt>ArrayList</tt> instance to a stream (that is,
         * serialize it).
         * 
         * @serialData The length of the array backing the <tt>ArrayList</tt>
         *             instance is emitted (int), followed by all of its elements
         *             (each an <tt>Object</tt>) in the proper order.
         */
        private void writeObject(java.io.ObjectOutputStream s)
                throws java.io.IOException {
            // Write out element count, and any hidden stuff
            int expectedModCount = modCount;
            s.defaultWriteObject();
    
            // Write out array length
            s.writeInt(elementData.length);
    
            // Write out all elements in the proper order.
            for (int i = 0; i < size; i++)
                s.writeObject(elementData[i]);
    
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
    
        }
    
        /**
         * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
         * deserialize it).
         */
        private void readObject(java.io.ObjectInputStream s)
                throws java.io.IOException, ClassNotFoundException {
            // Read in size, and any hidden stuff
            s.defaultReadObject();
    
            // Read in array length and allocate array
            int arrayLength = s.readInt();
            Object[] a = elementData = new Object[arrayLength];
    
            // Read in all elements in the proper order.
            for (int i = 0; i < size; i++)
                a[i] = s.readObject();
        }

*  构造方法

搞清楚了ArrayList的属性后，我们来看一下它的构造方法：

// ArrayList带容量大小的构造函数。
     public ArrayList(int initialCapacity) {
            super();
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            this.elementData = new Object[initialCapacity];
        }
    
        //ArrayList无参数构造参数，默认容量10
        public ArrayList() {
            super();
            this.elementData = EMPTY_ELEMENTDATA;
        }
    
         // 创建一个包含collection的ArrayList   
        public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray(); //调用toArray()方法把collection转换成数组 
            size = elementData.length; //把数组的长度赋值给ArrayList的size属性
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        }

*  注意：

上边参构造器的super()方法是ArrayList父类AbstractList的构造方法，这个构造方法如下，是一个空构造方法：

protected AbstractList() {
        }

在实际使用中，我们尽量一次性初始化ArrayList的合适大小来满足要求。如果初始过大会浪费空间，初始过小又会导致中途扩容，从而性能下降。  
EMPTY\_ELEMENTDATA的定义如下：

private static final Object[] EMPTY_ELEMENTDATA = {};

在JDK1.6中无参数的构造方法是：

// ArrayList无参构造函数。默认容量是10。    
        public ArrayList() {    
            this(10);    
        }

在1.7前，会默认在内存中直接分配10个空间，但是在1.7有了改变，会先在内存中分配一个对象的内存空间，但是这个对象是没有长度的（空的）。但是在你进行添加的时候，默认的会去拿对象的默认大小来作比较。

### 2、ArrayList的add（E e）方法 ###

add（E e）的方法简单来讲就是：  
1、确保数组容量，其中就包括是否扩容然后将数组整个复制。同时modCount(用来记录集合被修改的次数)值加一  
2、将元素添加到数组中  
其源码如下：

public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

ensureCapacityInternal从字面上理解就是确保内部容量，其源码如下：

private void ensureCapacityInternal(int minCapacity) {
            if (elementData == EMPTY_ELEMENTDATA) {
       //未指定初始容量
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY为10
            }
    
            ensureExplicitCapacity(minCapacity);
        }

这里的DEFAULT\_CAPACITY等于10。AarryList在用无参的构造方法创建时，是没有为里面的数组成员分配空间的，只有在进行add操作后才会分配空间，并会和10比较。再调用ensureExplicitCapacity来分配具体的空间。这样在第一次add时会直接分配10个空间。  
ensureExplicitCapacity的源码如下：

private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // 容量不够，需要扩容
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

对于未指定初始容量的ArrayList，在第一次add操作时，`elementData.length`的值是0。grow方法的源码如下：

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private void grow(int minCapacity) {
           // overflow-conscious code
            int oldCapacity = elementData.length;
            //首先得到数组的旧容量，然后进行oldCapacity + (oldCapacity >> 1)，将oldCapacity 右移一位，其效果相当于oldCapacity /2，整句的结果就是设置新数组的容量扩展为原来数组的1.5倍
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)//这个if只在初次分配10个空间时执行。
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)//判断有没超过最大限制，如果超出限制则调用hugeCapacity
                newCapacity = hugeCapacity(minCapacity);
             //将原来数组的值copy新数组中去， ArrayList的引用指向新数组
            //这里会新创建数组，如果数据量很大，重复的创建的数组，那么还是会影响效率，
            //因此鼓励在合适的时候通过构造方法指定默认的capaticy大小
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

newCapacity代表具体扩容成多大。第4行就相当于 `int newCapacity=oldCapacity+ordCapacity/2`（大约1.5倍）。用移位操作可以在数组容量大时节省点时间。  
hugeCapacity的源码如下：

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

关于Arrays.copyOf方法其实就是调用的System.arraycopy，而后者又是加了native关键字，底层应该是c++之类的语言去实现整个数组的复制。设计上面，Arrays.copyOf分了一个泛型方法和一个专门处理基本类型如int、float的方法。  
在明确数组大小时可以调用ensureCapacity手动为其扩容，来减少扩容的次数。

public void ensureCapacity(int minCapacity) {
            int minExpand = (elementData != EMPTY_ELEMENTDATA)? 0: DEFAULT_CAPACITY;
    
            if (minCapacity > minExpand) {
                ensureExplicitCapacity(minCapacity);
            }
        }

看一下JDK1.6的动态扩容的实现原理：

public void ensureCapacity(int minCapacity) {
          modCount++;
         int oldCapacity = elementData.length;
         if (minCapacity > oldCapacity) {
             Object oldData[] = elementData;
             int newCapacity = (oldCapacity * 3)/2 + 1;
                 if (newCapacity < minCapacity)
             newCapacity = minCapacity;
                 // minCapacity is usually close to size, so this is a win:
                 elementData = Arrays.copyOf(elementData, newCapacity);
         }
    }

从代码上，我们可以看出区别：  
第一：在容量进行扩展的时候，其实例如整除运算将容量扩展为原来的1.5倍加1，而jdk1.7是利用位运算，从效率上，jdk1.7就要快于jdk1.6。  
第二：在算出newCapacity时，其没有和ArrayList所定义的`MAX_ARRAY_SIZE`作比较，为什么没有进行比较呢，原因是jdk1.6没有定义这个`MAX_ARRAY_SIZE`最大容量，也就是说，其没有最大容量限制的，但是jdk1.7做了一个改进，进行了容量限制。

### 3、ArrayList的add(int index, E element)方法 ###

add(int index, E element)的主要操作如下：  
1、判断插入位置是否合法  
2、确保数组容量，其中就包括是否扩容然后将数组整个复制。同时modCount(用来记录集合被修改的次数)值加一。  
3、插入位置后的元素整体向后移一个单位。  
4、将元素放到指定位置。

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++;
        }

## 三、ArrayList的源码解析 ##

//继承AbstractList，支持泛型
        public class ArrayList<E> extends AbstractList<E>  
                    implements List<E>, RandomAccess, Cloneable, java.io.Serializable  
        {
          
            private static final long serialVersionUID = 8683452581122892189L;  
    
            //默认初始化大小  
            private static final int DEFAULT_CAPACITY = 10;  
    
            //空表
            private static final Object[] EMPTY_ELEMENTDATA = {};  
    
            //内部实现为数组  
            private transient Object[] elementData;  
    
            //元素数目  
            private int size;  
    
            //初始化一个initialCapacity大小的ArrayList  
            public ArrayList(int initialCapacity) {  
                super();//父类的构造函数本身没做什么事情  
                if (initialCapacity < 0)//检查是否合法  
                    throw new IllegalArgumentException("Illegal Capacity: "+  
                                                       initialCapacity);  
                this.elementData = new Object[initialCapacity];
            }  
    
            //初始化一个空的ArrayList  
            public ArrayList() {  
                super();  
                this.elementData = EMPTY_ELEMENTDATA;//数组为空  
            }  
    
            //按c里面的元素来初始化一个ArrayList  
            public ArrayList(Collection<? extends E> c) {
            //c中的元素转换为数组,elementData的类型为Object[],此处不需要类型转换    
                elementData = c.toArray();
                size = elementData.length;  
                if (elementData.getClass() != Object[].class)//确保elementData数组是object类型
                    elementData = Arrays.copyOf(elementData, size, Object[].class);  
            }  
    
        　　//相当于压缩ArrayList，比如ArrayList有10个空间，现在只存储了5个元素，
        　　//通过该方法将ArrayList的空间变为5个  
            public void trimToSize() {  
                modCount++;//修改次数+1  
                if (size < elementData.length) {  
                    elementData = Arrays.copyOf(elementData, size);  
                }  
            }  
    
            //申请minCapacity个空间  
            public void ensureCapacity(int minCapacity) {  
                //获取表默认的初始容量,空表为0，其他的默认为DEFAULT_CAPACITY 
                int minExpand = (elementData != EMPTY_ELEMENTDATA)? 0: DEFAULT_CAPACITY; 
                //只有minCapacity大于默认初始容量，才申请新的大小的空间  
                if (minCapacity > minExpand) {
                    ensureExplicitCapacity(minCapacity);//执行扩容  
                }  
            }  
            //申请minCapacity个空间  
            private void ensureCapacityInternal(int minCapacity) {  
                if (elementData == EMPTY_ELEMENTDATA) { 
                    //minCapacity取DEFAULT_CAPACITY和minCapacity的最大值  
                    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
                }  
    
                ensureExplicitCapacity(minCapacity);//执行扩容  
            }  
            //执行扩容，容量为minCapacity  
            private void ensureExplicitCapacity(int minCapacity) {  
                modCount++;//修改次数+1  
    
                //只有minCapacity大于默认初始容量，才执行扩容  
                if (minCapacity - elementData.length > 0)  
                    grow(minCapacity);//执行扩容,容量为minCapacity  
            }  
    
            //JVM支持大小为MAX_ARRAY_SIZE容量的数组  
            private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;  
    
            //执行扩容  
            private void grow(int minCapacity) {  
                //记录老的容量值  
                int oldCapacity = elementData.length;  
                //新的容量按老容量的1.5倍来扩容  
                int newCapacity = oldCapacity + (oldCapacity >> 1);
                if (newCapacity - minCapacity < 0)  
                    //如果申请的容量比目前容量的1.5倍还要大  
                    newCapacity = minCapacity;
                if (newCapacity - MAX_ARRAY_SIZE > 0)
                    newCapacity = hugeCapacity(minCapacity);  
                //增加新的空间，新增加空间的长度为newCapacity,原有的元素放到新空间的前面  
                elementData = Arrays.copyOf(elementData, newCapacity);
            }  
    
            private static int hugeCapacity(int minCapacity) {  
                if (minCapacity < 0) //溢出了  
                    throw new OutOfMemoryError();  
                return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE :MAX_ARRAY_SIZE;  
            }  
    
            //返回元素数目  
            public int size() {  
                return size;  
            }  
    
            //判断ArrayList是否为空
            public boolean isEmpty() {  
                return size == 0;  
            }  
    
            //判断是否包含值为o的元数  
            public boolean contains(Object o) {  
                return indexOf(o) >= 0;
            }  
    
            //定位第一个值为o的元素  
            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;  
            }  
    
            //定位最后一个值为o的元素  
            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;  
            }  
    
            //执行浅拷贝  
            public Object clone() {  
                try {  
                    @SuppressWarnings("unchecked")  
                        ArrayList<E> v = (ArrayList<E>) super.clone();  
                    //只执行数组中的引用拷贝，引用指向的内存一致
                    v.elementData = Arrays.copyOf(elementData, size);
                    v.modCount = 0;  
                    return v;  
                } catch (CloneNotSupportedException e) {  
                    throw new InternalError();  
                }  
            }  
    
            //转换为数组  
            public Object[] toArray() {  
                return Arrays.copyOf(elementData, size);  
            }  
    
            //转换为a类型的数组  
            @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个元素  
            @SuppressWarnings("unchecked")  
            E elementData(int index) {  
                return (E) elementData[index];//O(1)操作  
            }  
    
            //获取第index个元素  
            public E get(int index) {  
                rangeCheck(index);  
    
                return elementData(index);  
            }  
    
            //设置第index个元素的值为element  
            public E set(int index, E element) {  
                rangeCheck(index);  
    
                E oldValue = elementData(index);  
                elementData[index] = element;  
                return oldValue;  
            }  
    
            //尾部添加元素e  
            public boolean add(E e) {  
                ensureCapacityInternal(size + 1);  // Increments modCount!!  
                elementData[size++] = e;  
                return true;  
            }  
    
            //第index个位置添加元素element  
            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++;  
            }  
    
            //删除第index个元素  
            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;  
            }  
    
            //删除值为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个元素，即不返回删除的元素值  
            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  
            }  
    
            //将ArrayList置空  
            public void clear() {  
                modCount++;  
    
                //保证GC可以工作
                for (int i = 0; i < size; i++)  
                    elementData[i] = null;  
    
                size = 0;  
            }  
    
            //将c里面的所有元素都添加到当前表的尾部  
            public boolean addAll(Collection<? extends E> c) {  
                Object[] a = c.toArray();  
                int numNew = a.length;  
                ensureCapacityInternal(size + numNew);  // Increments modCount  
                System.arraycopy(a, 0, elementData, size, numNew);  
                size += numNew;  
                return numNew != 0;  
            }  
    
            //将c里面的所有元素都添加到第index个位置之后  
            public boolean addAll(int index, Collection<? extends E> c) {  
                rangeCheckForAdd(index);  
    
                Object[] a = c.toArray();  
                int numNew = a.length;  
                ensureCapacityInternal(size + numNew);  // Increments modCount  
    
                int numMoved = size - index;  
                if (numMoved > 0)  
                    System.arraycopy(elementData, index, elementData, index + numNew,  
                                     numMoved);//执行拷贝  
    
                System.arraycopy(a, 0, elementData, index, numNew);  
                size += numNew;  
                return numNew != 0;  
            }  
    
            //删除formIndex和toIndex之间的元素  
            protected void removeRange(int fromIndex, int toIndex) {  
                modCount++;  
                int numMoved = size - toIndex;  
                System.arraycopy(elementData, toIndex, elementData, fromIndex,  
                                 numMoved);  
    
                // clear to let GC do its work  
                int newSize = size - (toIndex-fromIndex);  
                for (int i = newSize; i < size; i++) {  
                    elementData[i] = null;  
                }  
                size = newSize;  
            }  
    
            //index范围检查  
            private void rangeCheck(int index) {  
                if (index >= size)  
                    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
            }  
    
            //index范围检查  
            private void rangeCheckForAdd(int index) {  
                if (index > size || index < 0)  
                    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
            }  
    
            private String outOfBoundsMsg(int index) {  
                return "Index: "+index+", Size: "+size;  
            }  
    
            //删除所有c里面不包含的元素  
            public boolean removeAll(Collection<?> c) {  
                return batchRemove(c, false);  
            }  
    
            //删除所有c里面包含的元素  
            public boolean retainAll(Collection<?> c) {  
                return batchRemove(c, true);  
            }  
            //执行批量删除  
            private boolean batchRemove(Collection<?> c, boolean complement) {  
                final Object[] elementData = this.elementData;  
                int r = 0, w = 0;  
                boolean modified = false;  
                try {  
                    for (; r < size; r++)  
                        if (c.contains(elementData[r]) == complement)  
                            elementData[w++] = elementData[r];  
                } finally {  
                    // Preserve behavioral compatibility with AbstractCollection,  
                    // even if c.contains() throws.  
                    if (r != size) {  
                        System.arraycopy(elementData, r,  
                                         elementData, w,  
                                         size - r);  
                        w += size - r;  
                    }  
                    if (w != size) {  
                        // clear to let GC do its work  
                        for (int i = w; i < size; i++)  
                            elementData[i] = null;  
                        modCount += size - w;  
                        size = w;  
                        modified = true;  
                    }  
                }  
                return modified;  
            }  
    
            //序列化  
            private void writeObject(java.io.ObjectOutputStream s)  
                throws java.io.IOException{  
                // Write out element count, and any hidden stuff  
                int expectedModCount = modCount;  
                s.defaultWriteObject();  
    
                // Write out size as capacity for behavioural compatibility with clone()  
                s.writeInt(size);  
    
                // Write out all elements in the proper order.  
                for (int i=0; i<size; i++) {  
                    s.writeObject(elementData[i]);  
                }  
    
                if (modCount != expectedModCount) {  
                    throw new ConcurrentModificationException();  
                }  
            }  
    
            //反序列化  
            private void readObject(java.io.ObjectInputStream s)  
                throws java.io.IOException, ClassNotFoundException {  
                elementData = EMPTY_ELEMENTDATA;  
    
                // Read in size, and any hidden stuff  
                s.defaultReadObject();  
    
                // Read in capacity  
                s.readInt(); // ignored  
    
                if (size > 0) {  
                    // be like clone(), allocate array based upon size not capacity  
                    ensureCapacityInternal(size);  
    
                    Object[] a = elementData;  
                    // Read in all elements in the proper order.  
                    for (int i=0; i<size; i++) {  
                        a[i] = s.readObject();  
                    }  
                }  
            }  
    
            //返回一个从index开始的双向迭代器  
            public ListIterator<E> listIterator(int index) {  
                if (index < 0 || index > size)  
                    throw new IndexOutOfBoundsException("Index: "+index);  
                return new ListItr(index);  
            }  
    
            //返回一个双向迭代器  
            public ListIterator<E> listIterator() {  
                return new ListItr(0);  
            }  
    
            //返回迭代器  
            public Iterator<E> iterator() {  
                return new Itr();  
            }  
    
            //私有内部类，从第0个元素开始的单向迭代器  
            private class Itr implements Iterator<E> {
          
                int cursor;       // index of next element to return  
                int lastRet = -1; // index of last element returned; -1 if no such  
                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 = i + 1;  
                    return (E) elementData[lastRet = i];  
                }  
    
                public void remove() {  
                    if (lastRet < 0)  
                        throw new IllegalStateException();  
                    checkForComodification();  
    
                    try {  
                        ArrayList.this.remove(lastRet);  
                        cursor = lastRet;  
                        lastRet = -1;  
                        expectedModCount = modCount;  
                    } catch (IndexOutOfBoundsException ex) {  
                        throw new ConcurrentModificationException();  
                    }  
                }  
    
                final void checkForComodification() {  
                    if (modCount != expectedModCount)  
                        throw new ConcurrentModificationException();  
                }  
            }  
    
            //私有内部类，从第index元素开始的双向迭代器  
            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;  
                }  
    
                @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;  
                        lastRet = -1;  
                        expectedModCount = modCount;  
                    } catch (IndexOutOfBoundsException ex) {  
                        throw new ConcurrentModificationException();  
                    }  
                }  
            }  
    
        }

## 四、LinkedList和ArrayList的对比 ##

1、顺序插入速度ArrayList会比较快，因为ArrayList是基于数组实现的，数组是事先new好的，只要往指定位置塞一个数据就好了；LinkedList则不同，每次顺序插入的时候LinkedList将new一个对象出来，如果对象比较大，那么new的时间势必会长一点，再加上一些引用赋值的操作，所以顺序插入LinkedList必然慢于ArrayList  
2、基于上一点，因为LinkedList里面不仅维护了待插入的元素，还维护了Entry的前置Entry和后继Entry，如果一个LinkedList中的Entry非常多，那么LinkedList将比ArrayList更耗费一些内存  
3、ArrayList使用for循环遍历快，因为是通过数组索引直接遍历，每次get的时间复杂度为O(1)。LinkedList使用foreach循环遍历快，因为使用普通for循环会每次从前一个节点拿后一个节点地址，相当于从头遍历一遍，每次get的时间复杂度为O(N)。

[20170822194019784]: /images/20220609/99101e04f77d48cd9cc62ed4eaed362c.png