ArrayList & LinkedList源码解析

• 2021 年 10 月 10 日
• 筆記
• 集合

本文记录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;
}    

综述 可以知道

1. 任何一个空的数组 第一次添加元素的时候 内部数组容量将被扩容为10
2. 扩容时，newCapacity为oldCapacity的1.5倍
3. 容量最大值为Integer.MAX_VALUE – 8
4. 尾部添加元素不用移动任何元素 所以速度快