Java常見比較二

ArrayList

1.png

ArrayList 在內(nèi)存中是連續(xù)的、單向的、有序的。
ArrayList 中維護(hù)了一個(gè)按照下標(biāo)順序的一組數(shù)組，數(shù)組中每個(gè) item 指向?qū)?yīng)得 value。

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
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;
}

當(dāng)我們通過下標(biāo)進(jìn)行指定位置增加或者刪除操作時(shí)，先由下標(biāo) index 從 item 數(shù)組找到對(duì)應(yīng) item，接著從這個(gè)下標(biāo)開始向后，把剩下的 item 通過覆蓋復(fù)制，向后或者向前移動(dòng)一位，最后在 index 位置增加一個(gè) item 或者置空末尾 item。

// 增加
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

// 刪除
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

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

    return oldValue;
}

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

當(dāng)我們通過下標(biāo)指定位置查找或者修改操作時(shí)，先由下標(biāo) index 從 item 數(shù)組獲取對(duì)應(yīng)item，返回或者修改 item 指向的對(duì)象地址。

// 查找
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

// 修改
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

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

LinkedList

2.png

LinkedList 在內(nèi)存中時(shí)不連續(xù)的、雙向的、有序的；
LinkedList 中的每個(gè) item，成為 node，它包含三個(gè)部分：當(dāng)前 node 的 value，指向上一個(gè) node 的指針 prev、指向下一個(gè) node 的指針 next。由于 LinkedList 還保存了第一個(gè) node 稱為 first 和最后一個(gè) node 稱為 last，所以他還是雙向的。

transient Node<E> first;
transient Node<E> last;
public LinkedList() {
}

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

當(dāng)我們通過下標(biāo)進(jìn)行指定位置增加或者刪除操作時(shí)，會(huì)從 first node 開始（如果下標(biāo)指向未端，則直接到末端 node），不斷地由 node 的 next 找到下一個(gè) node,直到到達(dá)目標(biāo) node,如果是增加操作，則創(chuàng)建一個(gè) node，將上一個(gè) node 的 next 指向新 node 的 prev，將下一個(gè) node 的 prev 指向新 node 的 next，這樣就在 list 中間重新連接起來；如果是刪除操作，則刪除當(dāng)前 node，將上一個(gè) node 的 next 指向下一個(gè) node 的 prev。

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

// 增加
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

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

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

// 刪除
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

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

當(dāng)我們通過下標(biāo)進(jìn)行指定位置查詢或者修改操作時(shí)，會(huì)從 first node 或者 last node（LinkedList.get(int index)方法中，會(huì)對(duì)下標(biāo)值進(jìn)行判斷，如果小于長(zhǎng)度的一半，則從 first 開始，否則從 last 開始，這是對(duì)雙向性的利用）開始，不斷的由 node 的 next 去找下一個(gè) node 的地址，直到到達(dá)目標(biāo) node，返回 value 或者修改 value 指向的地址
。

// 查找
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

// 修改
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

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

效率對(duì)比

• ArrayList的優(yōu)勢(shì)在于隨機(jī)快速讀取，其直接在末尾插入元素的效率也很高。唯一需要注意的是，其resize的時(shí)候，需要一定的開銷。所以如果你提前能預(yù)估ArrayList的大小，你可以在實(shí)例化時(shí)，給他賦一個(gè)initialCapacity，可以減小resize的次數(shù)。
• LinkedList的優(yōu)勢(shì)在于利用Iterator迭代器循環(huán)時(shí)，其插入和刪除的效率都是最高的。
• 在存儲(chǔ)空間上，LinkedList相比ArrayList的每個(gè)元素都有更多的開銷，因?yàn)檫€存儲(chǔ)了指向下一個(gè)和前一個(gè)元素的指針。所以如果你的list很大的話，這一點(diǎn)也需要考慮進(jìn)去。