Java List基本概念

java_collection

List

一个元素有序的、可重复、可以为null的集合
list接口实现的类在实现插入元素时，都会根据索引进行排序
list.sublist返回的是原始引用

AbstractCollection

没有实现boolean add(E)
boolean addAll(Collection c) 通过iterator + add()
boolean clear()通过iterator + remove()
boolean contains(object) 通过iterator + object.equals
boolean containsAll() 通过iterator + contains(o), 时间复杂度为O(n^2)
boolean isEmpty() 通过子类size()
boolean remove(o) 通过子类iterator.remove实现
boolean removeAll(collection) 通过iterator.remove(o) + contains(o)
boolean retainAll(collection) 通过iterator.remove(o) + contains(o)
boolean toArray() 通过转换成arrayList调用toArray()
boolean toString() 通过StringBuffer输出object的地址

AbstractList

是第一个实现随机访问方法的集合类，但不支持添加和替换。
默认不支持的 add(), set(),remove(); throw new UnsupportedOperationException()
indexOf(Object)首次出现，通过ListIterator向后遍历
lastIndexOf(Object)通过ListIterator向前遍历
class SubList主要调用父类list的方法在父类中进行操作。
创建内部迭代器itr和ListItr

实现两个内部子类 SubList 和 RandomAccessSublist:

class SubList<E> extends abstractList<E> {
   //构造参数:
   //list ：父 List
   //fromIndex : 从父 List 中开始的位置
   //toIndex : 在父 List 中哪里结束S
   SubList(AbstractList<E> list, int fromIndex, int toIndex) {
       //省略边界检查
       l = list;
       offset = fromIndex;
       size = toIndex   fromIndex;
       //和父类使用同一个 modCount
       this.modCount = l.modCount;
   }
}

class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
   RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
       super(list, fromIndex, toIndex);
   }

   public List<E> subList(int fromIndex, int toIndex) {
       return new RandomAccessSubList<>(this, fromIndex, toIndex);
   }
}

ArrayList

频繁的读size(), isEmpty(), get(), set(), iterator(), ListIterator() 时间复杂度为O(1)
private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData, transient表示无法序列化
MAX_ARRAY_SIZE = Integer.MAX_VALUE 8;
继承RandomAccess,get的效率大于迭代器
多线程不安全，可以使用List list = Collection.synchronizedList(new ArratList(...))加锁
ArrayList() 默认返回空数组
ArrayList(initialCapacity) 返回指定容量，为空则返回空数组

ArrayList(Collection) 调用toArray()创建数组，失败后通过Arrays.copyOf(),为空则返回空数组

boolean add(E e) {   插入队尾
   //对数组的容量进行调整
   ensureCapacityInternal(size + 1);
   elementData[size++];
   return true;
}

boolean add(indx, elem) {
   rangeCheck(indx);
   ensureCapacityInternal(size + 1);
   System.arraycopy(elementData, indx, elementData, indx + 1, size   indx);
   elementData[indx] = elem;
}

boolean addAll(Collection c) {
   object[] a = c.toArray();
   int numNew = a.length;
   ensureCapacityInternal(size + numNew);
   size += numNew;
   return numNew != 0;
}

ensureCapacityInternal(minCapacity) {
 modCount++;
 if (minCapacity   elementData.length > 0)
     grow(minCapacity);
}

grow(int) {
 int oldCap = elementData.length;
 int newCap = oldCap + (oldCap >> 1);

 if (newCap   minCapacity < 0) newCap = minCapacity;
 if (newCap   MAX_ARRAY_SIZE > 0) newCap = hugeCapcity(minCapacity);
 elementData = Arrays.copyOf(elementData,newCap)
}

private static int hugeCapacity(int minCapacity) {
   if (minCapacity < 0) // overflow
       throw new OutOfMemoryError();
   return (minCapacity > MAX_ARRAY_SIZE) ?
       Integer.MAX_VALUE :
       MAX_ARRAY_SIZE;
}

boolean batchRemove(collection, complement) {
   int r = 0, w = 0;
   try {
       for (; r < size; r++) {
           //根据complement决定是保留还是删除
           if (c.contains(elementData[r] == complement))
               elementData[w++] = elementData[r];
       }
   } finally {
       if (r != size) {
         System.arraycopy(elementData, r, elementData, w, size   r);
         w += size   r;
       }
       if (w != size) {
         //clear to let GC do its work
         for (int i = w; 1 < size; i++)
             elementData[i] = null;
         modCount += size   w;
         size = w;
         return true;
       }
   }
   return false;
}

int indexOf(o)遍历找到的第一个相同元素，调用o.equals(elementData[i]),否则返回-1
int lastIndexOf(o)从尾部遍历找到的第一个相同元素，调用o.equals(elementData[i]),否则返回-1
T[] toArray(T[] a)调用Arrays.copyOf(elementData, size,a.getClass());
iterator、ListIterator通过数组下标实现

AbstractSequentialList

只支持迭代器访问，将ListIterator相关方法实现

LinkedList

插入、删除频繁时使用

void linkFirst(E e) {
  final Node<E> f = first;
  final Node<E> newNode = new Node<>(null, e, f);
  first = newNode;
  if (f == null)
      //只有一个元素时，设置尾节点
      last = newNode;
  else
      f.prev = newNode;
  size++;
  modCount++;
}

void linkLast(E e) //类似linkFirst

boolean add(E object) //加在尾部

void add(indx, E e) //找寻位置，插入节点

//Queue
void push(E e) //插入头部

boolean offer(E e) //插入尾部

boolean offerFirst(E e) //插入头部

E pollLast() //弹出尾部

E pop() //弹出头

//Dequeue
boolean clear() //所有元素置为空

boolean poll() //获取第一个同时删除

boolean peek() //获取第一个不删除

class DescendingIterator implements Iterator<E>{} //倒叙迭代器

class ListItr implements ListIterator<E> {}

Vector

底层由一个可以增长的数组组成
Vector 通过 capacity (容量) 和 capacityIncrement (增长数量) 来尽量少的占用空间
扩容时默认扩大两倍
最好在插入大量元素前增加 vector 容量，那样可以减少重新申请内存的次数
通过 iterator 和 lastIterator 获得的迭代器是 fail-fast 的
通过 elements 获得的老版迭代器 Enumeration 不是 fail-fast 的
同步类，每个方法前都有同步锁 synchronized
在 JDK 2.0 以后，经过优化，Vector 也加入了 Java 集合框架大家族

Vector VS ArrayList

共同点：
- 都是基于数组
- 都支持随机访问
- 默认容量都是 10
- 都有扩容机制
区别：
- Vector 出生的比较早，JDK 1.0 就出生了，ArrayList JDK 1.2 才出来
- Vector 比 ArrayList 多一种迭代器 Enumeration
- Vector 是线程安全的，ArrayList 不是
- Vector 默认扩容2倍，ArrayList是1.5倍
- 如果没有线程安全的需求，一般推荐使用 ArrayList，而不是 Vector，因为每次都要获取锁，效率太低。