List接口：
● 这里我用的JDK8
● List集合代表一个有序集合，集合中每个元素都有其对应的顺序索引，它继承Collection接口，可以定义一个允许重复的有序集合
● List接口的特点：
1、有索引（下标）
2、有顺序
3、能重复
● 实现List接口的集合有：
○ ArrayList、LinkedList、Vector、Stack
ArraList和linkedList：
相同点：
- 都是List的子类。
- 允许空值
区别：
ArrayList:实现了长度可变的数组
数据结构：物理结构是紧密结构，逻辑结构是线性表（数组）
1. 内部是数组结构实现
2. 数据的插入和删除都需要对数组复制和重排序（删除和插入比较慢）
3. 有序可以重复
4. 插入和删除需要大量移动元素效率低，比较慢
5. 查找效率高：遍历元素和随机访问元素的效率比较高
6.线程不安全
LinkList:底层实现是双向链表存储对象
数据结构：物理结构是跳转结构，逻辑结构是线性表（链表）
1. 双向链表结构，对每一个元素都有指向前后元素的指针
2. 顺序读取效率比较高，随机读取元素效率比较低
3. 删除、插入效率高
4. 查询比较慢
ArrayList：
ArrayList实现了List接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。除该类未实现同步外，其余跟Vector大致相同。每个ArrayList都有一个容量(capacity)，表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。前面已经提过，Java泛型只是编译器提供的语法糖，所以这里的数组是一个Object数组，以便能够容纳任何类型的对象。
size(), isEmpty(), get(), set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。
为追求效率，ArrayList没有实现同步(synchronized)，如果需要多个线程并发访问，用户可以手动同步，也可使用Vector替代。
● 实现了List接口，也是最常用的一种集合
● 特点：底层数据结构是数组，查询快，增加删除慢，线程不安全，效率高
● 优点：读取效率高，底层是基于数组实现的，可以为null值，可以允许重复元素、元素有序；
● 缺点：由于它是底层是动态数组实现的，不适合频繁的对元素的进行插入和删除操作，因为每次插入和删除都需 要移动数组中的元素，操作慢且复杂。
● 最佳实践： 在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。
添加和删除效率较低，查询效率高的原因：
添加动态扩容和删除都需要移位复制，效率较低，
添加元素时，尤其是当数据量较大的时候，每次扩容消耗的时间会越来越多
可以预估指定集合大小，减少扩容次数，提高写入的效率
查询是随机访问，效率高
为什么可以随机访问？
由于ArrayList底层结构是数组，所以它占据了一块连续的内存空间且存储都是相同类型的元素，每个元素的大小相等，可以通过下标来计算出元素位置，可以快速定位
ArrayList的实现：
底层数据结构：
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
底层的数组， 数组类型是Object类型
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
* 数组中有效的数据
* @serial
*/
private int size;
构造函数:
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
自动扩容
每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。
数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
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;
}
添加元素add(), addAll()：
这两个方法都是向容器中添加新元素，这可能会导致capacity不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过grow()方法完成的。
add(int index, E e)需要先对元素进行移动，然后完成插入操作，也就意味着该方法有着线性的时间复杂度。
addAll()方法能够一次添加多个元素，根据位置不同也有两个版本，一个是在末尾添加的addAll(Collection<? extends E> c)方法，一个是从指定位置开始插入的addAll(int index, Collection<? extends E> c)方法。跟add()方法类似，在插入之前也需要进行空间检查，如果需要则自动扩容；如果从指定位置插入，也会存在移动元素的情况。 addAll()的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关。
添加元素----数组超出长度按1.5倍扩容-----数组拷贝复制-----引用指向新数组
不指定ArrayList容器大小时，创建初始容器的长度为0，第一次添加元素时，新数组默认为10
扩容机制
ArrayList添加元素时，当数组长度没有空余位置的时候需要进行扩容，扩容新数组长度为原来的数组的1.5倍, 然后使用拷贝的新数组替代原数组（数组引用指向新的数组）, 这样也就实现在动态调整数组长度;
添加删除元素可能慢的原因：
由于它是底层是动态数组实现的，不适合频繁的对元素的进行插入和删除操作，因为每次插入和删除都需 要移动数组中的元素，操作慢且复杂。
当添加需要大量元素，效率低
ArrayList的添加和删除是通过移位复制，并且是系统本地方法（arrayCopy C++ 代码实现），删除会遍历所有的元素，不确定性很大。所以在删除和添加操作是比较慢的
add(index,element)
public void add(int index, E element) {
// 比对下标和数据长度或者下标小于0，否则抛出数据下标越界
rangeCheckForAdd(index);
//DEFAULT_CAPACITY = 10 默认的容量是 10 ，最小值和默认参数对比（取最大的那个作为最小容量）
ensureCapacityInternal(size + 1); // Increments modCount!!
//移位复制 arraycopy，将 index 的位置空出去，本地方法C/c++写的。
System.arraycopy(elementData, index, elementData, index + 1,size - index);
//添加index元素
elementData[index] = element;
//数组长度自增
size++;
}
//10容量
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
//对比是否需要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//计算容量
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//拷贝复制，指向新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
add(E e)
public boolean add(E e) {
//自增容量，跟前面的指定位置存放是一样的
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
删除元素remove()：
remove()方法也有两个版本，一个是remove(int index)删除指定位置的元素，另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()操作的逆过程，需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用，必须显式的为最后一个位置赋null值。
关于Java GC这里需要特别说明一下，有了垃圾收集器并不意味着一定不会有内存泄漏。对象能否被GC的依据是是否还有引用指向它，上面代码中如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。
删除元素需要遍历所有的元素和移位复制到新数组，不确定性大，效率低
比如删除下标3的元素
原数组：elementData
从哪开始复制：index+1 = 4
目标数组：elementData
复制起始位置：index =3
长度： size - index - 1=6
remove（Object / index）
public E remove(int index) {
//第一步先判断是否有越界，如果越界直接IndexOutOfBoundsException
rangeCheck(index);
modCount++;
//把该元素从数组中提出
E oldValue = elementData(index);
//需要复制的长度
int numMoved = size - index - 1;
if (numMoved > 0)
//原数组，从哪开始复制，目标数组，复制起始位置，长度。过程如下图：
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//赋值null等待回收
elementData[--size] = null;
return oldValue;
}
//返回是否删除
public boolean remove(Object o) {
if (o == null) {
/**
* 当是null的时候
*/
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
//并非null的时候，是在全数组的方式遍历获取在删除的。
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
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
}
Fail-Fast机制:
ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
多线程场景使用 ArrayList
ArrayList 不是线程安全的
线程不安全的两种体现：
1 数组越界异常 ArrayIndexOutOfBoundsException
由于ArrayList添加元素是如上面分两步进行，可以看出第一个不安全的隐患，在多个线程进行add操作时可能会导致elementData数组越界。
具体逻辑如下：
列表大小为9，即size=9
线程A开始进入add方法，这时它获取到size的值为9，调用ensureCapacityInternal方法进行容量判断。
线程B此时也进入add方法，它获取到size的值也为9，也开始调用ensureCapacityInternal方法。
线程A发现需求大小为10，而elementData的大小就为10，可以容纳。于是它不再扩容，返回。
线程B也发现需求大小为10，也可以容纳，返回。
线程A开始进行设置值操作， elementData[size++] = e 操作。此时size变为10。
线程B也开始进行设置值操作，它尝试设置elementData[10] = e，而elementData没有进行过扩容，它的下标最大为9。于是此时会报出一个数组越界的异常ArrayIndexOutOfBoundsException.
2 元素值覆盖和为空问题
elementData[size++] = e 设置值的操作同样会导致线程不安全。从这儿可以看出，这步操作也不是一个原子操作，它由如下两步操作构成：
● elementData[size] = e;
● size = size + 1;
在单线程执行这两条代码时没有任何问题，但是当多线程环境下执行时，可能就会发生一个线程的值覆盖另一个线程添加的值，具体逻辑如下：
列表大小为0，即size=0
线程A开始添加一个元素，值为A。此时它执行第一条操作，将A放在了elementData下标为0的位置上。
接着线程B刚好也要开始添加一个值为B的元素，且走到了第一步操作。此时线程B获取到size的值依然为0，于是它将B也放在了elementData下标为0的位置上。
线程A开始将size的值增加为1
线程B开始将size的值增加为2
这样线程AB执行完毕后，理想中情况为size为2，elementData下标0的位置为A，下标1的位置为B。而实际情况变成了size为2，elementData下标为0的位置变成了B，下标1的位置上什么都没有。并且后续除非使用set方法修改此位置的值，否则将一直为null，因为size为2，添加元素时会从下标为2的位置上开始。
ArrayList线程安全处理：
**1.Collections.synchronizedList（常用）**
最常用的方法是通过 Collections 的 synchronizedList 方法将 ArrayList 转换成线程安全的容器后再使用。
List list =Collections.synchronizedList(new ArrayList);
2.为list.add()方法加锁
synchronized(list.get()) {list.get().add(model);}
**3.CopyOnWriteArrayList**
使用线程安全的 CopyOnWriteArrayList 代替线程不安全的 ArrayList。
List list1 = new CopyOnWriteArrayList();
4.使用ThreadLocal
使用ThreadLocal变量确保线程封闭性(封闭线程往往是比较安全的， 但由于使用ThreadLocal封装变量，相当于把变量丢进执行线程中去，每new一个新的线程，变量也会new一次，一定程度上会造成性能[内存]损耗，但其执行完毕就销毁的机制使得ThreadLocal变成比较优化的并发解决方案)。