測(cè)試結(jié)果

廢話不多說(shuō)，先上測(cè)試結(jié)果。作者分別在ArrayList和LinkedList的頭部、尾部和中間三個(gè)位置插入與查找100000個(gè)元素所消耗的時(shí)間來(lái)進(jìn)行對(duì)比測(cè)試，下面是測(cè)試結(jié)果

（感謝@Hosalo的指正，在這里說(shuō)明一下測(cè)試的環(huán)境，尾部插入是在空表的基礎(chǔ)上測(cè)試的，頭部和中間位置插入是在已存在100000個(gè)元素的表上進(jìn)行測(cè)試的）

插入 查找 ArrayList尾部 26ms 4ms ArrayList頭部 2887ms 3ms ArrayList中間 1936ms 4ms LinkedList尾部 28ms 9ms LinkedList頭部 15ms 11ms LinkedList中間 12310ms 11387ms

測(cè)試結(jié)論

ArrayList的查找性能絕對(duì)是一流的，無(wú)論查詢的是哪個(gè)位置的元素 ArrayList除了尾部插入的性能較好外（位置越靠后性能越好），其他位置性能就不如人意了 LinkedList在頭尾查找、插入性能都是很棒的，但是在中間位置進(jìn)行操作的話，性能就差很遠(yuǎn)了，而且跟ArrayList完全不是一個(gè)量級(jí)的

源碼分析

我們把Java中的ArrayList和LinkedList就是分別對(duì)順序表和雙向鏈表的一種實(shí)現(xiàn)，所以在進(jìn)行源碼分析之前，我們先來(lái)簡(jiǎn)單回顧一下數(shù)據(jù)結(jié)構(gòu)中的順序表與雙向鏈表中的關(guān)鍵概念

順序表：需要申請(qǐng)連續(xù)的內(nèi)存空間保存元素，可以通過(guò)內(nèi)存中的物理位置直接找到元素的邏輯位置。在順序表中間插入or刪除元素需要把該元素之后的所有元素向前or向后移動(dòng)。 雙向鏈表：不需要申請(qǐng)連續(xù)的內(nèi)存空間保存元素，需要通過(guò)元素的頭尾指針找到前繼與后繼元素（查找元素的時(shí)候需要從頭or尾開始遍歷整個(gè)鏈表，直到找到目標(biāo)元素）。在雙向鏈表中插入or刪除元素不需要移動(dòng)元素，只需要改變相關(guān)元素的頭尾指針即可。

所以我們潛意識(shí)會(huì)認(rèn)為：ArrayList查找快，增刪慢。LinkedList查找慢，增刪快。但實(shí)際上真的是這樣的嗎？我們一起來(lái)看看吧。

測(cè)試程序

測(cè)試程序代碼基本沒(méi)有什么營(yíng)養(yǎng)，這里就不貼出來(lái)了，但是得把程序的運(yùn)行結(jié)果貼出來(lái)，方便逐個(gè)分析。

運(yùn)行結(jié)果

ArrayList尾部插入100000個(gè)元素耗時(shí)：26msLinkedList尾部插入100000個(gè)元素耗時(shí)：28msArrayList頭部插入100000個(gè)元素耗時(shí)：859msLinkedList頭部插入100000個(gè)元素耗時(shí)：15msArrayList中間插入100000個(gè)元素耗時(shí)：1848msLinkedList中間插入100000個(gè)元素耗時(shí)：15981msArrayList頭部讀取100000個(gè)元素耗時(shí)：7msLinkedList頭部讀取100000個(gè)元素耗時(shí)：11msArrayList尾部讀取100000個(gè)元素耗時(shí)：12msLinkedList尾部讀取100000個(gè)元素耗時(shí)：9msArrayList中間讀取100000個(gè)元素耗時(shí)：13msLinkedList中間讀取100000個(gè)元素耗時(shí)：11387ms

ArrayList尾部插入

源碼

add(E e)方法 public boolean add(E e) { // 檢查是否需要擴(kuò)容 ensureCapacityInternal(size + 1); // Increments modCount!! // 直接在尾部添加元素 elementData[size++] = e; return true; }

可以看出，對(duì)ArrayList的尾部插入，直接插入即可，無(wú)須額外的操作。

LinkedList尾部插入

源碼

LinkedList中定義了頭尾節(jié)點(diǎn) /** * Pointer to first node. */ transient Node<E> first; /** * Pointer to last node. */ transient Node<E> last;

add(E e)方法，該方法中調(diào)用了linkLast(E e)方法

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

linkLast(E e)方法，可以看出，在尾部插入的時(shí)候，并不需要從頭開始遍歷整個(gè)鏈表，因?yàn)橐呀?jīng)事先保存了尾結(jié)點(diǎn)，所以可以直接在尾結(jié)點(diǎn)后面插入元素

/** * Links e as last element. */ void linkLast(E e) { // 先把原來(lái)的尾結(jié)點(diǎn)保存下來(lái) final Node<E> l = last; // 創(chuàng)建一個(gè)新的結(jié)點(diǎn)，其頭結(jié)點(diǎn)指向last final Node<E> newNode = new Node<>(l, e, null); // 尾結(jié)點(diǎn)置為newNode last = newNode; if (l == null) first = newNode; else // 修改原先的尾結(jié)點(diǎn)的尾結(jié)點(diǎn)，使其指向新的尾結(jié)點(diǎn) l.next = newNode; size++; modCount++; }

總結(jié)

對(duì)于尾部插入而言，ArrayList與LinkedList的性能幾乎是一致的

ArrayList頭部插入

源碼

add(int index, E element)方法，可以看到通過(guò)調(diào)用系統(tǒng)的數(shù)組復(fù)制方法來(lái)實(shí)現(xiàn)了元素的移動(dòng)。所以，插入的位置越靠前，需要移動(dòng)的元素就會(huì)越多

public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! // 把原來(lái)數(shù)組中的index位置開始的元素全部復(fù)制到index+1開始的位置（其實(shí)就是index后面的元素向后移動(dòng)一位） System.arraycopy(elementData, index, elementData, index + 1, size - index); // 插入元素 elementData[index] = element; size++; }

LinkedList頭部插入

源碼

add(int index, E element)方法，該方法先判斷是否是在尾部插入，如果是調(diào)用linkLast()方法，否則調(diào)用linkBefore()，那么是否真的就是需要重頭開始遍歷呢？我們一起來(lái)看看

public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }

在頭尾以外的位置插入元素當(dāng)然得找出這個(gè)位置在哪里，這里面的node()方法就是關(guān)鍵所在，這個(gè)函數(shù)的作用就是根據(jù)索引查找元素，但是它會(huì)先判斷index的位置，如果index比size的一半(size >> 1,右移運(yùn)算，相當(dāng)于除以2)要小，就從頭開始遍歷。否則，從尾部開始遍歷。從而可以知道，對(duì)于LinkedList來(lái)說(shuō)，操作的元素的位置越往中間靠攏，效率就越低

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

這個(gè)函數(shù)的工作就只是負(fù)責(zé)把元素插入到相應(yīng)的位置而已，關(guān)鍵的工作在node()方法中已經(jīng)完成了

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

總結(jié)

對(duì)于LinkedList來(lái)說(shuō)，頭部插入和尾部插入時(shí)間復(fù)雜度都是O(1) 但是對(duì)于ArrayList來(lái)說(shuō)，頭部的每一次插入都需要移動(dòng)size-1個(gè)元素，效率可想而知 但是如果都是在最中間的位置插入的話，ArrayList速度比LinkedList的速度快將近10倍

ArrayList、LinkedList查找

這就沒(méi)啥好說(shuō)的了，對(duì)于ArrayList，無(wú)論什么位置，都是直接通過(guò)索引定位到元素，時(shí)間復(fù)雜度O(1) 而對(duì)于LinkedList查找，其核心方法就是上面所說(shuō)的node()方法，所以頭尾查找速度極快，越往中間靠攏效率越低

到此這篇關(guān)于Java中LinkedList真的是查找慢增刪快 的文章就介紹到這了,更多相關(guān)Java LinkedList查找慢增刪快 內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！