ArrayList、LinkedList 和 Vector源碼解析

ArrayList查看源碼

//初始容量
private static final int DEFAULT_CAPACITY = 10;
//數(shù)據(jù)存儲(不可序列化的數(shù)組)
private transient Object[] elementData;
//當(dāng)前容量
private int size;

ArrayList add()方法

private void grow(int minCapacity) {
        //獲取原有數(shù)組長度
        int oldCapacity = elementData.length;
        //長度增加1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果長度擴(kuò)展后小于當(dāng)前所需容量則取當(dāng)前所需容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果擴(kuò)容已至最大Integer.MAX_VALUE - 8則依據(jù)當(dāng)前長度判斷取Integer.MAX_VALUE - 8還是取Integer.MAX_VALUE
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //數(shù)組復(fù)制將數(shù)組擴(kuò)容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

ArrayList remove()方法

   public E remove(int index) {
        //校驗(yàn)長度
        rangeCheck(index);
        //AbstractList變量 表示修改次數(shù)
        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        //數(shù)組移動
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

ArrayList get()方法

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }
    
     E elementData(int index) {
        return (E) elementData[index];
    }

綜上得出結(jié)論：==ArrayList底層為動態(tài)數(shù)組伐债，擴(kuò)容規(guī)則為1.5倍房午。ArrayList可快速的get(i),但是add和remove涉及System.arraycopy()數(shù)組復(fù)制蹋绽，性能變差==
LinkedList查看源碼

//鏈表頭
transient Node<E> first;
//鏈表尾
transient Node<E> last;
//鏈表數(shù)據(jù)結(jié)構(gòu)
private static class Node<E> {
    //當(dāng)前節(jié)點(diǎn)
    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;
    }
}

LinkedList add()方法

//創(chuàng)建新節(jié)點(diǎn) 將新創(chuàng)建的節(jié)點(diǎn)加入鏈表 
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++;
    }

LinkedList remove()方法

//從表頭開始遍歷拍霜，查出數(shù)據(jù)與刪除數(shù)據(jù)一致的節(jié)點(diǎn)
//刪除節(jié)點(diǎn) 簡單理解：將當(dāng)前節(jié)點(diǎn)的上一個節(jié)點(diǎn)的下一個節(jié)點(diǎn)置成當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)即可 
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

LinkedList get()方法

//根據(jù)下標(biāo)判斷是從鏈表頭還是從鏈表尾開始查找
    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

綜上得出結(jié)論：
==1、add()和remove() LinkedList的只涉及一個節(jié)點(diǎn)的操作挽铁，比ArrayList的數(shù)組移動效率高
2伟桅、get()方法ArrayList數(shù)組下標(biāo)獲取比LinkedList效率高==

Vector 和ArrayList一致，只不過在方法前加synchronized形成同步線性安全