ArrayList&LinkedList源码解读
ArrayList
概述
ArrayList实现了List接口，是顺序容器，允许放入null，底层通过数组实现，线程不安全，容量不足会自动扩容
transient Object[] elementData;//使用transient关键字不序列化某个变量
private int size;
构造函数
可以指定容量，默认为空，所以最少扩容一次，可以提前预估容量提升性能
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;
}
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
自动扩容逻辑
一般扩容1.5倍，超出最大值后扩容为Integer.MAX_VALUE
在可以预估扩容大小的时候可以使用内部公开方法ensureCapacity，提前扩容，以减少扩容次数。
private void grow(int minCapacity) {
//拿到旧的长度
int oldCapacity = elementData.length;
//设置新的为旧的1.5倍, 右移运算除以2
int newCaacity = oldCapacity + (oldCapacity >> 1);
//如果仍然满足不了最小需求，就设置为最小需求
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果已经超出了最大限制
if (newCapacity - MAX_ARRAY_SIZE > 0)
//将最大限制设置为Integer.MAX_VALUE
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;
}
添加逻辑
每次添加之前会检查容量是否足够，不够会使用grow方法进行扩容
如果指定添加的位置，则需要先对元素进行移动，O(n)的复杂度
同样的删除指定位置也需要移动，删除最后一个位置不需要。
需要注意的是为了让GC起作用，防止内存泄漏，需要为删除位置显示置空
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
缩容
指的是可以手动将数组空间调整为当前实际大小，防止空间浪费，也是通过移动数组实现的。
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
快速失败
任何结构性修改操作都会引发modCount++
当迭代器发现modCount被修改后，就会抛出ConcurrentModificationException异常（当前修改异常）
注意是结构性修改，例如add、remove等改变数组大小的操作
set操作修改某个特定位置的引用时，不会触发迭代器快速失败
LinkedList
概述
LinkedList使用双向链表实现了List和Deque接口，因此它可以作为顺序容器、队列和栈，但是这个类几乎不会被使用（但是我经常使用），一般定义栈或者队列可以使用ArrayDeque（我也得改过来），比LinkedList性能好很多。
因为使用了双向链表，所以决定了所有跟下标相关的操作都是线性时间。队首队尾操作是常数时间，线程不安全。
Deque<String> stack1 = new LinkedList<>();
Deque<String> stack2 = new ArrayDeque<>();
内部元素
LinkedList底层通过定义first和last指针指向第一个和最后一个元素，但时候链表为空的时候没有dummy节点，都指向null。
transient int size;
transient Node<E> first;
transient Node<E> last;
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;
}
}
构造函数
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
涉及方法
getFirst()
getLast()
removeFirst()
removeLast()
remove(e)
remove(index)
因为是双向链表，所以删除时只需要unlink就行，由JVM进行垃圾回收
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final ode<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; // GC
size--;
modCount++;
return element;
}
清空链表
LinkedList为了让GC可以更快速回收元素，提供了clear方法，清除所有节点间的引用关系。
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
快速失败
在遍历过程中对集合进行了结构性修改（如添加或删除元素），LinkedList的迭代器会抛出ConcurrentModificationException异常。
原理仍然是维护了一个modCount变量，每次结构性修改时++。
发散
在ArrayList中大量使用了Arrays.copyOf方法
方法传入（原始数组、新数组长度、新数组类型）进行数组扩容
这个方法底层其实是一个native方法System.arraycopy
System.arraycopy利用了底层系统的内存复制功能进行数组复制
-
首先创建一个新数组，定义复制参数
-
src：源数组，即要从中复制元素的数组。srcPos：源数组中的起始位置，从这个位置开始复制元素。dest：目标数组，即要将元素复制到的数组。destPos：目标数组中的起始位置，复制到这个位置。length：要复制的元素数量。