LinkedList與ArrayList新增/刪除元素效率哪個(gè)更快

ArrayList 與 LinkedList 刪除元素比較

刪除元素和新增元素的原理是一樣的，所以刪除元素的操作和新增元素的操作耗時(shí)也是很相近

這里就不再贅述

ArrayList 與 LinkedList 遍歷元素比較

測(cè)試結(jié)果非常明顯，對(duì)于 LinkedList 來(lái)說(shuō)，如果使用 for 循環(huán)的話，效率特別低，但是 ArrayList 使用 for 循環(huán)去遍歷的話，就比較高

為啥呢？

emmm ，得從源碼說(shuō)起

先來(lái)看 ArrayList 的源碼吧，這個(gè)比較簡(jiǎn)單

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

能夠看到， ArrayList 實(shí)現(xiàn)了 List ， RandomAccess ， Cloneable 還有 Serializable 接口

你是不是對(duì) RandomAccess 這個(gè)接口挺陌生的？這是個(gè)啥？

但是通過(guò)查閱源碼能夠發(fā)現(xiàn)它也只是個(gè)空的接口罷了，那 ArrayList 為啥還要去實(shí)現(xiàn)它嘞

因?yàn)?RandomAccess 接口是一個(gè)標(biāo)志接口，它標(biāo)識(shí)著“只要實(shí)現(xiàn)該接口的 list 類，都可以實(shí)現(xiàn)快速隨機(jī)訪問(wèn)”

實(shí)現(xiàn)快速隨機(jī)訪問(wèn)？你能想到什么？這不就是數(shù)組的特性嘛！可以直接通過(guò) index 來(lái)快速定位 & 讀取

那你是不是就能想到， ArrayList 是數(shù)組實(shí)現(xiàn)的，所以實(shí)現(xiàn)了 RandomAccess 接口， LinkedList 是用鏈表實(shí)現(xiàn)的，所以它沒(méi)有用 RandomAccess 接口實(shí)現(xiàn)吧？

beautiful ~就是這樣

咱瞅瞅 LinkedList 源碼

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

果然，跟咱們?cè)O(shè)想的一樣，沒(méi)有實(shí)現(xiàn) RandomAccess 接口

那為啥 LinkedList 接口使用 for 循環(huán)去遍歷的時(shí)候，慢的不行呢？

咱們瞅瞅 LinkedList 在 get 元素時(shí)，都干了點(diǎn)兒啥

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

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

在 get 方法中，主要調(diào)用了 node() 方法，因?yàn)?LinkedList 是雙向鏈表，所以 if (index < (size >> 1)) 在判斷 i 是在前半段還是后半段，如果是前半段就正序遍歷，如果是在后半段那就倒序遍歷，那么為什么使用 for 循環(huán)遍歷 LinkedList 時(shí)，會(huì)這么慢？（好像離真相越來(lái)越近了

原因就在兩個(gè) for 循環(huán)之中，以第一個(gè) for 循環(huán)為例

• get(0) ：直接拿到了node0 地址，然后拿到 node0 的數(shù)據(jù)

• get(1) ：先拿到 node0 地址，然后 i < index ，開(kāi)始拿 node1 的地址，符合條件，然后去拿 node1 的數(shù)據(jù)

• get(2) ：先拿到 node0 的地址，然后 i < index ，拿到 node1 的地址， i < index ，繼續(xù)向下走，拿到 node2 的地址，符合條件，獲取 node2 的數(shù)據(jù)

發(fā)現(xiàn)問(wèn)題了嘛？我就是想要 2 的數(shù)據(jù)， LinkedList 在遍歷時(shí)，將 0 和 1 也給遍歷了，如果數(shù)據(jù)量非常大的話，那效率可不就唰唰的下來(lái)了嘛

那到現(xiàn)在，咱們也就非常明確了，如果是要遍歷 ArrayList 的話，最好是用 for 循環(huán)去做，如果要遍歷 LinkedList 的話，最好是用迭代器去做

我猜你一定會(huì)說(shuō)，阿粉啊，那如果對(duì)方就給我傳過(guò)來(lái)了一個(gè) list ，我不知道它是 ArrayList 還是 LinkedList 呀？我該怎么辦呢

還記得 ArrayList 和 LinkedList 有什么不同嗎？是不是 ArrayList 實(shí)現(xiàn)了 RandomAccess 接口，但是 LinkedList 沒(méi)有實(shí)現(xiàn)，所以可以從這點(diǎn)去著手解決

暖暖的阿粉在這里給個(gè)簡(jiǎn)單的小 demo ，可以參考下:

public class ListTest {
    public static void main(String[] args) {
        List<String> arrayList = new ArrayList<String>();
        arrayList.add("aaa");
        arrayList.add("bbb");
        isUseIterator(arrayList);

        List<String> linkedList = new LinkedList<String>();
        linkedList.add("ccc");
        linkedList.add("ddd");
        isUseIterator(linkedList);
    }

    public static void isUseIterator(List list){
        if (list instanceof RandomAccess){
            System.out.println("實(shí)現(xiàn)了 RandomAccess 接口,使用 for 循環(huán)遍歷");

            for (int i = 0 ; i < list.size(); i++ ){
                System.out.println(list.get(i));
            }
        }else{
            System.out.println("沒(méi)有實(shí)現(xiàn) RandomAccess 接口,使用迭代器遍歷");

            Iterator it = list.iterator();
            while (it.hasNext()){
                System.out.println(it.next());
            }
        }
    }
}