ArrayList 与 linkedList 源码分析

ArrayList

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

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

线程不安全；

类图结构

重要属性

//默认容量10private 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;    }}