ArrayList & LinkedList源码解析
本文记录ArrayList & LinkedList源码解析 基于JDK1.8
ArrayList
ArrayList实现了List接口 所有拥有List接口所有方法 可以看成可’调节’的数组 可以包含任何类型数据（包括null，可重复）ArrayList线程不是安全的
类结构
ArrayList类主要成员变量：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
// 初始化容量(数组初始长度) 10
private static final int DEFAULT_CAPACITY = 10;
// 表示空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 也是空数组，和EMPTY_ELEMENTDATA区分开
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 装ArrayList的数组
transient Object[] elementData; // non-private to simplify nested class access
// 数组长度
private int size;
}
方法解析
构造函数
public ArrayList()
public ArrayList() {
// elementData为DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity)
public ArrayList(int initialCapacity) {
// initialCapacity初始化容量 由调用者传入
// 如果initialCapacity大于0
if (initialCapacity > 0) {
// elementData为 Object类型的 initialCapacity大小的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 如果初始值为0 elementData为 EMPTY_ELEMENTDATA 空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
// initialCapacity 小于0 抛错
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList(Collection<? extends E> c)
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;
}
}
创建一个包含指定集合c数据的ArrayList 上面为什么要多此一举使用
Arrays.copyOf(elementData, size, Object[].class)复制一遍数组呢？这是因为在某些情况下
调用集合的toArray()方法返回的类型并不是Object[].class 比如：
Long[] array1 = {1L, 2L};
List<Long> list1 = Arrays.asList(array1);
Object[] array2 = list1.toArray();
System.out.println(array2.getClass() == Object[].class); // false
List<Long> list2 = new ArrayList<>();
System.out.println(list2.toArray().getClass() == Object[].class); // true
add方法
add(E e)向数组尾部添加元素
public boolean add(E e) {
// 确定数组容量 size 类型为int 默认值(即初始值)为 0
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// minCapacity = size + 1 = 1
// elementData = {}
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// Math.max返回最大的数组 DEFAULT_CAPACITY = 10 minCapacity = 1 返回 10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// minCapacity = 10
// elementData = {}
// 10 - 0 > 0
if (minCapacity - elementData.length > 0)
// 扩容
grow(minCapacity);
}
private void grow(int minCapacity) {
// oldCapacity = 0
int oldCapacity = elementData.length;
// >> 右移运算符 相当于newCapacity为oldCapacity的1.5倍
// oldCapacity / 2 此处 0 + 0 / 2 还是等于 0
int newCapacity = oldCapacity + (oldCapacity >> 1);
// newCapacity = 0 minCapacity = 10 0 - 10 < 0 条件成立
if (newCapacity - minCapacity < 0)
// newCapacity = 10
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// // 复制到新数组 数组容量为10
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// MAX_ARRAY_SIZE常量值为Integer.MAX_VALUE - 8 通过
// 这段逻辑我们可以知道，ArrayList最大容量为Integer.MAX_VALUE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
综述 可以知道
- 任何一个空的数组 第一次添加元素的时候 内部数组容量将被扩容为10
- 扩容时，newCapacity为oldCapacity的1.5倍
- 容量最大值为Integer.MAX_VALUE – 8
- 尾部添加元素不用移动任何元素 所以速度快
