ArrayList LinkedList CopyOnWrite

1. ArrayList是最常用的集合之一，大小不固定，但是可以随着元素的增多可以自动扩容。底层实现是基于数组。 默认容量是10. 每次扩容都是增加0.5倍，即在为原大小的1.5倍，每次扩容都学要移动素组的元素，到新的素组，所以扩容的开销还是比较大的。
   同理，向某一个位置插入一个元素，也需要从该位置开始后移所有的元素，删除同样如此。
   所以ArrayList可以看到随机的插入和删除开销比较大。
   删除的话，如果在一个for循环的里面的话，如果删除了之后还i++的话，那指定宝座

ArrayList不支持并发操作，如果想要使其并发操作可以使用：

List list1 = Collections.synchronizedList(list);

转为Synchronized的，这样就支持并发操作了，因为synchronizedList对list进行了二次封装，每一个方法都加了synchronize的所以支持并发了。例如add 方法：

   public void add(int index, E element) {
            synchronized (mutex) {list.add(index, element);}
        }

当然Java并发包里面还提供了另外一个类 CopyOnWriteArrayList。
同样适用于并发操作，因为里面加了锁：

    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

但他的扩容和ArrayList很蛋疼，他虽然也是数组，但是并没有指定大小，而是每加一个元素 利用Arrays.copyOf一次，可想他的效率有多低了，所以不涉及并发尽量不要用CopyOnWriteArrayList。
再阅读list的源码的时候，需要注意：

 transient Object[] elementData; // non-private to simplify nested class access

元素数组前面加了transient，这个表示的是不需要序列化，因为它对这个素组单独实现了序列化writeObject和readObject.

2. LinkedList的实现是基于链表，而不是素组，所以linkedList的特点是可以很快的随机删除和插入，根据位置读取的话就没有arryList那么快了。既然是链表那就不存在扩容的问题了。
   虽然查找慢，但是也稍微进行了优化，如果查到的index在前半段则就从头结点开始遍历，如果是后半段则从尾节点开始向前查找。

 /**
     * Returns the (non-null) Node at the specified element 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;
        }
    }

欢迎关注我的公众号： manong_xiaodong或扫一扫下面的二维， 有大数据资料赠送哟，因为我最近也在学习大数据！欢迎一起学习！