List概述
List汇合的元素以线性形式存储
1.能够容许反复的对象。
2.能够插入多个null元素。
3.是一个有序汇合，放弃了每个元素的插入程序，输入的程序就是插入的程序。
List实现类
ArrayList
ArrayList底层是用数组实现的存储，Object[] elementData
查问效率高，增删效率低，线程不平安
ArrayList()提供了三种构造方法。
ArrayList()：结构一个初始容量为10的空列表。
/** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }ArrayList(int initialCapacity)：结构具备指定初始容量的空列表。
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); } }ArrayList(Collection c)：结构一个蕴含指定汇合的元素的列表，依照它们由汇合的迭代器返回的程序。
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; } }ArrayList要害源码解析
add()办法
public boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; // 如果minCapacity大于elementData的长度，则进行扩容解决 if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { int oldCapacity = elementData.length; //容量默认扩充1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) //数组容量存在最大值 newCapacity = hugeCapacity(minCapacity); //数组复制 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; } - int newCapacity = oldCapacity + (oldCapacity >> 1);每次扩容是原数组的1.5倍
- elementData = Arrays.copyOf(elementData, newCapacity);创立一个长度是原数组容量1.5倍的新的数组，将原数组的数据复制到新数组中，elementData指向新的数组地址
- 扩容也是无限的，存在最大值Integer.MAX_VALUE，然而在某些虚拟机上数组容量达到MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8时会内存溢出
4.最重要的一个点：如果咱们能够当时预计出数据量，那么最好给ArrayList一个初始值，这样能够缩小其扩容次数，从而省掉很屡次内存申请和数据搬移操作。（不指定初始值，至多会执行一次grow办法，用于初始化外部数组）。
remove()办法
public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); 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 return oldValue; }System.arraycopy(elementData, index+1, elementData, index,numMoved);复制一个index+1开始到最初的数组，而后把它放到index开始的地位
ArrayList为什么是线程不平安的
add()办法是非原子操作
1.多个线程进行add操作时可能会导致elementData数组越界
2.多线程环境下执行时，可能就会产生一个线程的值笼罩另一个线程增加的值
Vector
在ArrayList的所有办法加了synchronized关键字，线程平安。
LinkedList
ArrayList底层是用双向链表实现的存储，
查问效率低，增删效率高，线程不平安
Node节点：
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; } }LinkedList有一个空参构造函数和一个汇合参数构造函数：
public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); }LinkedList要害源码解析
get()办法：
public E get(int index) { checkElementIndex(index); return node(index).item; } Node<E> node(int index) { // assert isElementIndex(index); //查找地位 index 如果小于节点数量的一半(size>>1示意把size右移1位，相当于size/2)则从头节点开始查找，否则从尾节点查找 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }LinkedList为什么是线程不平安的
add()办法是非原子操作
多个线程进行add操作时可能会节点笼罩
Stack
Stack 继承自Vector，底层也是用数组实现的存储，线程平安，恪守 LIFO（后进先出）的操作程序
Stack要害源码解析
//入栈，增加一个元素到数组开端 public E push(E item) { addElement(item); return item; } //出栈，删除数组最初一个元素并返回 public synchronized E pop() { E obj; int len = size(); obj = peek(); removeElementAt(len - 1); return obj; } //获取最初一个元素，不删除 public synchronized E peek() { int len = size(); if (len == 0) throw new EmptyStackException(); return elementAt(len - 1); }参考：
一篇文章带您读懂List汇合（源码剖析）