【Java8-集合源码学习3-CopyOnWriteArrayList、LinkedList源码学习】

CopyOnWriteArrayList 1、概括

CopyOnWriteArrayList（顾名思义，写时复制）实现与ArrayList实现类似，底层都是对象数组，只不过对象数组由volatile修饰，并且维护了一个可重入锁对象 final transient ReentrantLock lock = new ReentrantLock()，用来保证线程安全性（下面会详细介绍）

public class CopyOnWriteArrayList
    implements List, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;

    final transient ReentrantLock lock = new ReentrantLock();

    // volatile保证一旦数组被修改，其它线程立马能够感知到
    private transient volatile Object[] array;
}

2、读写分离

写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。

读操作：

    public E get(int index) {
        return get(getArray(), index);
    }

    private E get(Object[] a, int index) {
        return (E) a[index];
    }

3、新增（写操作）

CopyOnWriteArrayList新增操作有如下四个步骤：

加锁；
从原数组拷贝出新数组；
将新数组引用赋值给原数组；
解锁。

   // 添加元素到数组尾部 
   public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        // 1、加锁 
        lock.lock();
        try {
            // 获取原数组
            Object[] elements = getArray();
            int len = elements.length;
            // 2、在原数组的基础上拷贝出一个新数组，新数组的长度在原数组长度上+1
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            // 设置新增元素在新数组尾部
            newElements[len] = e;
            // 3、将新数组引用赋值给原数组
            setArray(newElements);
            return true;
        } finally {
            // 4、解锁写在finally代码块里，保证即使 try 发生了异常，仍然能够释放锁 
            lock.unlock();
        }
    }

   final void setArray(Object[] a) {
        array = a;
    }

由于CopyOnWriteArrayList 的底层数组被volatile关键字修饰，意思是一旦数组被修改，其它线程立马能够感知到。

整体上来说，CopyOnWriteArrayList 就是利用锁 + 数组拷贝 + volatile 关键字保证了 List 的线程安全。

每一个要素都有着其独特的含义：

加锁：保证同一时刻只能有一个线程进行操作；
数组拷贝：保证数组的内存地址被修改，修改后触发 volatile 的可见性，其它线程可以立马知道数组已经被修改；
volatile：值被修改后，其它线程能够立马感知最新值。

4、删除

移除指定下标的元素源码：

    public E remove(int index) {
        final ReentrantLock lock = this.lock;
        // 加锁
        lock.lock();
        try {
            // 获取原数组老值
            Object[] elements = getArray();
            int len = elements.length;
            E oldValue = get(elements, index);
            int numMoved = len - index - 1;
             // 如果要删除的数据正好是数组的尾部，直接删除
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));
            else {
                //如果删除的数据在数组的中间，分三步走
                // 1、创建一个长度-1的新数组，因为要移除一个元素
                // 2、将原数组0-index的元素拷贝到新数组里
                // 3、将原数组index+1到末尾的元素拷贝到新数组
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

删除元素步骤分为三步：

加锁；
判断删除索引的位置，从而进行不同策略的拷贝；
解锁。

System.arraycopy()是个native方法，是做数组拷贝使用的

   

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

实践示例代码：

 int[] src = {1, 2, 4, 2, 7, 6, 10, 22};

        int[] dest = new int[5];
        System.arraycopy(src, 2, dest, 0, 5);
        System.out.println(Arrays.toString(dest));

结果如下：

5、迭代

在 CopyOnWriteArrayList 类注释中，明确说明了，在其迭代过程中，即使数组的原值被改变，也不会抛出 ConcurrentModificationException 异常，其根源在于数组的每次变动，都会生成新的数组，不会影响老数组，这样的话，迭代过程中，根本就不会发生迭代数组的变动（迭代的就是老数组）

    public Iterator iterator() {
        return new COWIterator(getArray(), 0);
    }

CopyOnWriteArrayList 迭代，迭代的是老数组，迭代过程中就算有添加操作也不会影响迭代结果，添加操作会新建数组不会影响老数组，即使 CopyOnWriteArrayList 的结构发生变动了，也不会抛出 ConcurrentModificationException 异常的原因：CopyOnWriteArrayList 迭代持有的是老数组的引用，而 CopyOnWriteArrayList 每次的数据变动，都会产生新的数组，对老数组的值不会产生影响，所以迭代也可以正常进行。

6、适用场景

CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。

但是 CopyOnWriteArrayList 有其缺陷：

内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；
数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中。

所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。

参考资料：

老猿说说-CopyOnWriteArrayLis

LinkedList 1、概述

LinkedList也是非线程安全的，如果要在多线程环境下使用他，需要做一些额外的努力。LinkedList分别实现了List接口和Deque接口，通过这种杂交方式，使他具有了独特的有别于ArrayList的特异功能。

public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable
{
    transient int size = 0;

    transient Node first;

    transient Node last;
}

基于双向链表实现，使用 Node 存储链表节点信息，prev指向上一个节点，next指向下一个节点，因此它可以进行双向遍历。同时，LinkedList中维护了两个指针，一个指向头部，一个指向尾部。维护这两个指针后，可以使得元素从头部插入，也可以使元素从尾部插入。基于方式，用户很容易就能实现FIFO(队列)，LIFO(栈)等效果。

    private static class Node {
        // 节点元素
        E item;
        // 指向下一个节点
        Node next;
        // 指向上一个节点
        Node prev;
        
        Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
        }
    }

LinkedList图示：

2、队列实现原理

队列的原理就是每次都从链表尾部添加元素，从链表头部获取元素，就像是生活中排队，先来后到。

    // 添加指定元素作为此列表的尾部（最后一个元素）
	public boolean offer(E e) {
        return add(e);
    }

    // 在此列表的末尾插入指定的元素
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

   // offer和offerLast底层调用的都是linkLast这个方法，顾名思义就是将元素添加到链表尾部。
    void linkLast(E e) {
        final Node l = last;
        // 新创建一个节点，头指针指向原末尾节点，尾指针为null
        final Node newNode = new Node<>(l, e, null);
        // 将last指针指向新创建的这个节点
        last = newNode;
        // 如果当前链表为空，那么将头指针也指向这个节点。
        if (l == null)
            first = newNode;
        else
             // 将链表的尾节点的next指针指向新建的节点，这样就完整的实现了在链表尾部添加一个元素的功能
            l.next = newNode;
        size++;
        modCount++;
    }

---
    
    // 检索并删除此列表的头部（第一个元素）
    public E poll() {
        final Node f = first;
        return (f == null) ? null : unlinkFirst(f);
    } 

    // 检索并删除此列表的第一个元素
    public E pollFirst() {
        final Node f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

   // 上面两个方法都调用了unlinkFirst(),将链表的头元素删除
    private E unlinkFirst(Node f) {
        // assert f == first && f != null; f头节点
        // 需要返回的头元素
        final E element = f.item; 
        // 第二个节点
        final Node next = f.next;
        f.item = null;
        f.next = null; // help GC 将原先头节点，数据域、尾指针域都至空，让Java垃圾回收器回收
        // 头节点指向第二个节点
        first = next;
        if (next == null)
            // 说明只有头节点一个节点，删除之后，尾指针也指向null
            last = null;
        else
            // 此时第二个节点是头节点，头节点头指针为null
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

	// 获取头元素，但是不会删除他。
    public E peek() {
        final Node f = first;
        return (f == null) ? null : f.item;
    }

3、栈实现原理

栈是一端封闭的容器，先进去的后出来，保证先进后出原则

    // 压栈，在链表的头部添加一个元素
    public void push(E e) {
        addFirst(e);
    }

  // push()最后调用的就是linkFirst(),从头部插入元素
    private void linkFirst(E e) {
        final Node f = first;
        // 新创建一个节点，节点头指针为null
        final Node newNode = new Node<>(null, e, f);
        // 头指针指向该节点
        first = newNode;
        if (f == null)
            // 列表为空，尾指针也指向该节点
            last = newNode;
        else
            // 原头节点的头指针指向该节点，实现头节点插入操作
            f.prev = newNode;
        size++;
        modCount++;
    }

---
    //出栈，弹出顶部结点。
   public E pop() {
        return removeFirst();
    }

   // pop()最后调用方法，unlinkFirst实现将链表顶部元素删除
    private E unlinkFirst(Node f) {
        // assert f == first && f != null;
        // 需要弹出元素
        final E element = f.item;
        // 第二个节点，将要变成头节点
        final Node next = f.next;
        f.item = null;
        f.next = null; // help GC  将原先头节点，数据域、尾指针域都至空，让Java垃圾回收器回收
        first = next;
        if (next == null)
            // 此时列表为空，尾指针为null
            last = null;
        else
            // 头节点头指针为null
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

	// 获取顶部结点，但是不删除
    public E peek() {
        final Node f = first;
        return (f == null) ? null : f.item;
    }

以上就是LinkedList实现的两种功能，这里包含了大部分关于链表操作的方法，但不仅限于这几种。不管是栈也好，队列也好，元素都是从头部删除的unlinkFirst方法。但是用户在使用的过程中并不只用到上面两种方式，我们也可以从链表尾部删除元素如removeLast，peekLast，pollLast，unlinkLast等方法（具体使用方法可看源码或者是api文档）。

4、存取操作

上述一些方法都是实现了Deque接口，实现的一些方法。而接下来要讲述的是实现与List的部分功能。那么最典型的操作就是直接对容器元素的读取，因为List容器的一大特点就是顺序存储，元素在容器中的位置和存入时是保持一致的，那么用户在读取元素的时候理所当然就可以通过元素下标来获取。介绍下面几种方法：

将元素插入容器的指定位置

    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            // 刚好插在链表尾部
            linkLast(element);
        else
            // 如果不是位于末尾，那么就将元素插入指定位置的元素之前
            linkBefore(element, node(index));
    }

    void linkBefore(E e, Node succ) {
        // assert succ != null;
        // 插在两个节点之间
        final Node pred = succ.prev;
        final Node newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

获取指定位置元素

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

   // 获取指定节点
    Node node(int index) {
        
        // 分块查找，看查找元素下标是在链表前半部分还是后半部分
        if (index < (size >> 1)) {
            // 前半部分，用头节点向后遍历
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            // 后半部分，用尾节点向前遍历
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    // 上述分块查找能够大大提高查找效率

5、迭代器实现

LinkedList的迭代器实现有两个，一个是实现了Iterator接口的DescendingIterator，另一个则是实现了ListIterator接口的ListItr。

1、ListItr

    private class ListItr implements ListIterator {
        private Node lastReturned; //最后一个返回的节点
        private Node next; //下一个节点
        private int nextIndex; //下一个节点索引
        private int expectedModCount = modCount;
    }

ListItr遍历需要指定一个起始值

public ListIterator listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }

ListItr会创建一个以index为起始值的迭代器，然后用户便可以以这个位置为起点，实现向前或者向后遍历。

ListItr(int index) {
    // 实例化的时候，将next指针指向指定位置的元素
    next = (index == size) ? null : node(index);
    nextIndex = index;
}

// 向后遍历
public E next() {
    checkForComodification();
    if (!hasNext())
        throw new NoSuchElementException();
    // 返回节点
    lastReturned = next;
    // 继续指向下一个节点
    next = next.next;
    // 下标+1
    nextIndex++;
    return lastReturned.item;
}


// 向前遍历
public E previous() {
    checkForComodification();
    if (!hasPrevious())
        throw new NoSuchElementException();
    lastReturned = next = (next == null) ? last : next.prev;
    nextIndex--;
    return lastReturned.item;
}

2、DescendingIterator

DescendingIterator复用了ListItr的previous()方法，从下可以看出，该迭代器的遍历方式是从链表的末尾逐个向前遍历的。

    public Iterator descendingIterator() {
        return new DescendingIterator();
    }

    private class DescendingIterator implements Iterator {
        private final ListItr itr = new ListItr(size());
        public boolean hasNext() {
            return itr.hasPrevious();
        }
        public E next() {
            return itr.previous();
        }
        public void remove() {
            itr.remove();
        }
    }

LinkedList与 ArrayList 的比较

ArrayList 基于动态数组实现，LinkedList 基于双向链表实现。ArrayList 和 LinkedList 的区别可以归结为数组和链表的区别：

数组支持随机访问O(1)，但插入删除的代价很高，需要移动大量元素O(n)；
链表不支持随机访问O(n)，但插入删除只需要改变指针，插入删除效率较高O(1)；
两个集合使用场景根据其特性进行选择，对查询、获取元素效率要求较高的使用ArrayList ；经常性插入删除元素的场景使用LinkedList。

【Java8-集合源码学习3-CopyOnWriteArrayList、LinkedList源码学习】

Java相关栏目本月热门文章