ArrayList 与 linkedList 源码分析

ArrayList

底层实现为数组，支持随机访问，可根据索引查找元素，插入删除中间元素时间复杂度为 O(n)；

默认初始容量为 10，使用默认初始容量时懒分配，扩容机制 1.5 倍；

线程不安全；

类图结构

重要属性

// 默认容量 10
private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};
// 二者区别在于是否由无参构造分配内存
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData;// 底层结构，存储元素的数组

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) {elementData = c.toArray();
    if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

扩容方法

1.5 倍扩容；

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 扩容 1.5 倍大小
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 新扩容容量溢出
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 新扩容容量大于 MAX_ARRAY_SIZE (Integer.MAX_VALUE - 8) 就分配 Integer.MAX_VALUE 的空间
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        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;
}

添加元素分析

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, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 如果新元素添加进来，新元素大于容量则扩容
    //minCapacity - elementData.length == 新元素个数 - 原数组容量
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

LinkedList

底层实现为双链表，插入删除中间元素时间复杂度为 O(1)，查找为 O(n)；

线程不安全；

类图结构

内部结构

// 内部类节点，双链表
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;
    }
}