一、List接口

1.概述

Collection 的子接口，里面的所有内容都是允许重复的。包括null值。
该接口有三个实现类：ArrayList、Vector、LinkedList

2.定义

public interface List extends Collection< E>

3.方法

1. add(int index,E e)、addAll(int index,Collection<? extends E> c)
   对父接口add做了扩充，加入按照索引操作
2. public E get(int index)
   根据索引取出元素
3. indexOf、lastIndexOf
   从前、从后查找指定对象，找不到返回-1
4. public ListIterator listIterator() 、…（int index）
   返回 ListIterator 接口实例化、从指定位置的 ListIterator 接口的实例
5. remove(int index)
   移除指定位置的元素
6. set(int index,E e)
   设置指定位置的内容
7. List subList(int fromIndex,int toIndex)
   返回子集合

二、ArrayList

1.概述

• 可调整大小的集合，允许重复，包括null
• 使用的是数组结构，底层用Object[] elementData来存储，对于增加删除快，查找慢
• 线程不安全的
• java.lang.Object
  • java.util.AbstractCollection
    • java.util.AbstractList
      • java.util.ArrayList

2.构造方法

1. ArrayList()
   构造初始容量为10的空列表
2. public ArrayList(int initialCapacity)
   构造具有指定初始容量的空列表
3. public ArrayList(Collection<? extends E> c)
   按照集合的迭代器返回的顺序构造一个包含指定集合元素的列表

3.方法

适用所有的List的方法，除此之外，还有以下：

• trimToSize()
  将此 ArrayList实例的容量调整为列表的当前大小。
• forEach
  对 Iterable每个元素执行给定操作，直到处理 Iterable所有元素或操作引发异常
• ensureCapacity​(int minCapacity)
  如有必要，增加此 ArrayList实例的容量，以确保它至少可以容纳由minimum capacity参数指定的元素数

4.扩容机制

  首先，ArrayList类提供以下几个属性：
（DEFAULT_CAPACITY = 10，EMPTY_ELEMENTDATA = {}，DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}，elementData，size，MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8）

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{private static final long serialVersionUID = 8683452581122892189L;private static final int DEFAULT_CAPACITY = 10;//默认的初始容量private static final Object[] EMPTY_ELEMENTDATA = {};//空数组private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//默认容量的空数组transient Object[] elementData; //实际存储元素的数组private int size;//列表中有效值大小private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//最大数组大小为Integer最大值-8......}

  其实，当我们使用空参构造器创建ArrayList对象时，它的容量并不是10，而是0。当然我们使用带参构造器创建时，容量便是指定的大小。那为什么我们常说ArrayList初始容量是10?

  public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

我们知道， DEFAULTCAPACITY_EMPTY_ELEMENTDATA是空数组，所以构造方法并没有对容量初始化，那么就按照 DEFAULTCAPACITY_EMPTY_ELEMENTDATA大小（0）来作为开始容量。
  初始化容量是在我们第一次add操作时发生的，有效长度如果等于当前数组长度，那么表示列表已满，此时需要调用grow()方法来扩容，反之，将元素e赋值给size的位置，有效长度size+1。
  1. grow（）方法是用来扩容的，它假定以size+1作为最小需要的容量大小minCapacity去调用newCapacity()来计算新的容量newCapacity来复制数组，并赋值给elementData；
2. newCapacity（）方法里先 newCapacity = oldCapacity + (oldCapacity >> 1);表示新的容量为旧容量+旧容量的一半，即原容量*1.5
3. 接下来，判断新容量是否小于最小容量，即新容量不够存或者minCapacity越界情况。newCapacity小于等于minCapacity两种情况：
 a. 原数组为默认空数组，原来容量为0，那么newCapacity就为0，minCapacity为1，这种情况就返回 默认容量DEFAULT_CAPACITY与最小容量的最大值作为新容量；
 b.minCapacity过大，overflow情况，那么就抛出OutOfMemoryError异常;
如果不是以上两种情况，那么最后返回minCapacity为新的容量。
4. 如果newCapacity不小于minCapacity，那么将newCapacity跟MAX_ARRAY_SIZE比较，MAX_ARRAY_SIZE 值为Integer.MAX_VALUE - 8，如果新容量小于等于MAX_ARRAY_SIZE ，那么就返回这个newCapacity，否则，newCapacity可能过大，也就是说minCapacity可能会越界overflow，也可能在MAX_ARRAY_SIZE和Integer.MAX_VALUE 之间，调用hugeCapacity（minCapacity）去判断，如果minCapacity小于0，则minCapacity过大越界，抛出OutOfMemoryError异常；然后如果minCapacity大于MAX_ARRAY_SIZE，表示minCapacity在MAX_ARRAY_SIZE和Integer.MAX_VALUE 之间，那么就返回Integer最大值即可，反之，返回MAX_ARRAY_SIZE。

    private void add(E e, Object[] elementData, int s) {if (s == elementData.length)elementData = grow();elementData[s] = e;size = s + 1;}private Object[] grow() {return grow(size + 1);//假定原size+1作为最小需要的容量}private Object[] grow(int minCapacity) {return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));//以新容量大小来复制elementData数组}private int newCapacity(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//旧的容量int newCapacity = oldCapacity + (oldCapacity >> 1);//新的容量为旧容量+旧容量的一半，即原容量*1.5if (newCapacity - minCapacity <= 0) {//判断新容量小于最小容量，即新容量不够存情况if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)//原数组为默认空数组，原来容量为0，那么newCapacity就为0，minCapacity为1return Math.max(DEFAULT_CAPACITY, minCapacity);//返回默认容量DEFAULT_CAPACITY与最小容量的最大值作为新容量if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return minCapacity;}return (newCapacity - MAX_ARRAY_SIZE <= 0)//新容量小于等于数组最大容量? newCapacity: hugeCapacity(minCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE)? Integer.MAX_VALUE: MAX_ARRAY_SIZE;}

  除此之外，ArrayList还有缩容机制，trimToSize方法，它主要调整当前列表容量为有效内容大小。

 public void trimToSize() {modCount++;if (size < elementData.length) {elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}}

先比较size跟elementData.length大小，有必要缩容再进行，如果size有效值为0，那么直接让数组elementData赋值为EMPTY_ELEMENTDATA，反之将原数组复制size长度内容给原数组。

三、Vector

1.概述

• 可调整大小的集合，允许重复，包括null
• 线程安全的
• Vector 属于 Java 元老级的操作类，是最早的提供了动态对象数组的操作类，在 JDK 1.0 的时候就已经推出了此
  类的使用，只是后来在 JDK 1.2 之后引入了 Java 类集合框架。但是为了照顾很多已经习惯于使用 Vector 的用户，所以在JDK 1.2 之后将 Vector 类进行了升级了，让其多实现了一个 List 接口，这样才将这个类继续保留了下来。

2.构造方法

1. Vector()
   构造一个空向量，使其内部数据数组的大小为 10 ，其标准容量增量为零
2. Vector​(int initialCapacity)
   构造一个具有指定初始容量且容量增量等于零的空向量
3. Vector​(int initialCapacity, int capacityIncrement)
   构造具有指定初始容量和容量增量的空向量
4. Vector​(Collection<? extends E> c)
   按照集合的迭代器返回的顺序构造一个包含指定集合元素的向量。

3.方法

操作与ArrayList基本类似

4.扩容机制

  初始容量为10，默认增量为0,初始化Vector时，就会默认10的容量给数组，如果未指定capacityIncrement，那么它默认为0。
  扩容也是发生在add方法时，如果已满，则调用grow，传入当前容量+1为参数作为minCapacity，调用newCapacity方法确定newCapacity值，newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);，意思是当指定了增量capacityIncrement，则oldCapacity+capacityIncrement作为newCapacity，之后处理如同ArrayList机制一样。
内部属性：elementData,elementCount,capacityIncrement;

public class Vector<E>extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{protected Object[] elementData;//存储元素的数组protected int elementCount;//实际有效大小protected int capacityIncrement;//增量，默认为0
.....
}

扩容代码：

    private Object[] grow() {return grow(elementCount + 1);}private Object[] grow(int minCapacity) {return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));}private int newCapacity(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);if (newCapacity - minCapacity <= 0) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return minCapacity;}return (newCapacity - MAX_ARRAY_SIZE <= 0)? newCapacity: hugeCapacity(minCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

ArrayList跟Vector区别

• 时间
  Vector在jdk1.0就定义了
  ArrayList在Jdk1.2才开始出现
• 性能
  Vector采用同步处理，线程安全
  ArrayList采用异步处理，线程不安全，效率高
• 输出
  Vector支持Iterator、listIterator、Enumeration
  ArrayList支持Iterator和listIterator

四、LinkedList

1.概述

• 双链表实现了List和Deque接口。 实现所有可选列表操作，并允许所有元素（包括null ）。
• 可调整大小的集合，允许重复，包括null
• 线程不安全的

2.构造方法

1. LinkedList()
2. LinkedList​(Collection<? extends E> c)
   按照集合的迭代器返回的顺序构造一个包含指定集合元素的列表。

3.特有方法

1. add
   addFirst​(E e)
    在此列表的开头插入指定的元素。
   addLast​(E e)
    将指定的元素追加到此列表的末尾。
2. get
   getFirst()
    返回此列表中的第一个元素。
   getLast()
    返回此列表中的最后一个元素。
3. remove
   removeFirst()
    删除并返回第一个元素
   removeLast()
    删除并返回最后一个元素
   removeFirstOccurrence​(Object o)
    删除此列表中第一次出现的指定元素（从头到尾遍历列表时）。
   removeLastOccurrence​(Object o)
    删除此列表中最后一次出现的指定元素（从头到尾遍历列表时）。
4. 模拟队列
   4-1.offer​(E e)
    将指定的元素添加为此列表的尾部（最后一个元素）。
    offerFirst​(E e)
     在此列表的前面插入指定的元素
    offerLast​(E e)
     在此列表的末尾插入指定的元素
   4-2.poll()
    检索并删除此列表的头部（第一个元素）。
    pollFirst()
     检索并删除此列表的第一个元素，如果此列表为空，则返回 null 。
    pollLast()
     检索并删除此列表的最后一个元素，如果此列表为空，则返回 null 。
   4-3. peek()
    检索但不删除此列表的头部（第一个元素）。
    peekFirst()
     检索但不删除此列表的第一个元素，如果此列表为空，则返回 null
    peekLast()
    检索但不删除此列表的最后一个元素，如果此列表为空，则返回 null
5. 模拟栈
   5-1.pop()
    弹出此列表所代表的堆栈中的元素
   5-2. push​(E e)
    将元素推送到此列表所表示的堆栈上。

总结

  在 List 接口中有以上 10 个方法是对已有的 Collection 接口进行的扩充。
  所以，证明，List 接口拥有比 Collection 接口更多的操作方法。
了解了 List 接口之后，那么该如何使用该接口呢？需要找到此接口的实现类，常用的实现类有如下几个：
·   ArrayList（95%）、Vector（4%）、LinkedList（1%）
重点掌握ArrayList。

转载注明来源。