目录

ArrayList分析

属性 

常用方法 

构造函数 

增加 

刪除 

  修改

 总结

ArrayList关于删除需要注意的点位 

LinkedList 解析

 Vector解析

 CopyOnWriteArrayList解析

可以从源码看出 List 接口 继承  Collection<E>

在Collection中，List集合是有序的，且可重复的可对其中每个元素的插入位置进行精确地控制，可以通过下标，foreach，迭代器来遍历

List有那么几个类ArrayList、LinkedList、Vector、CopyOnWriteArrayList

ArrayList分析

ArrayList 是一个数组队列，相当于 动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。

 

• AbstractList 抽象类，提供了List接口的相关实现和迭代逻辑的实现，不过对ArrayList意义不大，因为ArrayList大量重写了AbstractList的实现
• List 接口，定义了数组的增删改查迭代遍历等相关操作。
• Cloneable 接口，支持ArrayList克隆
• Serializabel 接口，支持ArrayList序列化与反序列化
• RandomAccess 接口，支持ArrayList快速访问

属性 

可通过源码获取属性

 public class ArrayList<E> extends AbstractList<E>
         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
 {
     // 默认初始容量。
     private static final int DEFAULT_CAPACITY = 10;
     
     // 用于空实例的共享空数组(创建空实例时使用)
     private static final Object[] EMPTY_ELEMENTDATA = {};
     
     // 用于默认大小的空实例的共享空数组实例。
     // 我们将其与EMPTY_ELEMENTDATA区分开来，以便知道添加第一个元素时要膨胀多少。
     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 ​
     // 存储数组列表元素的数组缓冲区。arrayList的容量就是这个数组缓冲区的长度。
     // 任何空的ArrayList 将被扩展到10当(第一次添加元素时)
     // 注意是通过transient修饰
     transient Object[] elementData; // non-private to simplify nested class access
 ​
     // 数组列表的大小(它包含的元素数量)
     private int size;
     
     /* 要分配的数组的最大大小
      * 尝试分配更大的数组可能会导致OutOfMemoryError:请求的数组大小超过VM限制*/
     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
     
     // 该属性是通过继承 AbstractList 得来,列表修改的次数(版本号)
     protected transient int modCount = 0;
 }

通过源码我们可以知道到：

• DEFAULT_CAPACITY 表示ArrayList的初始容量（采用无参构造时第一次添加元素扩容的容量，后面会介绍），默认是10。
• elementData 表示ArrayList实际储存数据的数组，是一个Object[]。
• size 表示该ArrayList的大小(就是elementData包含的元素个数)。
• MAX_ARRAY_SIZE 表示ArrayList能分配的最大容量 Integer.MAX_VALUE - 8
• modCount 表示该ArrayList修改的次数，在迭代时可以判断ArrayList是否被修改。

这里可以看出ArrayList底层实现就是一个数组，其初始容量是10。 

常用方法 

构造函数 

 // 使用指定的初始容量构造一个空列表。
 public ArrayList(int initialCapacity) {
     if (initialCapacity > 0) {
         this.elementData = new Object[initialCapacity];
     } else if (initialCapacity == 0) {
         this.elementData = EMPTY_ELEMENTDATA; // 如果为0使用默认空数组
     } else {
         throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
     }
 }
 ​
 /*Constructs an empty list with an initial capacity of ten.
 * 构造一个初始容量为10的空列表。(在第一次扩容时容量才为10，现在还是null)*/
 public ArrayList() {
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }
 ​
 // 构造一个包含指定集合的元素的列表，按照集合的迭代器返回它们的顺序。
 public ArrayList(Collection<? extends E> c) {
     elementData = c.toArray(); // 将集合转变为数组
     // 赋值 size 并判非 0
     if ((size = elementData.length) != 0) {
         // c.toArray might (incorrectly) not return Object[] (see 6260652) 这是一个bug在java9已经被解决
         if (elementData.getClass() != Object[].class)
             elementData = Arrays.copyOf(elementData, size, Object[].class);
     } else {
         // replace with empty array.
         this.elementData = EMPTY_ELEMENTDATA;
     }
 }

通过查看源码我们可以发现：

• ArrayList 有三个构造函数：指定初始化大小构造，无参构造，指定初始化数据构造
• ArrayList的无参构造，其实默认是空数组，我们上面说的初始化容量默认为10，是当我们用无参构造函数后，第一次向ArrayList添加元素时扩容的默认大小。

增加 

ArrayList添加元素的方法有四个：一个是在末尾添加，一个是指定索引添加，另两个是在末尾添加集合和在指导索引位置添加集合 

 // 将指定的元素添加到列表的末尾。
 public boolean add(E e) {
     // 确保容量足够
     ensureCapacityInternal(size + 1);  // Increments modCount!!
     elementData[size++] = e;
     return true;
 }
 ​
 // 在列表指定的位置插入指定的元素。
 // 将当前位于该位置的元素(如果有的话)和随后的元素向右移动(下标加1)。
 public void add(int index, E element) {
     // 确保索引合法
     rangeCheckForAdd(index);
     // 确保容量
     ensureCapacityInternal(size + 1);  // Increments modCount!!
     // 移动元素 （原始数组,起始位置，目标数组，起始位置，拷贝大小）
     System.arraycopy(elementData, index, elementData, index + 1, size - index);
     elementData[index] = element;
     size++; // 大小加 1
 }
 ​
 private void ensureCapacityInternal(int minCapacity) {
     // 判断是不是通过无参构造创建的
     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
         // 这才是第一次添加元素是默认扩容到10
         minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
     }
     ensureExplicitCapacity(minCapacity);
 }
 ​
 // 预扩容
 private void ensureExplicitCapacity(int minCapacity) {
     modCount++; // 修改版本号
     // overflow-conscious code 
     if (minCapacity - elementData.length > 0)
         grow(minCapacity);
 }
 ​
 // 增加容量，以确保至少可以保存由最小容量(minCapacity)参数指定的元素数量。
 private void grow(int minCapacity) {
     // overflow-conscious code
     int oldCapacity = elementData.length;
     // 1.5倍扩容
     int newCapacity = oldCapacity + (oldCapacity >> 1);
     if (newCapacity - minCapacity < 0) // 扩容后不满足期望大小则以期望大小作为容量
         newCapacity = minCapacity;
     if (newCapacity - MAX_ARRAY_SIZE > 0) // 分配jvm的最大容量，防溢出
         newCapacity = hugeCapacity(minCapacity);
     // minCapacity is usually close to size, so this is a win:
     // 扩容
     elementData = Arrays.copyOf(elementData, newCapacity);
 }
 ​
 // 分配最大容量
 private static int hugeCapacity(int minCapacity) {
     if (minCapacity < 0) // overflow 
         throw new OutOfMemoryError();
     return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
 }
 ​
 // 将指定集合中的所有元素追加到此列表的末尾。按照指定集合的迭代器返回它们的顺序。
 public boolean addAll(Collection<? extends E> c) {
     Object[] a = c.toArray(); // 集合转数组
     int numNew = a.length;  // 获取要添加的长度
     ensureCapacityInternal(size + numNew);  // Increments modCount
     System.arraycopy(a, 0, elementData, size, numNew); // 通过元素拷贝来追加元素
     size += numNew;
     return numNew != 0;
 }
 ​
 // 将指定集合中的所有元素插入到此列表中，从指定位置开始。
 // 新元素将按照指定集合的迭代器返回的顺序出现在列表中。
 public boolean addAll(int index, Collection<? extends E> c) {
     rangeCheckForAdd(index); // 检查索引是否合法
     
     Object[] a = c.toArray();
     int numNew = a.length;
     ensureCapacityInternal(size + numNew);  // Increments modCount
     
     int numMoved = size - index;
     if (numMoved > 0) // 腾出空位
         System.arraycopy(elementData, index, elementData, index + numNew,numMoved);
     // 将a拷贝到elementData
     System.arraycopy(a, 0, elementData, index, numNew);
     size += numNew;
     return numNew != 0;
 }

 

通过源码我们需要注意：

• 扩容是原容量+原容量大小一半，也就是说是按照1.5倍扩容:oldCapacity + (oldCapacity >> 1),但最后的容量并不一定是按照这个规则计算得到的大小，因为他还有两个if判断。
• ArrayList中数组最大只能分配Integer.MAX_VALUE,在大就会导致OutOfMemoryError。
• ArrayList扩容时有许多溢出判断操作，这非常值得借鉴。
• ArrayList扩容底层调用的是System.arraycopy(Object src,int srcPos,Object dest, int destPos,in

数组容量会改变，改变的规则是按照原数组1.5倍进行扩容，但最终容量不一定是通过该规则计算得到的值，因为后面有两个if判断：1.是否满足期望容量；2.是否超出jvm分配的最大容量 

刪除 

 // 删除列表中指定位置的元素。将所有后续元素向左移动(从它们的下标减去1)。
 public E remove(int index) {
     // 确保index合法
     rangeCheck(index);
 ​
     modCount++;
     E oldValue = elementData(index); // 获取老元素
 ​
     int numMoved = size - index - 1;
     // 判断是否需要移动
     if (numMoved > 0)
         System.arraycopy(elementData, index+1, elementData, index,numMoved);
     elementData[--size] = null; // clear to let GC do its work
 ​
     return oldValue;
 }
 ​
 // 从列表中删除指定元素的第一个匹配项，如果它存在的话并返回 true。
 public boolean remove(Object o) {
     if (o == null) { // 空值单独删除,因为add时也没有对null进行效验
         for (int index = 0; index < size; index++)
             if (elementData[index] == null) {
                 fastRemove(index); // 移除元素
                 return true;
             }
     } else {
         for (int index = 0; index < size; index++)
             if (o.equals(elementData[index])) { // 通过equals比较，如果是自定义对象元素，一定要重写它
                 fastRemove(index);
                 return true;
             }
     }
     return false;
 }
 ​
 // 跳过边界检查的移除方法(因为已经被验证边界合法)
 private void fastRemove(int index) {
     modCount++;
     int numMoved = size - index - 1;
     if (numMoved > 0) // 通过数组拷贝覆盖来移除元素
         System.arraycopy(elementData, index+1, elementData, index,numMoved);
     elementData[--size] = null; // clear to let GC do its work
 }
 ​
 // 从此列表中删除指定集合中包含的所有元素。
 // 如果此列表包含空元素，而指定的集合不允许空元素则会抛出NullPointerException
 public boolean removeAll(Collection<?> c) {
     // 判断是否为null
     Objects.requireNonNull(c);
     return batchRemove(c, false);
 }
 ​
 // 通过不同complement来操作列表
 private boolean batchRemove(Collection<?> c, boolean complement) {
     final Object[] elementData = this.elementData;
     int r = 0, w = 0;
     boolean modified = false;
     try {
         for (; r < size; r++) // complement决定操作行为
             if (c.contains(elementData[r]) == complement) 
                 elementData[w++] = elementData[r];
     } finally {
         // Preserve behavioral compatibility with AbstractCollection,
         // even if c.contains() throws.
         if (r != size) {
             System.arraycopy(elementData, r,elementData, w,size - r);
             w += size - r; 
         }
         if (w != size) { // 将删除的元素赋null
             // clear to let GC do its work
             for (int i = w; i < size; i++)
                 elementData[i] = null;
             modCount += size - w;
             size = w;
             modified = true;
         }
     }
     return modified;
 }
 ​
 @Override
 public boolean removeIf(Predicate<? super E> filter) {
     Objects.requireNonNull(filter);
     // figure out which elements are to be removed 找出要删除的元素
     // any exception thrown from the filter predicate at this stage
     // will leave the collection unmodified
     int removeCount = 0;
     final BitSet removeSet = new BitSet(size); // 记录要删除元素的集合
     final int expectedModCount = modCount; // 记录版本号
     final int size = this.size;
     for (int i=0; modCount == expectedModCount && i < size; i++) {
         @SuppressWarnings("unchecked")
         final E element = (E) elementData[i];
         if (filter.test(element)) { // 记录要删除的元素index
             removeSet.set(i);
             removeCount++;
         }
     }
     if (modCount != expectedModCount) { // 如果版本号不一致，抛出异常
         throw new ConcurrentModificationException();
     }
 ​
     // shift surviving elements left over the spaces left by removed elements
     final boolean anyToRemove = removeCount > 0;
     if (anyToRemove) {
         final int newSize = size - removeCount;
         // 遍历并剔除要删除的元素
         for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
             i = removeSet.nextClearBit(i);
             elementData[j] = elementData[i];
         }
         for (int k=newSize; k < size; k++) {
             elementData[k] = null;  // Let gc do its work
         }
         this.size = newSize;
         if (modCount != expectedModCount) {
             throw new ConcurrentModificationException();
         }
         modCount++;
     }
     return anyToRemove;
 }

通过源码我们可以知道：

• ArrayList删除元素是通过System.arraycopy移动数组覆盖元素来实现的
• ArrayList添加元素时没有校验null值，所以删除null值时是特殊处理的
• ArrayList通过对象删除时判断相等是通过equals判断，所以我们在储存自定义对象是要注意对equals进行重写

  修改

 // 将列表中指定位置的元素替换为指定的元素。
 public E set(int index, E element) {
     rangeCheck(index);
     E oldValue = elementData(index);
     elementData[index] = element;
     // 返回被替换的元素
     return oldValue;
 }

 总结

简单数据结构，超出容量自动扩容，动态数组
内部实现是基于基础的对象数组的
随机访问快
不适合随机增加或删除
线程不安全

ArrayList关于删除需要注意的点位 

ArrayList remove 的注意点
    数据准备：为方便演示，需要有紧挨在一起的两个或多个相同的元素
          List<Integer> list=new ArrayList<Integer>();
  list.add(1);
  list.add(2);
  list.add(3);
  list.add(3);
  list.add(4); 

for(int i=0;i<list.size();i++){
   if(list.get(i)==3) list.remove(i);
}
	错误，为啥？
    因为ArrayList是一个有序的动态数组
    移除一个后面的元素会往上顶，顶替删除
    元素下标，这样的情况会发生在有相同的
    元素并且相邻紧凑
for(int i=0;i<list.size();i++){
   if(list.get(i)==3) list.remove(i--);
}
	正确，为啥？
    因为ArrayList是一个有序的动态数组
    移除一个后面的元素会往上顶，顶替删除
    元素下标，因为删除成功使用了i--
    会再一次比较当前的下标是否符合条件
for(int i=list.size()-1;i>=0;i--){
 if(list.get(i)==3){
  list.remove(i);
 }
}
	正确，为啥？
    因为ArrayList是一个有序的动态数组
    移除一个后面的元素会往上顶，顶替删除
    元素下标,换位思考如果是从后面删除的话
    就算删掉了，下标上的问题也不会错位
for(Integer i:list){
    if(i==3) list.remove(i);
}
	错误，？？
    因为foreach遍历遵循了迭代器的判定规则
    list.remove()删除方法，只是删除了元素
    没有让迭代器 expectedModCount = modCount;
    修改次数和期望次数相等抛出异常
    这里会有一个bug如果刚好删除的是倒数第二位，
    这里不会触发异常
Iterator<Integer> it=list.iterator();
 while(it.hasNext()){
  if(it.next()==3){
   it.remove();
  }
}
	正确，？？
因为使用了迭代器，迭代器里面封装好了
删除时会使expectedModCount = modCount;
这两个值相等
Iterator<Integer> it=list.iterator();
 while(it.hasNext()){
  Integer value=it.next();
   if(value==3){
   list.remove(value);
  }
}
	错误，？？
虽然使用了迭代器，但是最终删除调用方法的是list
这个对象，而不是迭代器实例化的
最终导致expectedModCount = modCount
不一致抛出异常
 
list.remove(2);
	输出结果是什么？
如果是一个整数类型，则是根据下标删除元素
如果是对象，就直接删除元素

LinkedList 解析

LinkedList底层通过双向链表实现

LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元，当链表为空的时候first和last都指向null。

LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步（synchronized），如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装

LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部
线程不安全
LinkedList可被用作堆栈（stack）【包括了push，pop方法】，队列（queue）或双向队列（deque）
以双向链表实现，链表无容量限制，允许元素为null，线程不安全
适合做随机的增加或删除 

 Vector解析

可用于在需要存储有序的，可动态扩充线程安全的集合。整理逻辑算法上基本与ArrayList相同，但在操做数据的方法上都使用了synchronized关键字，在多 线程调用时，会将并行请求，变为串行请求，因为使用了synchronized方法，所以他的性能方面比ArrayList要差 

并行性能慢，不建议使用 

 CopyOnWriteArrayList解析

（拷贝写数组) 是ArrayList线程安全的集合其中所有可变操作（add、set等等）都是通过对底层数组进行一次新的复制来实现的。
它不存在“扩容”的概念，每次写操作（add 、remove）都要copy一个副本，在副本的基础上修改后改变array引用，所以称为“CopyOnWrite”，因此在写操作是加锁，并且对整个list的copy操作时相当耗时的，过多的写操作不推荐使用该存储结构。读取的方法没有加锁 写的时候才加锁 所以性能 比 vector高

写时复制
线程安全
适合于读多，写少的场景
写时复制出一个新的数组，完成插入、修改或者移除操作后将新数组赋值给array
比Vector性能高
最终一致性
实现了List接口，使用方式与ArrayList类似

今天分享就到此结束了