容器之路 List解析
1.类图
这里我们主要介绍两个类，分别是ArrayList和LinkedList，这两个类都是List的实现类，下面是简要的类图。
2.ArrayList
ArrayList是我们非常常用的list实现，这个类的底层实际上是使用可以变化长度数组来保存数据，一些操作都是非常简单的，我们主要需要注意的就是可以变化长度这一点的实现方式。
transient Object[] elementData;
transient关键字表示elementData不会被序列化，但是这不表示ArrayList无法序列化，ArrayList使用了自定义的方法来进行序列化，这种做法可能是为了防止大量空的数据被序列化
2.1 初始化
当我们初始化一个ArrayList的时候，实际上就是初始化了一个数组。
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2.2 add方法
在数组中增加元素是十分简单的，这个方法主要需要注意的就是边界检查，判断是否需要动态的增加数组的长度。
类中有变量size用来保存数组中元素的个数，当我们增加一个元素的时候，size的大小需要增加。我们需要判定，增加后的大小是否超出。
这里有两种情况，第一种，数组初始化后第一次插入数据，那么比较默认大小10和传入参数的大小，选择较大的一个。第二种，不是第一插入数据，选择传入参数。
有了确切的应该可以容纳的元素个数后，我们判断目前数组的长度是否大于这个值。如果不大于，那么我们就需要调用方法grow来增加数组的长度。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, intminCapacity) {
//第一次插入数据
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
如果数组长度需要增加，那么，我们会让数组的长度变为原来的1.5倍，然后将原来的数据复制到新数组中。
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);
}
2.3 remove方法
移除方法有两个，一个是移除某个index上的值，一个是移除object。
移除对象的操作我们一般先将移除对象之后的所有元素向前移动，然后将最后一个元素置为null，并将size减1。
另外需要说明的一点是，我们移除一个对象，只会移除list中第一个对象。
2.4 序列化问题
我们在上面提到ArrayList没有使用默认的序列化方法，而是自己实现了序列化方法，下面我们给出方法。
如果一个类需要序列化，那么我们需要让这个类实现接口Serializable。
如果我们不想使用默认的序列化方法，我们可以自己实现下面两个方法。然后，将字段使用transient修饰。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
3.LinkedList
LinkedList的底层是实现是使用双链表，链表中的节点数据结构如下
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即实现了List接口，也实现了Deque接口，实际上Deque接口就是double queue，双端队列。
使用链表的形式，我们可以很方便的移除或者新增一个元素，但是如果我们需要访问某个元素，只能依次遍历。同时，我们也可以使用LinkedList来实现栈或者队列的功能。
LinkedList中有两个指针，分别指向第一个元素和最后一个元素。
transient Node<E> first;
transient Node<E> last;
3.1.增加与删除元素
类中提供了多种方式可以在链表的头部和尾部增加或删除结点，同时也可以在某个index处增加或删除结点。
增加或删除元素时，我们需要注意指向前驱节点以及后继结点的指针的处理。
我们仍需注意的一点时头结点和尾结点的处理。
下图给出的是通用的链表中增加或删除元素的图示，相信大家对这些内容都是十分熟悉的，再次不再赘述。
LinkedList的方便之处在于我们灵活的在首尾增删节点。但是如果我们需要的单纯是一个队列或者栈，我们应该选用ArrayDeque，它效率更高。LinkedList相较ArrayList增删结点等操作需要更为复杂的处理。
4.关于遍历
ArrayList与LinkedList中有两种迭代器，分别是Iterator和ListIterator。
Iterator在遍历过程中不能动态增加list中的元素，但是ListIterator可以增加或修改元素。另外ListIterator不仅可以向后遍历，同时也可以向前遍历，能够灵活的移动，更加方便。
Iterator是一个更为通用的迭代器类，所有集合对象都可以使用。
另外需要注意，在使用迭代器遍历的过程中，不能够直接调用集合的增加修改删除方法，这样会抛出异常，当需要修改时，可以考虑使用迭代器自带的方法进行操作。
public class IteratorTest {
public static void main(String[] args) {
String[] strings = {"aaa", "bbbb", "ccc"};
ArrayList<String> list = new ArrayList<>(Arrays.asList(strings));
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
String tmp = (String) iterator.next();
System.out.println(tmp);
//满足条件remove当前结点
if ("aaa".equals(tmp)) {
iterator.remove();
}
}
Stream.of(list).forEach(System.out::println);
ListIterator listIterator = list.listIterator();
while (listIterator.hasNext()) {
String tmp = (String) listIterator.next();
System.out.println(tmp);
if ("bbbb".equals(tmp)) {
//满足条件，修改结点的值
(listIterator).set("change");
//并且增加结点，在当前结点后面增加
(listIterator).add("dddd");
}
}
Stream.of(list).forEach(System.out::println);
}
}
//输出结果
aaa
bbbb
ccc
[bbbb, ccc]
bbbb
ccc
[change, dddd, ccc]