ArrayList

ArrayList本质上是一个动态数组，它与数组的区别主要就是：不需要提前给定确切的长度，并且可以动态扩容，比数组更加灵活。

一、常用方法

方法	含义
.add(Object element)	添加元素value
.add(int index, Object element)	在指定下标位置index添加元素value
.size()	返回元素个数，即 ArrayList 长度
.get(int index)	获取下标为index的值
.set(int index, Object element)	替换下标index的值为element，并返回原来的元素值
.isEmpty()	判断是否为空。空，则返回true，否则返回false
.contains(Object element)	是否包含元素element。存在，返回true，否则，返回false
.remove(int index)	删除下标index的元素，并返回该元素
.remove(Object element)	删除第一次出现element的元素，移除成功，返回true；否则，返回false

二、源码

参数

// Default initial capacity. 初始化容量大小
private static final int DEFAULT_CAPACITY = 10;
// Shared empty array instance used for empty instances. 用于空实例的共享空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 共享空数组实例，与 EMPTY_ELEMENTDATA 区分开
// 目的是为了观看添加第一个元素时需要扩大多少容量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 真正数据对象存储的地方，不参与序列化
transient Object[] elementData; // non-private to simplify nested class access
// 列表的容量大小
private int size;

构造函数

// 创建容量大小为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);}
}// 创建空列表
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}// 将集合Collection的元素copy到列表中，并更新size值
public ArrayList(Collection<? extends E> c) {elementData = c.toArray();// 如果size长度不为0if ((size = elementData.length) != 0) {if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// 长度为0，则赋值为空{}this.elementData = EMPTY_ELEMENTDATA;}
}

添加add

1. 每次添加先确定是否会出现越界
2. 第一次添加元素后，ArrayList的容量变为默认的初始值10
3. 而后每一次扩容 = 原有容量*1.5 （代码中表示为oldCapacity + oldCapacity >> 1）
4. 列表满时，将所有数据重新装入一个新的列表，比较耗时

// 添加元素e
public boolean add(E e) {// 确保添加元素后的容量：size + 1 不会越界// 扩容，添加元素ensureCapacityInternal(size + 1);  elementData[size++] = e;return true;
}private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// DEFAULT_CAPACITY 初始值为10// 第一次添加元素后，minCapacity 值变为10minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);
}private void ensureExplicitCapacity(int minCapacity) {modCount++;// 动态扩容if (minCapacity - elementData.length > 0)grow(minCapacity);
}private void grow(int minCapacity) {
// 动态获取新的容量大小，并更改elementData列表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);
}

// 在下标为index处添加元素element
public void add(int index, E element) {// 确保index没有越界rangeCheckForAdd(index);// 扩容ensureCapacityInternal(size + 1);  // 空出原数组index位置System.arraycopy(elementData, index, elementData, index + 1, size - index);// 添加元素elementData[index] = element;size++;
}private void rangeCheckForAdd(int index) {if (index > size || index < 0)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

获取get

public E get(int index) {rangeCheck(index);// 返回下标为index的元素return elementData(index);
}// 确保index没有越界
private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

替换set

public E set(int index, E element) {rangeCheck(index);	// index不越界E oldValue = elementData(index);elementData[index] = element;// 返回旧值return oldValue;
}

是否包含contains

public boolean contains(Object o) {return indexOf(o) >= 0;
}

三、FailFast机制

源码中有modCount++;，如果有两个线程操作同一个ArrayList，可能会导致modCount不一致，而出现并发问题。因此，提出FailFast快速失败机制，以保证集合迭代过程中会出现的并发问题而对内部结构的一种防护措施，会抛出异常 java.util.ConcurrentModificationException。

---

LinkedList

LinkedList本质是双向链表，查找效率没有ArrayList高，但是删除、插入效率高，因为LinkedList不需要移动元素。

一、常用方法

方法	含义
.size()	返回元素个数，即 LinkedList 长度
.add(Object element)	添加元素element （队列压入）
.addFirst(Object element)	添加元素element到列表头部
.addLast(Object element)	添加元素element到列表尾部
.get(int index)	获取下标为index的值
.getFirst(int index)	获取列表第一个值
.getLast(int index)	获取列表最后一个值
.set(int index, Object element)	替换下标index的值为element，并返回原来的元素值
.remove(int index)	删除下标index的元素，并返回该元素
.remove(Object element)	删除第一次出现element的元素，移除成功，返回true；否则，返回false
.removeFirst(int index)	删除并返回第一个元素
.removeLast(Object element)	删除并返回最后一个元素
.isEmpty()	判断是否为空。空，则返回true，否则返回false
.contains(Object element)	是否包含元素element。存在，返回true，否则，返回false
.push(Object element)	元素element压入堆栈
.pop()	弹出堆栈
.peek()	获取堆栈首部元素
.poll()	队列首弹出第一个元素

二、源码

Node类

链表中的节点类，包含prev指向前一个的指针、next指向后一个的指针、item元素值

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、push

add与push的不同
add方法进行尾插，而push是头插，push往往用于堆栈的实现。

1. add

   public boolean add(E e) {// linkLast 在列表尾部添加linkLast(e);return true;
   }// linkLast 在列表尾部添加
   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++;
   }
   

2. push

   public void push(E e) {addFirst(e);
   }public void addFirst(E e) {linkFirst(e);
   }private void linkFirst(E e) {final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);first = newNode;if (f == null)last = newNode;elsef.prev = newNode;size++;modCount++;
   }
   

获取get

通过二分法查找以降低耗时。本质上还是遍历。
如果index小于size/2，则从头部开始查找；反之，大于size/2，则从尾部开始查找

public E get(int index) {// 确保index不越界checkElementIndex(index);return node(index).item;
}Node<E> node(int index) {// get获取方法的核心// 通过二分法查找以降低耗时。// 如果index小于size/2，则从头部开始查找// 反之，大于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;}
}private void checkElementIndex(int index) {if (!isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

---

Vector

Vector类似于ArrayList，也是动态数组。但其已经过时，因为Vector里的每一个操作方法都是同步的，非常的耗时（Vector是线程安全的）。

比方如下所示的Vector的add方法，与ArrayList相似，但它用synchronized来修饰。Vector的很多操作方法都被synchronized修饰。

public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;
}

小总结

1. 通过以上学习可以知道ArrayList、LinkedList是线程不安全的，而Vector线程安全。但是由于Vector大量使用synchronized方法，导致性能很低，所以Vector不推荐使用。

   在需要对列表处理同步问题时，可以通过集合工具类Collections将线程不安全的列表转化为线程安全的。List syncList = Collections.synchronizedList(list); 该工具类的方法本质上就是给列表的操作加上同步代码块使之变为线程安全的。

2. 使用LinkedList可以实现栈、队列的数据结构

   栈的实现

   Stack<Integer> stack = new Stack<>();
   stack.push(3);
   int var = stack.pop();
   

   队列的实现

   Queue<Integer> queue = new LinkedList<>();
   queue.add(3);
   int var = queue.poll();