UML
列表底层的数据结构
Java中的列表都是可以动态伸缩的。跟数组不一样，数组超过了一定的长度，会直接报越界异常。
其次，列表的特点就是有序性，插入其中的元素，都是有序的。比如往[1,2,3]的队列中插入4，那么得到的列表就是[1,2,3,4].
为此，我们来回顾一下数据结构.
数组-ArrayList
数组扩容的过程
先来看看构造函数:
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);
}
}
如果传入一个初始的长度，那么创建一个长度为initialCapacity的数组.
那么ArrayList是怎么做动态扩容的呢，答案在add()里面.
- java.util.ArrayList#add(E)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
往列表添加元素的时候，先确保列表的内置因子是足够大小的，如果超出了一定的长度，需要进行扩容，随后对当前的size+1索引位赋值元素引用.
- java.util.ArrayList#ensureCapacityInternal
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
- java.util.ArrayList#calculateCapacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
计算因子大小，如果当前列表为空，那么再比较10与传入的minCapacity哪个大，以此作为数组的因子。
如果不为空，那么按传入的minCapacity为因子.
- java.util.ArrayList#ensureExplicitCapacity
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
modCount: 此列表在结构上被修改的次数。 结构修改是改变列表的大小，或者以其他方式扰乱它，以致正在进行的迭代可能会产生不正确的结果。
此字段由返回的迭代器和列表迭代器实现中使用iterator和listIterator方法。 如果此字段的值意外更改，迭代器（或列表迭代器）将抛出ConcurrentModificationException以响应next 、 remove 、 previous 、 set或add操作。 这提供了快速失败行为，而不是在迭代期间面对并发修改时的非确定性行为。
子类使用此字段是可选的。 如果一个子类希望提供快速失败的迭代器（和列表迭代器），那么它只需要在它的add(int, E)和remove(int)方法（以及它覆盖的任何其他导致结构化的方法remove(int)增加这个字段列表的修改）。 对add(int, E)或remove(int)的单个调用必须向该字段添加不超过一个，否则迭代器（和列表迭代器）将抛出虚假的ConcurrentModificationExceptions 。 如果实现不希望提供快速失败的迭代器，则可以忽略此字段
如果 minCapacity比当前数组的长度要大，那么要进行扩容操作，调用grow->增加容量以确保它至少可以容纳由最小容量参数指定的元素数量。
- java.util.ArrayList#grow
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);
}
首先获取原本的数组长度.
再计算出newCapacity->原本的数组长度*1.5倍(这里不是严格的1.5,按二进制算,比如7>>1,得到3)
随后检查是否大于Integer.MAX_VALUE-8(这是由于虚拟机的限制，可能要在数组中保留一些信息)的长度.
最后调用Arrays.copyOf进行数组拷贝.
数组位移
在往数组中间插入元素的时候，java做了以下的操作
Object[] elementData = new Object[10];
elementData[0]=1;
elementData[1]=3;
// 相当于把3复制多了一个
System.arraycopy(elementData, 1, elementData, 2, 1);
System.out.println(Arrays.toString(elementData));
elementData[1] = 2;
System.out.println(Arrays.toString(elementData));
- java.util.ArrayList#add(int, E)
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
size-获取数组的长度
ArrayList内置数组的长度字段，所以直接返回size,时间复杂度是O(1).
public int size() {
return size;
}
indexOf-找出数组中与某个元素匹配的第一个元素
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
这里注意一下equals即可.
clear-清空数组
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
addAll-合并两个列表
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;
}
这里注意，有泛型的限制.
subList-子视图
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
子视图，顾名思义就是获取一定范围内的列表内容进行操作。如果越界，会报异常.
Arrays.asList-固定长度的列表
List<Integer> integers = Arrays.asList(1, 2);
integers.add(2);
上面的例子是会触发异常的，因为Arrays.asList获得的List无法动态扩容，它是固定长度的。
建议使用Guava包的Lists.newArrayList.
总结数组的好处
数组的好处就是随机访问一个元素非常方便，可以直接通过索引定位。缺点就是从数组中间插入或者删除元素时会造成元素移动.
链表-LinkedList
add-尾插法追加元素
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;
else
l.next = newNode;
size++;
modCount++;
}
last代表的是指向最后一个元素的引用，每次add的时候，将最新的元素视为last,然后前一个last的next指向新的last.
remove-删除
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
总结链表的缺点
链表不支持快速访问元素，比如[1,2,3],要访问2，就必须经过1.next，再访问2.
但是链表的插入和删除复杂度低，为O(1).
但是，任何的东西都要建立在数据量上，如果你的容器装载的元素数量不多，那么选择数组或者链表，区别都不大。
Vector-同步列表
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
Vector就是带有synchronized的List,在Java8中已经不推荐使用了，这里不做过多介绍。
线程安全问题
ArrayList和LinkedList是线程不安全的，Vector是线程安全的.
可以使用以下的方法获取线程安全的List.
List list = Collections.synchronizedList(new ArrayList());
