1.List简介

List接口是Java对线性表（逻辑上的）的特征的抽象。

2.List接口的实现

2.1ArrayList

最常用的List集合实现，是一种动态可增长基于数组的有序集合。

2.1.1基本特征

①数据存储是基于数组实现的（默认数组大小为10）；
②添加数据时，会首先检测是否超过数组容量，如果超过了则需要对数组进行扩容（扩容采用Arrays.copyOf（）方法，代价很高避免扩容这样的操作）；
③删除数据时，需要将删除点+1位置开始到数组末尾的数据全部向前移动一位。
④获取数据很快，根据数组下标可以直接获取。
⑤此实现不是线程安全的；

2.1.2 ArrayList的实现

2.1.2.1 属性

 private transient Object[] elementData;//存储元素 transient标识的属性在序列化时并不会被序列化
 private int size;//数组内元素的数量

2.1.2.2 常用API及特殊API

tip1：因为底层是基于数组的，那么自然的在末尾增加移除元素是较容易的，在指定位置插入移除元素就相对的消耗时间了.
tip2：因为底层是基于数组的，按下标取元素时间复杂度就是常数了

2.1.2.2.1 add()系列

public boolean add(E e);//在末尾加入元素
public void add(int index, E element) ;//在指定位置插入元素,包括当前位置元素在内以后的元素向右移动（index加1）。 
public boolean addAll(int index, Collection<? extends E> c);//在末尾增加元素列表
public boolean addAll(int index, Collection<? extends E> c);//在指定位置插入元素列表

2.1.2.2.2 remove()系列

public boolean remove(Object o);//根据指针去除元素
public boolean remove(int index);//根据游标去除元素
public boolean removeAll(Collection<?> c);//去除c内包含的元素

2.1.2.2.3 set()系列

public E set(int index, E element);//替换指定位置的元素

2.1.2.2.4 get()系列

 public E get(int index);//返回制定位置的元素

2.1.2.2.5 subList(int fromIndex, int toIndex)

public List<E> subList(int fromIndex, int toIndex);
//返回当前List中对于(fromIndex,toIndex)部分的引用

注意：和String.subString()完全不一样，例如：
ArrayList<Object> objs1= new ArrayList<Object>(100);
objs1.subList(0, 5).clear();//objs1 中下标为0,1,2,3,4的数据会变成null；

2.1.2.2.5 trimToSize()；

public void trimToSize();//将List的capacity削减到和size大小一致；

2.2LinkedList

LinkedList是List接口基于双向链表的实现，基于链表使得LinkedList在插入和删除时更优于ArrayList，而随机访问则比ArrayList逊色些。

2.2.1数据结构

double-linked.jpg

2.2.2数据结构的代码描述

transient Node<E> first;//LinkedList的首指针
transient Node<E> last;//LinkedList的尾指针
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;
  }
}

2.2.2常用API及其实现

2.2.2.1 add()系列：

public boolean add(E e)；//末尾追加元素

public boolean add(E e) {
  linkLast(e);
  return true;
}
void linkLast(E e) {
  final Node<E> l = last;//取最后一个元素
  final Node<E> newNode = new Node<>(l, e, null);//构造新节点
  last = newNode;//设置新节点为最后的节点
 if (l == null)//如果为新构造的空链表，则把首指针也设置为尾指针
    first = newNode;
 else
   l.next = newNode;//进行链接
   size++;//元素数量增加
   modCount++;//fast-fail 机制支持
}

objs2.add(index, element)；//在指定下标插入元素,涉及到双向列表的遍历

public void add(int index, E element) {
  checkPositionIndex(index);//检测是否查过元素数量
  if (index == size)//如果是在末尾插入，则直接追加
    linkLast(element);
  else
    linkBefore(element, node(index));//在指定位置插入元素
}
//双向链表的遍历
Node<E> node(int index) {
  if (index < (size >> 1)) {//在index小于size的一半时，从first向后遍历
    Node<E> x = first;
    for (int i = 0; i < index; i++)
      x = x.next;
    return x;
  } else {//在index大于size的一半时，从last向前遍历
    Node<E> x = last;
    for (int i = size - 1; i > index; i--)
      x = x.prev;
    return x;
  }
}
//插入元素e在succ前面
void linkBefore(E e, Node<E> succ) {
  // assert succ != null;
  final Node<E> pred = succ.prev;
  final Node<E> newNode = new Node<>(pred, e, succ);
  succ.prev = newNode;
  if (pred == null)
    first = newNode;
  else
    pred.next = newNode;
    size++;
    modCount++;
}

public void addFirst(E e)；//首部添加
public void addLast(E e);//尾部添加
public boolean addAll(Collection<? extends E> c)；//末尾链接集合
public boolean addAll(int index, Collection<? extends E> c)；//在指定位置插入集合，也涉及到index的遍历，可参考上面两个来写，遍历找到index位置节点然后循环追加，然后链接上。

2.2.2.2 clear（）：

public void clear()；//置空双向链表,同时置空每个节点的首尾指针，尽管置空节点的首尾指针比不必要的但是
-helps a generational GC if the discarded nodes inhabit more than one generation
-is sure to free memory even if there is a reachable Iterator
也就是避免 ‘在这个List的某些特定的节点仍有外部引用指向时，导致的其他节点不可被清理’ 涉及到分代GC的原理

public void clear() {
  for (Node<E> x = first; x != null; ) {
    Node<E> next = x.next;
    x.item = null;
    x.next = null;
    x.prev = null;
    x = next;
   }
   first = last = null;
   size = 0;
   modCount++;
}

2.2.2.2 clone()链表的克隆：

克隆链表后把原链表的数据遍历加入

public Object clone() {
  LinkedList<E> clone = superClone();
  // Put clone into "virgin" state
  clone.first = clone.last = null;
  clone.size = 0;
  clone.modCount = 0;
  // Initialize clone with our elements
  for (Node<E> x = first; x != null; x = x.next)
      clone.add(x.item);
   return clone;
}

2.2.2.3 descendingIterator()反向遍历迭代器：

2.2.2.4 remove()：删除元素

遍历查找元素然后将前后两个节点链接起来即可。

2.2.3 关于LinkedList的遍历性能问题

参看这篇文章 http://blog.csdn.net/u010853261/article/details/54143917
不要使用for循环，还是用迭代器吧

2.3Vector

ArrayList的线程安全版本，方法上增加synchronized 实现。

3.fast-fail机制

在AbstractList类中有modCount这么一个字段，扩展类ArrayList、LinkedList以及Vector中 在对自身的元素进行更改时均会modCount++操作；
Thread a,b 两个线程对同一个List实例 listTest通过迭代器迭代（迭代期对象持有一个在自身被创建时listTest的modCount的值），如果a线程进行修改导致了modCount++操作，b线程在的迭代器modCount未进行改变，则b线程迭代会导致 ConcurrentModificationException();而Java并不保证一定能触发，所以还是不要在多线程环境中使用这些实现或者自己在外部提供同步机制

final void checkForComodification() {
  if (modCount != expectedModCount)
     throw new ConcurrentModificationException();
}