java之arraylist与linkedlist比较 ~ git

ArrayList
ArrayList的底层实现为数组存储在内存中，线程不同步。可通过数组下标的形式进行查找，所以在查询方面的效率较为出色，常用在查询较多的情景下。

LinkedList
LinkedList的底层实现为链表形式，也为线程不同步。而链表的底层也决定了它在查询方面不如数组底层的ArrayList而在指定位置插入等修改操作下，性能优于ArrayList。

Vector
另外还有Vector，Vector也是和ArrayList、LinkedList一样实现了java.util.List接口。最大的区别在于Vestor是线程同步的，所以在效率方面不如另外两者，适用于多线程项目中。

由于它的底层是用双向链表实现的，没有初始化大小，也没有扩容的机制。每次add操作只需要将last的链表和新的添加连起来合成新的就可以了

 public boolean add(E e) {
        linkLast(e);
        return true;
    }

  void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

ArrayList继承自AbstractList，实现了 List, RandomAccess, Cloneable, java.io.Serializable接口，因此可以copy和序列化
这里可以看到定义了ArrayList的默认初始值的10，最大值是2的31次方-8。
有三个构造函数，分别是一个无参构造函数和两个有参构造函数，

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /* 
    这里定义了arrayList的最大值，2的31次方-8;
    */
     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

    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);
        }
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    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;
        }
    }

扩容操作在执行add操作时执行，可以看出add操作制作两件事。
- 1.执行所需容量加1
- 2.执行将添加元素加入列表
在ensureCapacityInternal会将新的所需容量传递给calculateCapacity，它会判断，如果elementData为空时，直接返回默认初始值10，否则返回所需容量值，
ensureExplicitCapacity则会执行modCount加1的操作，用于记录每次add操作，然后判断所需容量大于当前数组长度后，执行grow进行扩容，每次扩容的量时现有容量的1.5倍

/*
在执行add添加新元素时，首先执行ensureCapacityInternal，使最小容量加1，然后将添加的元素存入索引为size++的elementData中，返回true
*/

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

/*
    calculateCapacity判断elementData不等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA时（即不是空时），返回minCapacity，否则直接返回默认值10
*/

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }


/*
    继承自abstractList的modCount++，记录每次执行add的次数，当minCapacity大于elementData.length时，执行扩容
*/
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }




    /**
     * 这里执行真正的扩容操作，新容量=旧容量+旧容量/2，
       如果新容量依然小于所需容量，新容量=所需容量，
       如果新容量大于最大容量，返回最大容量，确保容量不能超过最大容量
       然后将数据copy到新的大容量list中
     *
     * @param minCapacity 所需要的最小容量
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        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;
    }