作为集合，也叫做容器。底层必须有一个数据结构做基础。常用的数据结构 数组，链表，树（红黑树）。

List

list集合特点：有序 即：数据插入的顺序与遍历的顺序是一致的。

ArrayList

 public boolean add(E e) {//每次add数据之前需要确保集合中有足够的容量存放ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}

private void ensureCapacityInternal(int minCapacity) {//在使用无参构造器时才会给一个初始容量10 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}//每次add之前都会判断是否达到了扩容的要求，因为list中没有阈值的概念ensureExplicitCapacity(minCapacity);}

private void ensureExplicitCapacity(int minCapacity) {
//记录add的次数，该值与迭代器有关系modCount++;// overflow-conscious code//如果新数据插入会大于现有数组的长度就需要扩容，否则不需要if (minCapacity - elementData.length > 0)grow(minCapacity);}

private void grow(int minCapacity) {// overflow-conscious codeint 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);// minCapacity is usually close to size, so this is a win:	//扩容以后需要把数据进行迁移，使用了数组复制api，所以Arraylist的瓶颈就是在大量数据的扩容	elementData = Arrays.copyOf(elementData, newCapacity);}

get

public E get(int index) {//校验下标的合法性rangeCheck(index);return elementData(index);}

 private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}

 E elementData(int index) {// 根据下标在数组中找到对应的值放回return (E) elementData[index];}

iterator,ArrayList中维护了一个Itr的内部类，遍历内部的数组需要注意就是在遍历list时不能在往list中add数据，否则就会报异常。

 private class Itr implements Iterator<E> {int cursor;       // index of next element to returnint lastRet = -1; // index of last element returned; -1 if no such//这个变量只会在遍历之前赋值int expectedModCount = modCount;public boolean hasNext() {return cursor != size;}@SuppressWarnings("unchecked")public E next() {checkForComodification();int i = cursor;if (i >= size)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length)throw new ConcurrentModificationException();cursor = i + 1;return (E) elementData[lastRet = i];}

  final void checkForComodification() {//每便利一次就会检验modCount != expectedModCount，而在此时如果有add操作，就会使modCount++ ，导致两个变量值不一样报错if (modCount != expectedModCount)throw new ConcurrentModificationException();}

同时list还支持添加一个集合

 public boolean addAll(Collection<? extends E> c) {//将要添加的集合变成一个数组Object[] a = c.toArray();int numNew = a.length;//扩容ensureCapacityInternal(size + numNew);  // Increments modCount//复制数组System.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;}

LinkedList

该集合底层时一个链表（双向链表）的结构。并且是无界的，可以一直添加节点。每一个节点都是一个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;}}

add 方法 默认是在链表末添加

 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;elsel.next = newNode;size++;modCount++;}

get

 public E get(int index) {checkElementIndex(index);return node(index).item;}

private void checkElementIndex(int index) {if (!isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}

Node<E> node(int index) {
//在获取node时，为了提高效率通常会分前后两部分查找// assert isElementIndex(index);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;}}

迭代器，此迭代器通常会方便不少。

private class ListItr implements ListIterator<E> {private Node<E> lastReturned;private Node<E> next;private int nextIndex;private int expectedModCount = modCount;ListItr(int index) {// assert isPositionIndex(index);next = (index == size) ? null : node(index);nextIndex = index;}public boolean hasNext() {return nextIndex < size;}public E next() {checkForComodification();if (!hasNext())throw new NoSuchElementException();lastReturned = next;next = next.next;nextIndex++;return lastReturned.item;}

CopyOnWriteArrayList 线程安全，读写分离

此集合是基于数组实现，最大的特点就是线程安全，在读多写少的情况下使用。效果更好

 public boolean add(E e) {//添加lock锁，保证线程安全final ReentrantLock lock = this.lock;lock.lock();try {//在操作之前先获得一个数据副本，操作副本。 不影响读操作Object[] elements = getArray();int len = elements.length;Object[] newElements = Arrays.copyOf(elements, len + 1);newElements[len] = e;//将副本替换原数据setArray(newElements);return true;} finally {lock.unlock();}}

final Object[] getArray() {return array;}

final void setArray(Object[] a) {array = a;}

get

public E get(int index) {return get(getArray(), index);}

private E get(Object[] a, int index) {return (E) a[index];}

此集合虽然可以线程安全（写操作加锁），但是也会副本也会消耗也写内存，并且也存在数据的一致性。