深入LinkedList,CopyOnWriteArrayList底层原理与源码解析

原创

用户8639654

修改于 2021-07-23 17:53:14

33700

代码可运行

文章被收录于专栏：云计算运维云计算运维

运行总次数：0

代码可运行

LinkedList

特性

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

继承于 AbstractSequentialList ，本质上与继承 AbstractList 没有什么区别，AbstractSequentialList 完善了 AbstractList 中没有实现的方法。
Serializable：成员变量 Node 使用 transient 修饰，通过重写read/writeObject 方法实现序列化。
Cloneable：重写clone（）方法，通过创建新的LinkedList 对象，遍历拷贝数据进行对象拷贝。
Deque：实现了Collection 大家庭中的队列接口，说明他拥有作为双端队列的功能。
LinkedList与ArrayList最大的区别就是LinkedList中实现了Collection中的 Queue（Deque）接口拥有作为双端队列的功能

基本属性

链表没有长度限制，他的内存地址不需要分配固定长度进行存储，只需要记录下一个节点的存储地址即可完成整个链表的连续。

//当前有多少个结点，元素个数
transient int size = 0;
//第一个结点
transient Node<E> first;
//最后一个结点
transient Node<E> last;
//Node的数据结构
private static class Node<E> {
    E item;//存储元素
    Node<E> next;//后继
    Node<E> prev;//前驱
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

LinkedList 在1.6 版本以及之前，只通过一个 header 头指针保存队列头和尾。这种操作可以说很有深度，但是从代码阅读性来说，却加深了阅读代码的难度。因此在后续的JDK 更新中，将头节点和尾节点区分开了。节点类也更名为 Node。

为什么Node这个类是静态的？答案是：这跟内存泄露有关，Node类是在LinkedList类中的，也就是一个内部类，若不使用static修饰，那么Node就是一个普通的内部类，在java中，一个普通内部类在实例化之后，默认会持有外部类的引用，这就有可能造成内存泄露（内部类与外部类生命周期不一致时）。但使用static修饰过的内部类（称为静态内部类），就不会有这种问题

非静态内部类会自动生成一个构造器依赖于外部类：也是内部类可以访问外部类的实例变量的原因

静态内部类不会生成，访问不了外部类的实例变量，只能访问类变量

构造器

public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);//操作次数只会记录一次   设置前驱后继
}

添加元素

public boolean add(E e) {
     linkLast(e);
     return true;
 }
//目标节点创建后寻找前驱节点， 前驱节点存在就修改前驱节点的后继，指向目标节点
void linkLast(E e) {
    final Node<E> l = last;//获取这个list对象内部的Node类型成员last，即末位节点，以该节点作为新插入元素的前驱节点
    final Node<E> newNode = new Node<>(l, e, null);//创建新节点
    last = newNode;//把新节点作为该list对象的最后一个节点
    if (l == null)//处理原先的末位节点，如果这个list本来就是一个空的链表
        first = newNode;//把新节点作为首节点
    else
        l.next = newNode;//如果链表内部已经有元素，把原来的末位节点的后继指向新节点，完成链表修改
    size++;//修改当前list的size，
    modCount++;//并记录该list对象被执行修改的次数
}
public void add(int index, E element) {
    checkPositionIndex(index);//检查下标的合法性
    if (index == size)//插入位置是末位，那还是上面末位添加的逻辑
        linkLast(element);
    else
        linkBefore(element, node(index));
}
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}
Node<E> node(int index) {
    if (index < (size >> 1)) {//二分查找   index离哪端更近 就从哪端开始找
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;//找到index位置的元素
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
//指位添加方法核心逻辑  操作新节点，紧接修改原有节点的前驱属性，最后再修改前驱节点的后继属性
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;//原位置节点的前驱pred
    final Node<E> newNode = new Node<>(pred, e, succ);//创建新节点,设置新节点其前驱为原位置节点的前驱pred，其后继为原位置节点succ
    succ.prev = newNode;//将新节点设置到原位置节点的前驱
    if (pred == null)//前驱如果为空，空链表，则新节点设置为first
        first = newNode;
    else
        pred.next = newNode;//将新节点设置到前驱节点的后继
    size++;//修改当前list的size
    modCount++;//记录该list对象被执行修改的次数。
}
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);
    //将集合转化为数组
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Node<E> pred, succ;
    //获取插入节点的前节点（prev）和尾节点（next）
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }
    //将集合中的数据编织成链表
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }
    //将 Collection 的链表插入 LinkedList 中。
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
    size += numNew;
    modCount++;
    return true;
}

final修饰，不希望在运行时对变量做重新赋值

LinkedList 在插入数据优于ArrayList ，主要是因为他只需要修改指针的指向即可，而不需要将整个数组的数据进行转移。而LinkedList 由于没有实现 RandomAccess，或者说不支持索引搜索的原因，他在查找元素这一操作，需要消耗比较多的时间进行操作（n/2）。

删除元素

1、AbstractSequentialList的remove

public E remove(int index) {
    checkElementIndex(index);
    //node(index)找到index位置的元素
    return unlink(node(index));
}
//remove(Object o)这个删除元素的方法的形参o是数据本身，而不是LinkedList集合中的元素（节点），所以需要先通过节点遍历的方式，找到o数据对应的元素，然后再调用unlink(Node x)方法将其删除
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}
E unlink(Node<E> x) {
    //x的数据域element
    final E element = x.item;
    //x的下一个结点
    final Node<E> next = x.next;
    //x的上一个结点
    final Node<E> prev = x.prev;
    //如果x的上一个结点是空结点的话，那么说明x是头结点
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;//将x的前后节点相连   双向链表
        x.prev = null;//x的属性置空
    }
    //如果x的下一个结点是空结点的话，那么说明x是尾结点
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;//将x的前后节点相连   双向链表
        x.next = null;
    }
    x.item = null;//指向null  方便GC回收
    size--;
    modCount++;
    return element;
}

2、Deque 中的Remove

//将first 节点的next 设置为新的头节点，然后将 f 清空。 removeLast 操作也类似。
private E unlinkFirst(Node<E> f) {
    final E element = f.item;
    //获取到头结点的下一个结点           
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // 方便 GC
    //头指针指向的是头结点的下一个结点
    first = next;
    //如果next为空，说明这个链表只有一个结点
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

双端链表（队列Queue）

java中队列的实现就是LinkedList：我们之所以说LinkedList 为双端链表，是因为他实现了Deque 接口；我们知道，队列是先进先出的，添加元素只能从队尾添加，删除元素只能从队头删除，Queue中的方法就体现了这种特性。支持队列的一些操作，我们来看一下有哪些方法实现：

pop（）是栈结构的实现类的方法，返回的是栈顶元素，并且将栈顶元素删除
poll（）是队列的数据结构，获取对头元素并且删除队头元素
push（）是栈结构的实现类的方法，把元素压入到栈中
peek（）获取队头元素，但是不删除队列的头元素
offer（）添加队尾元素

可以看到Deque 中提供的方法主要有上述的几个方法，接下来我们来看看在LinkedList 中是如何实现这些方法的。

1.1、队列的增

offer（）添加队尾元素

public boolean offer(E e) {
    return add(e);
}

具体的实现就是在尾部添加一个元素

1.2、队列的删

poll（）是队列的数据结构，获取对头元素并且删除队头元素

public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

具体的实现前面已经讲过，删除的是队列头部的元素

1.3、队列的查

peek（）获取队头元素，但是不删除队列的头元素

public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

1.4、栈的增

push（）是栈结构的实现类的方法，把元素压入到栈中

push（）方法的底层实现，其实就是调用了 addFirst（Object o）

public void push(E e) {
    addFirst(e);
}

1.5、栈的删

pop（）是栈结构的实现类的方法，返回的是栈顶元素，并且将栈顶元素删除

public E pop() {
    return removeFirst();
}
public E removeFirst() {
    final Node f = first;
    if (f == null)
    throw new NoSuchElementException();
    return unlinkFirst(f);
}

CopyOnWriteArrayList

特性

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

特性基本与arrayList一致，底层也是数组结构

基本属性

private static final long serialVersionUID = 8673264195747942595L;//序列化版本号
//全局锁
final transient ReentrantLock lock = new ReentrantLock();
//存储数据的数组
private transient volatile Object[] array;

构造器

public CopyOnWriteArrayList() {
    setArray(new Object[0]);//创建一个大小为0的Object数组作为array初始值
}
public CopyOnWriteArrayList(E[] toCopyIn) {
    //创建一个list，其内部元素是toCopyIn的的副本
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
//将传入参数集合中的元素复制到本list中
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class)
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        elements = c.toArray();
        // c.toArray可能不是Object[]（比如：继承ArrayList，重写toArray方法返回String[]，
        //只有ArrayList的toArray方法实现是Arrays.copyOf，因此在jdk8中，此处改为了ArrayList.class）
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    setArray(elements);
}

添加元素

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);//复制到新数组中，长度+1
        newElements[len] = e;//在新数组中添加元素
        setArray(newElements);//将新数组设置给array
        return true;
    } finally {
        lock.unlock();
    }
}

指定位置添加元素

public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        // 获取旧数组
        Object[] elements = getArray();
        int len = elements.length;
        // 检查是否越界, 可以等于len
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+len);
        Object[] newElements;
        int numMoved = len - index;
        if (numMoved == 0)
            // 如果插入的位置是最后一位
            // 那么拷贝一个n+1的数组, 其前n个元素与旧数组一致
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            // 如果插入的位置不是最后一位
            // 那么新建一个n+1的数组
            newElements = new Object[len + 1];
            // 拷贝旧数组前index的元素到新数组中
            System.arraycopy(elements, 0, newElements, 0, index);
            // 将index及其之后的元素往后挪一位拷贝到新数组中
            // 这样正好index位置是空出来的
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        // 将元素放置在index处
        newElements[index] = element;
        setArray(newElements);
    } finally {
        // 释放锁
        lock.unlock();
    }
}

addIfAbsent

//添加一个不存在于集合中的元素。
public boolean addIfAbsent(E e) {
    // 获取元素数组
    Object[] snapshot = getArray();
    //已存在返回false，否则添加
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
        addIfAbsent(e, snapshot);
}

private boolean addIfAbsent(E e, Object[] snapshot) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        // 重新获取旧数组
        Object[] current = getArray();
        int len = current.length;
        // 如果快照与刚获取的数组不一致，说明有修改
        if (snapshot != current) {
            // 重新检查元素是否在刚获取的数组里，减少indexOf的对比次数
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                //判断是否有线程指定下标添加了元素
                if (current[i] != snapshot[i] && eq(e, current[i]))
                    return false;
            if (indexOf(e, current, common, len) >= 0)
                    return false;
        }
        // 拷贝一份n+1的数组
        Object[] newElements = Arrays.copyOf(current, len + 1);
        // 将元素放在最后一位
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        // 释放锁
        lock.unlock();
    }
}

获取指定位置元素

public E get(int index) {
    return get(getArray(), index);
}
final Object[] getArray() {
    return array;
}
//私有方法
private E get(Object[] a, int index) {
    return (E) a[index];
}

这个方法是线程不安全的，因为这个分成了两步，分别是获取数组和获取元素，而且中间过程没有加锁。假设当前线程在获取数组（执行getArray()）后，其他线程修改了这个CopyOnWriteArrayList，那么它里面的元素就会改变，但此时当前线程返回的仍然是旧的数组，所以返回的元素就不是最新的了，这就是写时复制策略产生的弱一致性问题。

修改指定位置元素

public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();    
    try {
        Object[] elements = getArray();
        E oldValue = get(elements, index);//先获取要修改的旧值
        if (oldValue != element) {//值确实需要修改
            int len = elements.length;
            //将array复制到新数组
            Object[] newElements = Arrays.copyOf(elements, len);            
            newElements[index] = element;//修改元素
            setArray(newElements);//设置array为新数组
        } else {
            // 虽然值不需要改，但要保证volatile语义，需重新设置array
            setArray(elements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

删除元素

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 {
            //将元素分两次复制到新数组中
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);//拷贝index前面的元素
            System.arraycopy(elements, index + 1, newElements, index,numMoved);//拷贝index后面的元素
            setArray(newElements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

弱一致性的迭代器

指返回迭代器后，其他线程对list的增删改对迭代器是不可见的

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);   //返回一个COWIterator对象
}
static final class COWIterator<E> implements ListIterator<E> {
    //数组array快照
    private final Object[] snapshot;
    //遍历时的数组下标
    private int cursor;
    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;//保存了当前list的内容
    }
    public boolean hasNext() {
        return cursor < snapshot.length;
    }
    @SuppressWarnings("unchecked")
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }

如果在返回迭代器后没有对里面的数组array进行修改，则这两个变量指向的确实是同一个数组；但是若修改了，则根据前面所讲，它是会新建一个数组，然后将修改后的数组复制到新建的数组，而老的数组就会被“丢弃”，所以如果修改了数组，则此时snapshot指向的还是原来的数组，而array变量已经指向了新的修改后的数组了。这也就说明获取迭代器后，使用迭代器元素时，其他线程对该list的增删改不可见，因为他们操作的是两个不同的数组，这就是弱一致性。

CopyOnWriteArrayList使用写时复制策略保证list的一致性，而获取–修改–写入三个步骤不是原子性，所以需要一个独占锁保证修改数据时只有一个线程能够进行。另外，CopyOnWriteArrayList提供了弱一致性的迭代器，从而保证在获取迭代器后，其他线程对list的修改是不可见的，迭代器遍历的数组是一个快照。

使用场景及优点

并发容器用于读多写少的并发场景。比如白名单，黑名单等场景。

读操作可能会远远多于写操作的场景。比如，有些系统级别的信息，往往只需要加载或者修改很少的次数，但是会被系统内所有模块频繁的访问。对于这种场景，我们最希望看到的就是读操作可以尽可能的快，而写即使慢一些也没关系。

CopyOnWriteArrayList 的思想比读写锁的思想更进一步。为了将读取的性能发挥到极致，CopyOnWriteArrayList 读取是完全不用加锁的，更厉害的是，写入也不会阻塞读取操作，也就是说你可以在写入的同时进行读取，只有写入和写入之间需要进行同步，也就是不允许多个写入同时发生，但是在写入发生时允许读取同时发生。这样一来，读操作的性能就会大幅度提升。

读写分离

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

node.js

编程算法

java

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

node.js

编程算法

java

登录后参与评论

0 条评论

热度