【参考文档】
鲁班语雀ArrayList:[https://www.yuque.com/books/share/9f4576fb-9aa9-4965-abf3-b3a36433faa6/fua39n](https://www.yuque.com/books/share/9f4576fb-9aa9-4965-abf3-b3a36433faa6/fua39n)

java中的浅拷贝和深拷贝:[https://www.cnblogs.com/ysocean/p/8482979.html](https://www.cnblogs.com/ysocean/p/8482979.html)

Fail-Fast机制：[https://www.cnblogs.com/fanlinglong/p/6627393.html](https://www.cnblogs.com/fanlinglong/p/6627393.html)

一、通常ArrayList和LinkedList给人的感觉

ArrayList:读快，写慢
LinkedList:读慢，写快

二、而实际情况是什么呢？

1.先来看看ArrayList

【读分析】
ArrayList读之所以快，是因为ArrayList底层是维护的一个数组，数组在内存中是连续的，
并且每个数组元素分配的内存大小一致，所以程序在读取时只需知道数组下标，就可以
定位到数组元素的起始偏移量，读取效率相当快。
//elementData是arrylist中维护的数组 
public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
//根据下标获取数组的元素
E elementData(int index) {
        return (E) elementData[index];
}

【写分析】
创建ArrayList如果不指定长度，在add操作时，会通过Arrays.copyOf扩容到默认数组长度10，
如果写入的元素数远远大于数组长度10，那就会每隔一段时间进行一次数组扩容copy，每次扩容是原数组长度的1.5，
在扩容的时候，会进行数组copy，数组元素越多，copy所消耗的性能越大，这才是导致arraylist写操作慢的原因，如果在创建
arraylist时指定合适的数组长度，使其不进行数组扩容，就会解决写入慢的问题。
public boolean add(E e) {
        //判断数组是否已满，数组满的话进行数组扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //添加数组元素
        elementData[size++] = e;
        return true;
    }
   private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
  private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
          //数组扩容
            grow(minCapacity);
    }
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

2.LinkedList分析

【读分析】
LinkedList的get(i)方法需要通过循环遍历查找i所在的节点对象，一旦涉及到循环，效率就不会
高。
有一种高效率的读取方式就是通过iterate，遍历读取，这种读取方式，只会遍历一次查找到遍历的
起点节点，后续的遍历调用iter.next()方法是通过当前节点维护的next
节点或者pre节点的指针进行循环。

【get(i)方法】
public E get(int index) {
       //检查index是否合法
        checkElementIndex(index);
       //循环查找node返回node.item
      //其中item就是我们存入的元素 
       return node(index).item;
    }
//先判断index是跟起始节点近还是跟末尾节点近
//跟谁近就从哪头开始遍历
Node<E> node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

【迭代器的next()】
public ListIterator<E> listIterator(int index) {  // 继承回调该方法
    checkPositionIndex(index);
    return new ListItr(index);
}
 
private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;  // 使用node节点查找并缓存数据
    private Node<E> next;
    private int nextIndex;  // 是否遍历结束
    private int expectedModCount = modCount;
 
    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }
 
    public boolean hasNext() {
        return nextIndex < size;
    }
 
    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();
 
        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }
 
    public boolean hasPrevious() {
        return nextIndex > 0;
    }
 
    public E previous() {  // 支持前后两种遍历方法
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();
 
        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }
 
    public int nextIndex() {
        return nextIndex;
    }
 
    public int previousIndex() {
        return nextIndex - 1;
    }
 
    public void remove() {  // 不带索引值的移除
        checkForComodification();
        if (lastReturned == null)
            throw new IllegalStateException();
 
        Node<E> lastNext = lastReturned.next;
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        expectedModCount++;
    }
 
    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }
 
    public void add(E e) {  // 添加和重置元素值的功能
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }
 
    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (modCount == expectedModCount && nextIndex < size) {
            action.accept(next.item);
            lastReturned = next;
            next = next.next;
            nextIndex++;
        }
        checkForComodification();
    }
 
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

【写分析】
以add(str)为例，默认添加到队列末端，添加元素只是把新元素设置为
last，把新元素的prev元素设置成旧的末端元素，把旧的末端元素的
next元素设置成新元素；总之就是指针的一种切换，效率比较高。
 /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
     Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
    }