引言

由上一篇我們知道，ArrayList的優(yōu)勢(shì)是查詢(xún)速度快，但是插入、刪除相對(duì)較慢，那對(duì)于需要大量增、刪操作的數(shù)據(jù)，該用什么樣的結(jié)構(gòu)呢？

鏈表

單向鏈表

如圖所示，定義一種鏈表結(jié)構(gòu)，每一個(gè)節(jié)點(diǎn)都持有下一個(gè)節(jié)點(diǎn)的引用，當(dāng)增加元素時(shí)，只需要修改當(dāng)前位置的指向即可，速度就會(huì)比ArrayList復(fù)制快。

單向鏈表新增元素

顯然，它有一個(gè)弊端，如果我們想獲取最后一個(gè)元素，必須從第一個(gè)元素一個(gè)一個(gè)查下去，浪費(fèi)時(shí)間。

為了提高查詢(xún)效率，定義如下結(jié)構(gòu)：

雙向鏈表

每個(gè)元素都持有它前、后兩個(gè)元素的引用，在遇到上述問(wèn)題，會(huì)大大縮短查詢(xún)時(shí)間。

LinkedList源碼

鏈表首、尾節(jié)點(diǎn)的引用：

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;
/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

Node結(jié)構(gòu)

private static class Node<E> {
    E item;
    Node<E> next;// 下一個(gè)元素
    Node<E> prev;// 上一個(gè)元素
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

添加元素 add -> linkLast

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

/**
 * Links e as last element.
 */
void linkLast(E e) {
    // 取尾部元素
    final Node<E> l = last;
    // 生成新的Node節(jié)點(diǎn)
    final Node<E> newNode = new Node<>(l, e, null);
    // 將尾引用指向新的節(jié)點(diǎn)
    last = newNode;
    if (l == null)// 如果列表中沒(méi)有元素，將頭指向新節(jié)點(diǎn)
        first = newNode;
    else// 如果有元素，將新節(jié)點(diǎn)鏈接到隊(duì)尾
        l.next = newNode;
    size++;
    modCount++;
}

刪除元素 remove -> unlink

public boolean remove(Object o) {
    if (o == null) {
        // 遍歷刪除null
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        // 遍歷找到equals的對(duì)象
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

E unlink(Node<E> x) {
    // assert x != null;
    // 獲取當(dāng)前節(jié)點(diǎn)的前后節(jié)點(diǎn)
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    // 刪除跟上個(gè)節(jié)點(diǎn)的關(guān)系
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    // 刪除跟下個(gè)節(jié)點(diǎn)的關(guān)系
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    // 刪除數(shù)據(jù)
    x.item = null;
    size--;
    modCount++;
    return element;
}

查詢(xún)數(shù)據(jù) get -> node

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

Node<E> node(int index) {
    // assert isElementIndex(index);
    // 判斷index是否<總個(gè)數(shù)/2
    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;
    }
}

其他

LinkedList插入一定比ArrayList快嗎？

大家不妨跑跑下面的代碼:

public class MyTest {
    private static ArrayList<Integer> testArray = new ArrayList<>();
    private static LinkedList<Integer> testLinked = new LinkedList<>();

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++) {
            testArray.add(i);
        }
        System.out.println("AAAAA test array time:" + (System.currentTimeMillis() - start));

        start = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++) {
            testLinked.add(i);
        }
        System.out.println("AAAAA test linked time:" + (System.currentTimeMillis() - start));
    }

}

這是我跑了幾次的結(jié)果

AAAAA test array time:1233
AAAAA test linked time:2396

AAAAA test array time:833
AAAAA test linked time:2312

AAAAA test array time:824
AAAAA test linked time:2242

于是得出以下結(jié)論，在涉及大量數(shù)據(jù)的增加（直接增加，插入末尾）且很少涉及刪除的操作時(shí)，ArrayList速度反而更快。

為什么會(huì)如此呢？可能與以下代碼有關(guān)：

LinkedList添加元素時(shí)，創(chuàng)建新的Node

LinkedList每次add時(shí)，便創(chuàng)建一個(gè)Node對(duì)象，增大了時(shí)間開(kāi)銷(xiāo)。