ArrayList、Vector、CopyOnWriteArrayList、LinkedList源码进阶解析

电玩女神 2023-06-14 14:58 18阅读 0赞

#### 前言： ####

1.  List集合下常用的集合有 ArrayList (JDK1.2)、Vector (JDK1.0)、CopyOnWriteArrayList (JDK1.5)、LinkedList (JDK1.2)，对应的加入JDK的版本也不同。
2.  其中 ArrayList、Vector、CopyOnWriteArrayList 底层均是由数组来实现的，其中Vector和CopyOnWriteArrayList 是线程安全的如果不考虑它们加入JDK的时间 Vector和CopyOnWriteArrayList更像是ArrayList为保证线程安全而进行的不用方向的进化。
3.  LinkedList 不同的是 它底层是由双向链表组成的，和ArrayList一样也是线程不安全的，它和ArrayList区别究根到底也就是链表和数组之间的差别

#### 总结： ####

1.  ArrayList:  
    a. 线程不安全，是基于数组来实现的。  
    b. 优势：相比于LinkedList 在遍历列表和查找时速度快。  
    c. 劣势：在删除中间数据时会导致后面数据的迁移，当新增数据时原数组Size不够，会导致数组的扩容，都会产生性能的消耗  
    d. 优化：如果数组有频繁的删除，新增且遍历较少时，可以考虑LinkedList；如果预先能知道集合大小在初始化时将参数传入
2.  Vector ：  
    a. 线程安全，基本实现和 ArrayList相同  
    b. Vector 在对数组进行操作的方法加入了synchronized 对象锁，保证了线程安全的同时但对高并发的场景并不是很友好。
3.  CopyOnWriteArrayList :  
    a. 线程安全,也是基于数组来实现的。  
    b. 它类似于提供了一个读写分离的方案，读取时，会直接读取数组中的值。当对数组进行新增、插入、删除时，利用ReentrantLock加锁，将原来的旧数组复制成一个新的数组后，再在新数组上进行操作，最后将CopyOnWriteArrayList 指向新的数组
4.  LinkedList：  
    a. 线程不安全，基于双向链表实现的，它和ArrayList是相互补充的作用。  
    b. 优势：即是链表的特性，新增、删除效率高，仅仅修改相邻两个链表之间的引用即可  
    c. 劣势：即是ArrayList的优势。

##### ArrayList 源码解析： #####

以下源码均是基于 JDK8 中源码讲解，

###### ArrayList 中常用定义的参数： ######

1.  Object\[\] **elementData** ： 是保存数据的数组【重点参数】。
2.  size： 当前ArrayList中元素的个数【重点参数】
3.  源码示意：

public class ArrayList<E> extends AbstractList<E>
            implements java.util.List<E>, RandomAccess, Cloneable, java.io.Serializable
    { 
    	// 初始化数组大小
        private static final int DEFAULT_CAPACITY = 10;
    
        // 用于空实例的共享空数组实例。
        private static final Object[] EMPTY_ELEMENTDATA = { };
    
        // 默认空数组
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    
        // 保存数据的 数组
        transient Object[] elementData; // non-private to simplify nested class access
    
        // ArrayList元素大小
        private int size;
    
    	// 最大容量
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

###### 初始化 ： ######

1.  ArrayList() ：默认创建一个空数组
2.  **ArrayList(int initialCapacity)**: 指定容量初始化ArrayList 【实际创建指定长度的数组 elementData】，推荐使用避免后面 elementData 扩容
3.  ArrayList(Collection<? extends E> c): 初始化并将集合C中元素放置到ArrayList
4.  源码分析：

// 无参初始化
        public ArrayList() { 
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
    	// 指定容量 初始化ArrayList 【实际创建指定长度的数组 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);
            }
        }
    	
    	// 初始化并将集合C中元素放置到ArrayList
        public ArrayList(Collection<? extends E> c) { 
            elementData = c.toArray();
            if ((size = elementData.length) != 0) { 
                // c.toArray might (incorrectly) not return Object[] (see 6260652)
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else { 
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

#### 新增方法： ####

1.  假设我们使用 ArrayList()初始化时。
2.  当我们 首次执行 add(E e) 时， ensureCapacityInternal(int minCapacity) 会帮我们创建一个length为10的空数组:  
    ![在这里插入图片描述][20191120111547472.png]
3.  如果我们 连续执行三次 add(E e)，参数分别为 a、b、c 时，ArrayList 中参数如下：  
    ![在这里插入图片描述][20191120111532646.png]
4.  第四次操作我们调用 add(1, “x”) 在 第二个位置插入"x",这时，b，c 需要向后移动一位，给x让出位置，如果后面数据量多大，这里就会有性能问题。在ArrayList中通过 System.arraycopy()来实现后续数据迁移的功能。  
    ![在这里插入图片描述][2019112011232210.png]
5.  当我们第11次调用 add 方添加 “j”时 ensureCapacityInternal 会判断我们当前的数组大小无法存储这么多数据，便对 elementData 大小进行扩容为原来的1.5倍数，再将add 的数据进行保存【这里会有较大的性能消耗】，结果如下：  
    ![!\[在这里插入图片描述\](https://img-blog.csdnimg.cn/20191120143523456.png][https_img-blog.csdnimg.cn_20191120143523456.png]
6.  根据上面图文解释看一下，在源码中新增方法具体是怎么实现的：

// ArrayList 新增一个元素【常用方法】
        public boolean add(E e) { 
            // 判断当前 elementData 大小是否可以存放新的元素
            // 是否对 数组进行扩容
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            // 将元素放置在 elementData 最后位置
            elementData[size++] = e;
            return true;
        }
    
    	// 在指定位置插入element
        public void add(int index, E element) { 
            rangeCheckForAdd(index);
    
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            /** * 数组复制 * * 1、第一个elementData: 原来的数组 * 2、index：复制开始的位置 * 3、第二个 elementData: 目标数组 * 4、index+ 1：粘贴的开始位置 * 5、size - index：需要复制的长度 */
            System.arraycopy(elementData, index, elementData, index + 1,
                    size - index);
            elementData[index] = element;
            size++;
        }
    	
    	/** * 1、判断当前 elementData 大小是否可以存放新的元素 * 2、是否对 数组进行扩容 * @param minCapacity 需要的最小容量 */
        private void ensureCapacityInternal(int minCapacity) { 
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            // 根据minCapacity 是否对 elementData 进行扩容处理
            ensureExplicitCapacity(minCapacity);
        }
    
        // 根据minCapacity 是否对 elementData 进行扩容处理
        private void ensureExplicitCapacity(int minCapacity) { 
            // AbstractList 中变量 统计ArrayList被操作的次数
            modCount++;
    
            // 所需的最小值minCapacity大于elementData，需要扩容
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    	
    	// 扩大elementData容量,并将数据迁移
        private void grow(int minCapacity) { 
            // 旧的容量
            int oldCapacity = elementData.length;
            // 默认扩展后的容量
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 取 newCapacity 和 minCapacity 的最大值
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            // capacity 过大的处理方式
            // 将 elementData 中数据复制到新的 newCapacity 中，并赋值给 elementData
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            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;
        }

#### remove方法： ####

1.  在了解了上面 add 方法之后，我们在第4步之后吧 ‘x’ 移除掉，调用 remove(1)结果如下：  
    ![在这里插入图片描述][2019112014484657.png]  
    索引位1之后的元素会向前移动一位，保证整个数组中间不会存在空位【当数量过多时，这里会有较大的性能消耗】
2.  源码示意:

// 移除指定索引位,并返回元素
        public E remove(int index) { 
            // 检测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;
    
            return oldValue;
        }
    
        // 移除第一次出现 Object 的索引位
        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 位置的元素移除,并将后面的元素在数组中向前移一位 * @param index */
        private void fastRemove(int index) { 
            modCount++;
            int numMoved = size - index - 1;
            if (numMoved > 0)
                /** * 数组复制 * * 1、第一个elementData: 原来的数组 * 2、index+1：复制开始的位置 * 3、第二个 elementData: 目标数组 * 4、index：粘贴的开始位置 * 5、numMoved：需要复制的长度 */
                System.arraycopy(elementData, index+1, elementData, index,
                        numMoved);
            elementData[--size] = null; // clear to let GC do its work
        }

##### Itr迭代器： #####

1.  我们先来看一下 ArrayList 的内部类 Itr 迭代器实现的源码：

/** * ArrayList 的迭代器 */
        private class Itr implements Iterator<E> { 
            // 指针
            int cursor;
    
            //返回的迭代器遍历的最后一个元素的索引
            int lastRet = -1;
    
            // ArrayList 被操作的次数
            int expectedModCount = modCount;
    
            // 是否有下一个
            public boolean hasNext() { 
                return cursor != size;
            }
    
            // 获取下一个元素
            public E next() { 
                // 校验 expectedModCount是否等于modCount, 保证迭代器的正常运行
                // 这里存在一个常见的面试题，为什么在foreach的时候，调用ArrayList的remove方法后，会抛出异常?
                // 简单来讲 foreach 其实是迭代器实现的，当调用ArrayList的remove是否会导致++modCount，而expectedModCount不变
                // 因此在调用next()时checkForComodification()会抛出异常，
                // 所以迭代器遍历删除元素时，需要调用 Itr.remove() 操作
                checkForComodification();
                int i = cursor;
                if (i >= size)
                    throw new NoSuchElementException();
                Object[] elementData = java.util.ArrayList.this.elementData;
                if (i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i + 1;
                return (E) elementData[lastRet = i];
            }
    
            // 移除迭代器遍历的最后一个元素，即上个 next() 获取到的元素
            public void remove() { 
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();
    
                try { 
                    java.util.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();
        }
      }

1.  这里有个非常经典的面试题，  
    问. 关于集合的遍历有 for、foreach、迭代器 三种方式，但是在在 foreach 遍历时为什么调用可不可以直接调用其remove方法？  
    答. 不可以，因为 foreach 其实是迭代器实现的，当调用ArrayList的remove是否会导致++modCount，而迭代器中 expectedModCount不变，因此在下一次调用 next() 时 checkForComodification()会抛出异常，所以当遍历ArrayList 需要删除元素时，建议使用迭代器遍历，并调用 Itr.remove() 操作。

#### ArrayList总结： ####

关于 Arraylist ，博主认为最关键的是理解 参数：elementData、size 和方法 System.arraycopy ，至于其他方法都是围绕着两个参数来实现功能的，也比较简单，不过多深入，有兴趣的小伙伴可以吧 ArrayList 的源码读一读，这样对于以后面试和工作中就不会存在任何问题。

#### Vector ####

上面我们已经学习了 ArrayList 源码的实现，ArrayList 是 Vector 升级版本，两者代码实现并无太大区别，唯一的一点是 Vector 在操作数组 elementData 的方法上加入了 synchronized 修饰来保证线程安全。  
例如:

// 新增一个元素
    public synchronized boolean add(E e) { ...}
    
    // 在指定的位置新增一个元素
    public synchronized void insertElementAt(E obj, int index){ .... }
    
    // 获取元素
    public synchronized E get(int index){ ....}
    
    // 将 index 位置的元素进行替换
    public synchronized E set(int index, E element){ ....}
    
    // remove index位置的元素
    public synchronized E remove(int index){ ...}
    
    .......

我需要记住的是Vector是 线程安全的，ArrayList 是线程不安全的，但是Vector基本上把所有操作获取方法都加了synchronized 来修饰，这对并发很不友好，因此在 JDK1.5 引入了 CopyOnWriteArrayList 读写List 来替代 Vector。

#### CopyOnWriteArrayList： ####

1.  CopyOnWriteArrayList 在JDK1.5 引入的，解决了 ArrayList 线程不安全 且 Vector 并发不友好，类似读写分离的一种操作。
2.  设计原理：  
    读： 直接从 array 【和ArrayList中 elementData 相同】，获取数据。  
    写： 先通过 ReentrantLock 加锁，根据 array 复制一份新的 Object 数组 newElements，添加元素到 newElements ，然后再把 CopyOnWriteArrayList 指向新的数组，完成新增操作。
3.  适用于读多写少的操作，例如黑白名单操作。
4.  先看看一下add方法示意图：  
    a. 假设我们调用 CopyOnWriteArrayList() 初始化. 参数:array = \{\}  
    b. 当我们执行新增方法 add(“a”) 时，先创建一个长度为 1 的数组 newElements，将"a"放入，最后将array指向新的数组 newElements  
    ![在这里插入图片描述][20191120163410469.png]  
    c. 当我们通过 add 加入了一些元素之后，调用 add(2,“x”)时, 先创建比原来数组长度大一的新数组 newElements，并将 index 位置留下，再讲“x” 放入其中，最后将array指向新的数组 newElements  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neW9uZzAxMjQ1_size_16_color_FFFFFF_t_70]
5.  移除 remove 方法和add方法正好相反，直接在生成新的数组时将元素移除
6.  不多废话，下面是一些关键方法的源码：

public class CopyOnWriteArrayList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable { 
    
    	// 当对数组 进行增、删时会进行加锁操作
        final transient ReentrantLock lock = new ReentrantLock();
    
        // 保存数据的数组 和 ArrayList中elementData 功能相同
        private transient volatile Object[] array;
    
        // 获得保存数据的数组
        final Object[] getArray() { 
            return array;
        }
    
        // 设置保存数据的数组
        final void setArray(Object[] a) { 
            array = a;
        }
    
    	// 直接获取指定位置元素
        public E get(int index) { 
            return get(getArray(), index);
        }
        @SuppressWarnings("unchecked")
        private E get(Object[] a, int index) { 
            return (E) a[index];
        }
    	
    	// 新增一个元素
        public boolean add(E e) { 
            // 获得 ReentrantLock 并加锁
            final ReentrantLock lock = this.lock;
            lock.lock();
            try { 
                // 得到存储数据的数组
                Object[] elements = getArray();
                int len = elements.length;
                // 根据 array 复制一个新的数组 newElements
                Object[] newElements = Arrays.copyOf(elements, len + 1);
                // 将元素放置到新的数组上
                newElements[len] = e;
                // 将原来数组的指向为新的数组
                setArray(newElements);
                return true;
            } finally { 
                lock.unlock();
            }
        }
    
    
        // 在指定索引位 添加元素
        public void add(int index, E element) { 
            // 获得 ReentrantLock 并加锁
            final ReentrantLock lock = this.lock;
            lock.lock();
            try { 
                // 得到存储数据的数组
                Object[] elements = getArray();
                int len = elements.length;
                if (index > len || index < 0)
                    throw new IndexOutOfBoundsException("Index: "+index+
                            ", Size: "+len);
                // 定义一个新的数组
                Object[] newElements;
                // 新元素插入后，数组后面的元素需要移动的位数
                int numMoved = len - index;
                // index 位置刚好是放在原数组最后一位的后面
                if (numMoved == 0)
                    // 复制新的数组，数组中元素相同，比原数组 length 大1
                    newElements = Arrays.copyOf(elements, len + 1);
                // index < array.length
                else { 
                    // 创建新的空数组，比原数组 length 大1
                    newElements = new Object[len + 1];
                    // 将原数组从0到index 复制到 新数组从0到index
                    System.arraycopy(elements, 0, newElements, 0, index);
                    // 将原数组从index到最后 复制到 新数组从index+1到最后
                    System.arraycopy(elements, index, newElements, index + 1,
                            numMoved);
                }
                // 将元素放置到新的数组上
                newElements[index] = element;
                // 将原来数组的指向为新的数组
                setArray(newElements);
            } finally { 
                lock.unlock();
            }
        }
    
    	// 删除指定位置的元素
        public E remove(int index) { 
            // 获取锁 并加锁
            final ReentrantLock lock = this.lock;
            lock.lock();
            try { 
                // 获得原数组
                Object[] elements = getArray();
                int len = elements.length;
                // 得到原来index位置的元素
                E oldValue = get(elements, index);
                int numMoved = len - index - 1;
                // index 刚好是原数组最后一位
                if (numMoved == 0)
                    // 直接创建一个新的数组 元素相同，比原数组小1，舍弃最后一个元素
                    setArray(Arrays.copyOf(elements, len - 1));
                else { 
                    // 创建一个新的数组 比原数组小1
                    Object[] newElements = new Object[len - 1];
                    // 将原数组 0~index 拷贝到 新数组 0~index
                    System.arraycopy(elements, 0, newElements, 0, index);
                    // 将原数组 index+1~最后 拷贝到 新数组 index~最后
                    System.arraycopy(elements, index + 1, newElements, index,
                            numMoved);
                    // 指向新的数组
                    setArray(newElements);
                }
                return oldValue;
            } finally { 
                lock.unlock();
            }
        }
    
    
    	........................
    }

#### LinkedList 讲解： ####

1.  LinkedList 底层是基于双向链表设计的，对象中保存 head、last节点。
2.  链表的优势在于，新增和移除功能相比ArrayList快的多，但是遍历速度远不及 ArrayList，上个节点一般保存下个节点的引用，查询时需要根据内存地址去查找。
3.  LinkedList 存储数据示意图：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neW9uZzAxMjQ1_size_16_color_FFFFFF_t_70 1]
4.  对应的 add、remove、get 源码如下：

public class LinkedList<E>
            extends AbstractSequentialList<E>
            implements java.util.List<E>, Deque<E>, Cloneable, java.io.Serializable
    { 
    	 transient int size = 0;
    
        // LinkedList 第一个节点
        transient java.util.LinkedList.Node<E> first;
    
        // LinkedList 最后一个节点
        transient java.util.LinkedList.Node<E> last;
    
        public LinkedList() { 
        }
    
        public LinkedList(Collection<? extends E> c) { 
            this();
            addAll(c);
        }
    	
    	// 新增一个元素 直接在最后添加一个元素
        public boolean add(E e) { 
            linkLast(e);
            return true;
        }
    
        // 在最后添加一个元素
        void linkLast(E e) { 
            // 获取最后的节点 last
            final java.util.LinkedList.Node<E> l = last;
            // 根据 e 设置新的Node, 其中 prev指向last， next指向空
            final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(l, e, null);
            // 将新建的节点 newNode 最为最后一个节点
            last = newNode;
            // 当前集合为null，设置头尾节点相同
            if (l == null)
                first = newNode;
            else
                // 将原来的尾节点的next 指向新的节点
                l.next = newNode;
            size++;
            modCount++;
        }
    
    	// 在链表的指定位置插入元素
        public void add(int index, E element) { 
            // 校验 index
            checkPositionIndex(index);
    
            // 直接将 element 插入到最后位置
            if (index == size)
                linkLast(element);
            else
                // 将 element 放置到index位置
                linkBefore(element, node(index));
        }
    
        // 校验 index 时候在范围内
        private void checkPositionIndex(int index) { 
            if (!isPositionIndex(index))
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    
        private boolean isPositionIndex(int index) { 
            return index >= 0 && index <= size;
        }
    
        // 返回当前索引位置 的节点
        java.util.LinkedList.Node<E> node(int index) { 
            // 因为LinkedList是双向链表 这里才用了折中查找法
            // 如果 index 在前半截 就从first查找
            // 如果 index 在后半截 就从last查找
            if (index < (size >> 1)) { 
                java.util.LinkedList.Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else { 
                java.util.LinkedList.Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }
    
    
        // 在 succ 前面加入新的节点
        void linkBefore(E e, java.util.LinkedList.Node<E> succ) { 
            // succ 的上一个节点
            final java.util.LinkedList.Node<E> pred = succ.prev;
            // 创建新的节点，元素是E，它的上一个节点是succ.prev,它的下一个节点是succ
            final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(pred, e, succ);
            // 设置 newNode为 succ的上一个节点
            succ.prev = newNode;
            // 集合初始化
            if (pred == null)
                first = newNode;
            else
                // succ 上一个节点的 next 设置为新的节点
                pred.next = newNode;
            size++;
            modCount++;
        }
    
    	// 移除指定位置的元素
        public E remove(int index) { 
            // 校验index
            checkElementIndex(index);
            // node(index) 获取到元素
            // unlink(node) 使当前的节点脱离链表
            return unlink(node(index));
        }
    	
    	// 使当前的节点脱离链表
        E unlink(java.util.LinkedList.Node<E> x) { 
            // 元素
            final E element = x.item;
            // 下一个节点
            final java.util.LinkedList.Node<E> next = x.next;
            // 上一个节点
            final java.util.LinkedList.Node<E> prev = x.prev;
    
            // 处理上一个节点
            // 上一个节点为null, 表示当前节点为 头结点，把下一个节点设置为头结点
            if (prev == null) { 
                first = next;
            }
            else { 
                // 将当前节点的下一个节点设置为上一个节点的next
                prev.next = next;
                // 将当前节点的prev 设置为null, 等待GC
                x.prev = null;
            }
    
            // 处理下一个节点
            // 上一个节点为null, 表示当前节点为尾结点，把上一个节点设置为尾结点
            if (next == null) { 
                last = prev;
            }
            else { 
                // 把下一个节点的prev指向当前节点的上一个节点
                next.prev = prev;
                // 将当前节点的 next 设置为null, 等待GC
                x.next = null;
            }
    
            x.item = null;
            size--;
            modCount++;
            return element;
        }
    
    	// 获取
        public E get(int index) { 
            // 校验 index
            checkElementIndex(index);
            // 获取节点
            return node(index).item;
        }
        
    	.....
    	
    }

关于方法的设计逻辑在上述代码中，已经描述的很详细了，这里就不过多的阐述了。

#### 关于List下的常用集合，其实看源码并不复杂，多看多做多研究，更上一层楼！！ ####

[20191120111547472.png]: https://img-blog.csdnimg.cn/20191120111547472.png
[20191120111532646.png]: https://img-blog.csdnimg.cn/20191120111532646.png
[2019112011232210.png]: https://img-blog.csdnimg.cn/2019112011232210.png
[https_img-blog.csdnimg.cn_20191120143523456.png]: https://img-blog.csdnimg.cn/20191120143646968.png
[2019112014484657.png]: https://img-blog.csdnimg.cn/2019112014484657.png
[20191120163410469.png]: https://img-blog.csdnimg.cn/20191120163410469.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neW9uZzAxMjQ1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/201911201636024.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neW9uZzAxMjQ1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neW9uZzAxMjQ1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191120183651249.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neW9uZzAxMjQ1,size_16,color_FFFFFF,t_70