天天看點
傳回

上次被 ArrayList 錘了一拳後，LinkedList 很不服氣，做出最後一擊(3)

經過源碼分析以後，小夥伴們是不是在想：“好像 ArrayList 在新增元素的時候效率并不一定比 LinkedList 低啊！”

當兩者的起始長度是一樣的情況下：

如果是從集合的頭部新增元素，ArrayList 花費的時間應該比 LinkedList 多，因為需要對頭部以後的元素進行複制。

public class ArrayListTest {
    public static void addFromHeaderTest(int num) {
        ArrayList<String> list = new ArrayList<String>(num);
        int i = 0;
        long timeStart = System.currentTimeMillis();
        while (i < num) {
            list.add(0, i + "沉默王二");
            i++;
        }
        long timeEnd = System.currentTimeMillis();
        System.out.println("ArrayList從集合頭部位置新增元素花費的時間" + (timeEnd - timeStart));
    }
}
/**
 * @author 微信搜「沉默王二」，回複關鍵字 PDF
 */
public class LinkedListTest {
    public static void addFromHeaderTest(int num) {
        LinkedList<String> list = new LinkedList<String>();
        int i = 0;
        long timeStart = System.currentTimeMillis();
        while (i < num) {
            list.addFirst(i + "沉默王二");
            i++;
        }
        long timeEnd = System.currentTimeMillis();
        System.out.println("LinkedList從集合頭部位置新增元素花費的時間" + (timeEnd - timeStart));
    }
}

num 為 10000，代碼實測後的時間如下所示：

ArrayList從集合頭部位置新增元素花費的時間595

LinkedList從集合頭部位置新增元素花費的時間15

ArrayList 花費的時間比 LinkedList 要多很多。

如果是從集合的中間位置新增元素，ArrayList 花費的時間搞不好要比 LinkedList 少，因為 LinkedList 需要周遊。

public class ArrayListTest {
    public static void addFromMidTest(int num) {
        ArrayList<String> list = new ArrayList<String>(num);
        int i = 0;
        long timeStart = System.currentTimeMillis();
        while (i < num) {
            int temp = list.size();
            list.add(temp / 2 + "沉默王二");
            i++;
        }
        long timeEnd = System.currentTimeMillis();
        System.out.println("ArrayList從集合中間位置新增元素花費的時間" + (timeEnd - timeStart));
    }
}
public class LinkedListTest {
    public static void addFromMidTest(int num) {
        LinkedList<String> list = new LinkedList<String>();
        int i = 0;
        long timeStart = System.currentTimeMillis();
        while (i < num) {
            int temp = list.size();
            list.add(temp / 2, i + "沉默王二");
            i++;
        }
        long timeEnd = System.currentTimeMillis();
        System.out.println("LinkedList從集合中間位置新增元素花費的時間" + (timeEnd - timeStart));
    }
}

ArrayList從集合中間位置新增元素花費的時間1

LinkedList從集合中間位置新增元素花費的時間101

ArrayList 花費的時間比 LinkedList 要少很多很多。

如果是從集合的尾部新增元素，ArrayList 花費的時間應該比 LinkedList 少，因為數組是一段連續的記憶體空間，也不需要複制數組；而連結清單需要建立新的對象，前後引用也要重新排列。

public class ArrayListTest {
    public static void addFromTailTest(int num) {
        ArrayList<String> list = new ArrayList<String>(num);
        int i = 0;
        long timeStart = System.currentTimeMillis();
        while (i < num) {
            list.add(i + "沉默王二");
            i++;
        }
        long timeEnd = System.currentTimeMillis();
        System.out.println("ArrayList從集合尾部位置新增元素花費的時間" + (timeEnd - timeStart));
    }
}
public class LinkedListTest {
    public static void addFromTailTest(int num) {
        LinkedList<String> list = new LinkedList<String>();
        int i = 0;
        long timeStart = System.currentTimeMillis();
        while (i < num) {
            list.add(i + "沉默王二");
            i++;
        }
        long timeEnd = System.currentTimeMillis();
        System.out.println("LinkedList從集合尾部位置新增元素花費的時間" + (timeEnd - timeStart));
    }
}

ArrayList從集合尾部位置新增元素花費的時間69

LinkedList從集合尾部位置新增元素花費的時間193

1

2

ArrayList 花費的時間比 LinkedList 要少一些。

這樣的結論和預期的是不是不太相符？ArrayList 在添加元素的時候如果不涉及到擴容，性能在兩種情況下（中間位置新增元素、尾部新增元素）比 LinkedList 好很多，隻有頭部新增元素的時候比 LinkedList 差，因為數組複制的原因。

當然了，如果涉及到數組擴容的話，ArrayList 的性能就沒那麼可觀了，因為擴容的時候也要複制數組。

04、ArrayList 和 LinkedList 删除元素時究竟誰快？

1）ArrayList

ArrayList 删除元素的時候，有兩種方式，一種是直接删除元素（remove(Object)），需要直先周遊數組，找到元素對應的索引；一種是按照索引删除元素（remove(int)）。

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}
public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;
    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);
    return oldValue;
}

但從本質上講，都是一樣的，因為它們最後調用的都是 fastRemove(Object, int) 方法。

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

從源碼可以看得出，隻要删除的不是最後一個元素，都需要數組重組。删除的元素位置越靠前，代價就越大。

2）LinkedList

LinkedList 删除元素的時候，有四種常用的方式：

remove(int)，删除指定位置上的元素

public E remove(int index) {

   checkElementIndex(index);

   return unlink(node(index));

}

先檢查索引，再調用 node(int) 方法（ 前後半段周遊，和新增元素操作一樣）找到節點 Node，然後調用 unlink(Node) 解除節點的前後引用，同時更新前節點的後引用和後節點的前引用：

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;
    }
remove(Object)，直接删除元素
public boolean remove(Object o) {
    if (o == null) {
        for (LinkedList.Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (LinkedList.Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}
也是先前後半段周遊，找到要删除的元素後調用 unlink(Node)。
removeFirst()，删除第一個節點
public E removeFirst() {
    final LinkedList.Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
private E unlinkFirst(LinkedList.Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final LinkedList.Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

删除第一個節點就不需要周遊了，隻需要把第二個節點更新為第一個節點即可。

removeLast()，删除最後一個節點

删除最後一個節點和删除第一個節點類似，隻需要把倒數第二個節點更新為最後一個節點即可。

可以看得出，LinkedList 在删除比較靠前和比較靠後的元素時，非常高效，但如果删除的是中間位置的元素，效率就比較低了。

這裡就不再做代碼測試了，感興趣的小夥伴可以自己試試，結果和新增元素保持一緻：

從集合頭部删除元素時，ArrayList 花費的時間比 LinkedList 多很多；

從集合中間位置删除元素時，ArrayList 花費的時間比 LinkedList 少很多；

從集合尾部删除元素時，ArrayList 花費的時間比 LinkedList 少一點。

我本地的統計結果如下所示，小夥伴們可以作為參考：

ArrayList從集合頭部位置删除元素花費的時間380

LinkedList從集合頭部位置删除元素花費的時間4

ArrayList從集合中間位置删除元素花費的時間381

LinkedList從集合中間位置删除元素花費的時間5922

ArrayList從集合尾部位置删除元素花費的時間8

LinkedList從集合尾部位置删除元素花費的時間12

05、ArrayList 和 LinkedList 周遊元素時究竟誰快？

周遊 ArrayList 找到某個元素的話，通常有兩種形式：

get(int)，根據索引找元素
public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

由于 ArrayList 是由數組實作的，是以根據索引找元素非常的快，一步到位。

indexOf(Object)，根據元素找索引
public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

根據元素找索引的話，就需要周遊整個數組了，從頭到尾依次找。

索引 索引分鐘 引用索引 選擇索引 使用索引 索引指定
上一篇: 上次被 ArrayList 錘了一拳後，LinkedList 很不服氣，做出最後一擊(4)
下一篇: 關于Chrome支援http header最大長度限制的讨論

繼續閱讀