ArrayList、LinkedList、CopyOnWriteArrayList源码分析记录

90 阅读 0 评论 60 点赞

我是靠谱客的博主土豪树叶，最近开发中收集的这篇文章主要介绍ArrayList、LinkedList、CopyOnWriteArrayList源码分析记录，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

最近学习了ArrayList、LinkedList、CopyOnWriteArrayList底层源码，来记录一下自己所学到的东西。

ArrayList 底层是基于动态数组来进行的

List的长度size是根据增删元素来进行自增或自减的；
ArrayList在新增元素时，先判断数组的长度是否足够，若足够则把新元素添加至数组中，若不够则进行扩容(也就是数组的复制)，扩容完成后把新增的元素添加到新数组中即可完成数据的新增操作；
ArrayList在删除元素时，同样是依靠数组的复制来进行的，数组中的元素整体向前移动一位，把要删除的元素覆盖掉，这样数组的最后一个位置就空出来了并将其置为null，这样GC就会将其回收，至此删除操作就完成了；
ArrayList在进行增删改操作时依赖数组的复制来进行，所以当数组的数据量较大时且操作的元素在数组的末尾时，ArrayList的效率较高（因为需复制的元素个数较少）；
System.arraycopy(源数组,源数组下标起始位置,目标数组,目标数组的下标起始位置,要复制的源数组的长度);
Arrays.copyOf(源数组，目标数组的长度);
ArrayList 实现了RandomAccess接口（是个标志接口，接口中没有任何方法，实现此接口的用普通for循环遍历数据，没有实现此接口的用Iterator迭代器来进行遍历数据），查询效率较高，但修改数据的速度较慢，适合用普通for循环来遍历其数据，是线程不安全的。

LinkedList 底层是基于双向链表（指针）来进行的，

第一个元素：| previous | element | next | …_______________ … 第二个元素： | previous | element | next |
previous :指向上一个元素的引用地址
next：指向下一个元素的引用地址
element : 存放的是真正的数据
第一个元素.next = 第二个元素.previous / 第二个元素.next = 第一个元素.previous
LinkedList 的增删改都是通过修改链表的 previous 和 next进行的，修改速度较快，但是查找元素速度较慢。
LinkedList 适合用foreach来遍历数据，效率较高，是线程不安全的。

ArrayList、LinkedList区别：

ArrayList 查找元素效率高，但修改元素效率低（涉及数组的复制）
LinkedList 查找元素效率低，但修改元素效率高
当ArrayList 操的数据在数组末端时，对数据的操作效率不亚于LinkedList ；当LinkedList 操作的数据在链表靠前位置时，操作效率高于ArrayList 。
顺序插入时ArrayList 速度较快

CopyOnWriteArrayList对数据的操作类似ArrayList，但和ArrayList又不同

其增加、删除、修改、插入的操作原理都是一样的，底层就是一个Object [] array，然后实例化一个新的数组;
在多线程并发操作此数据时,CopyOnWriteArrayList能够保证数据的最终一致性(即：读写分离、最终一致，读操作原来的数组，写操作新的数组，最终进行同步)，是线程安全的。

以add方法为例:

3.1 先看对CopyOnWriteArrayList 的定义

 public class CopyOnWriteArrayList<E>
 implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
 private static final long serialVersionUID = 8673264195747942595L;
 
 transient final ReentrantLock lock = new ReentrantLock();
 
 private volatile transient Object[] array;   // 底层就是这个数组
    ...
}

public CopyOnWriteArrayList() { // 实例化此对象时会指向一个长度为0的新数组
     setArray(new Object[0]);
}

final void setArray(Object[] a) {  // 把Object[] array引用指向新创建的数组
    array = a;
}

3.2 再看add方法的定义 （可以分析出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);  // 把Object array引用指向新创建的数组
      return true;
   } finally {
      lock.unlock();          // 解锁
   }
}