List集合及其实现类的相关内容

集合类是Java数据结构的实现。Java的集合类是java.util包中的重要内容，它允许以各种方式将元素分组，并定义了各种使这些元素更容易操作的方法。Java集合类是Java将一些基本的和使用频率极高的基础类进行封装和增强后再以一个类的形式提供。集合类是可以往里面保存多个对象的类，存放的是对象，不同的集合类有不同的功能和特点，适合不同的场合，用以解决一些实际问题。

Java中的集合类可以分为两大类：一类是实现Collection接口；另一类是实现Map接口。
Collection是一个基本的集合接口，Collection中可以容纳一组集合元素（Element）。
Map没有继承Collection接口，与Collection是并列关系。Map提供键（key）到值（value）的映射。一个Map中不能包含相同的键，每个键只能映射一个值。
Collection有两个重要的子接口List和Set。List表达一个有序的集合，List中的每个元素都有索引，使用此接口能够准确的控制每个元素插入的位置。用户也能够使用索引来访问List中的元素，List类似于Java的数组。Set接口的特点是不能包含重复的元素。对Set中任意的两个元素element1和element2都有elementl.equals（element2）= false。另外，Set最多有一个null元素。此接口模仿了数学上的集合概念。

Collection接口、List接口、Set接口以及相关类的关系如下图所示。

List的实现类有：ArrayList，Vector，linkedList类。

ArrayList：作为List接口的主要实现类；线程不安全的，效率高；底层使用Object[] elementData存储

linkedList：对于频繁的插入和删除操作，使用此类效率比ArrayList高；底层使用双向链表存储

Vector：作为List接口的古老实现类：线程安全的，执行效率低；底层使用Object[] elementData存储

ArrayList list = new ArrayList();//底层创建了长度是10的Object[]数组elementData
list.add(123);//elementData[0] = new Integer(123);
list.add(11);

结论：建议开发中使用带参的构造器：ArrayList list = new ArrayList(int capacity)

ArrayList list = new ArrayList();//底层Object[] elementData初始化为{}，并没有创建长度为10的数组
list.add(123);

后续的添加和扩容操作与jdk 7 无异。

jdk 7中ArrayList的对象的创建类似于单例模式的饿汉式，而jdk 8中的ArrayList的对象的创建类似于单例的懒汉式，延迟了数组的创建，节省空间。

	linkedList list = new linkedList();//内部声明了Node类型的first和last属性，默认值为null。
	list.add(123);//将123封装到Node中，创建了Node对象。

其中，Node定义为：体现了linkedList的双向链表的说法

private static class Node{
   E item;
   Node next;
   Node prev;

   Node(Node prev,E element,Node next){
   		this.item = element;
		this.next = next;
		this.prev = prev;
	}      
}

linkedLis是实现了基于双链表的数据结构，在插入、删除集合中任何位置的元素所花费的时间都是一样的，但它在索引一个元素的时候比较慢。

private void grow(int minCapacity) {
	
	// 获取数组的真实容量（实际存放成员的个数）
	int oldCapacity = elementData.length;
	
	// 由于capacityIncrement = 0 ，因此newCapacity = oldCapacity + oldCapacity
	int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
									 capacityIncrement : oldCapacity);
	if (newCapacity - minCapacity < 0)
		newCapacity = minCapacity;
	if (newCapacity - MAX_ARRAY_SIZE > 0)
		newCapacity = hugeCapacity(minCapacity);
	// 将数组容量扩容至原来的2倍，并保留原数据
	elementData = Arrays.copyOf(elementData, newCapacity);
}

jdk7和jdk8中通过Vector()构造器创建对象时，底层都创建了长度为10的数组，在扩容方面，默认扩容为原来数组长度的二倍。所以在一般情况下我们可以把Vector当做线程安全的ArrarList使用，每次扩容增大一倍容量，效率低于ArrayList。