LinkedList和ArrayList一樣是集合List的實(shí)現(xiàn)類，雖然較之ArrayList，其使用場(chǎng)景并不多，但同樣有用到的時(shí)候，那么接下來(lái)，我們來(lái)認(rèn)識(shí)一下它。

一. 定義一個(gè)LinkedList

public static void main(String[] args) { List<String> stringList = new LinkedList<>(); List<String> tempList = new ArrayList<>(); tempList.add('牛魔王'); tempList.add('蛟魔王'); tempList.add('鵬魔王'); tempList.add('獅駝王'); tempList.add('獼猴王'); tempList.add('禺賊王'); tempList.add('美猴王'); List<String> stringList2 = new LinkedList<>(tempList);}

上面代碼中采用了兩種方式來(lái)定義LinkedList，可以定義一個(gè)空集合，也可以傳遞已有的集合，將其轉(zhuǎn)化為L(zhǎng)inkedList。我們看一下源碼

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ transient int size = 0; /** * 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; /** * Constructs an empty list. */ public LinkedList() { } /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection’s * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public LinkedList(Collection<? extends E> c) { this(); addAll(c); }}

LinkedList繼承了AbstractSequentialList類，實(shí)現(xiàn)了List接口，AbstractSequentialList中已經(jīng)實(shí)現(xiàn)了很多方法，如get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)，這些方法是我們集合操作時(shí)使用最多的，不過(guò)這些方法在LinkedList中都已經(jīng)被重寫(xiě)了，而抽象方法在LinkedList中有了具體實(shí)現(xiàn)。因此我們回到LinkedList類

LinkedList類中定義了三個(gè)變量

針對(duì)first變量和last變量，我們看到是Node類的實(shí)體，這是一個(gè)靜態(tài)內(nèi)部類，關(guān)于靜態(tài)內(nèi)部類的講解，我們?cè)趕tatic五大應(yīng)用場(chǎng)景一章已經(jīng)有說(shuō)明

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

我們知道LinkedList是通過(guò)雙向鏈表實(shí)現(xiàn)的，而雙向鏈表就是通過(guò)Node類來(lái)體現(xiàn)的，類中通過(guò)item變量保存了當(dāng)前節(jié)點(diǎn)的值，通過(guò)next變量指向下一個(gè)節(jié)點(diǎn)，通過(guò)prev變量指向上一個(gè)節(jié)點(diǎn)。

二. LinkedList常用方法

1. get(int index)

我們知道隨機(jī)讀取元素不是LinkedList所擅長(zhǎng)的，讀取效率比起ArrayList也低得多，那么我來(lái)看一下為什么

public E get(int index) { checkElementIndex(index); return node(index).item;}/** * 返回一個(gè)指定索引的非空節(jié)點(diǎn). */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(int index)方法是通過(guò)node(int index)來(lái)實(shí)現(xiàn)的，它的實(shí)現(xiàn)機(jī)制是：

比較傳入的索引參數(shù)index與集合長(zhǎng)度size/2，如果是index小，那么從第一個(gè)順序循環(huán)，直到找到為止；如果index大，那么從最后一個(gè)倒序循環(huán)，直到找到為止。也就是說(shuō)越靠近中間的元素，調(diào)用get(int index方法遍歷的次數(shù)越多，效率也就越低，而且隨著集合的越來(lái)越大，get(int index)執(zhí)行性能也會(huì)指數(shù)級(jí)降低。因此在使用LinkedList的時(shí)候，我們不建議使用這種方式讀取數(shù)據(jù)，可以使用getFirst()，getLast()方法，將直接用到類中的first和last變量。

2. add(E e) 和 add(int index, E element)

大家都在說(shuō)LinkedList插入、刪除操作效率比較高，以stringList.add(“豬八戒”)為例來(lái)看到底發(fā)生了什么？

在LinkedList中我們找到add(E e)方法的源碼

public boolean add(E e) { linkLast(e); return true;}/** * 設(shè)置元素e為最后一個(gè)元素*/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++;}

很好理解：

情況1：假如stringList為空，那么添加進(jìn)來(lái)的node就是first，也是last，這個(gè)node的prev和next都為null;

情況2：假如stringList不為空，那么添加進(jìn)來(lái)的node就是last，node的prev指向以前的最后一個(gè)元素，node的next為null；同時(shí)以前的最后一個(gè)元素的next.

而如果通過(guò)stringList.add(1, “豬八戒”)這種方式將元素添加到集合中呢？

//在指定位置添加一個(gè)元素public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index));}/** * 在一個(gè)非空節(jié)點(diǎn)前插入一個(gè)元素 */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++;}

其實(shí)從代碼中看到和add(E e)的代碼實(shí)現(xiàn)沒(méi)有本質(zhì)區(qū)別，都是通過(guò)新建一個(gè)Node實(shí)體，同時(shí)指定其prev和next來(lái)實(shí)現(xiàn)，不同點(diǎn)在于需要調(diào)用node(int index)通過(guò)傳入的index來(lái)定位到要插入的位置，這個(gè)也是比較耗時(shí)的，參考上面的get(int index)方法。

其實(shí)看到這里，大家也都明白了。

LinkedList插入效率高是相對(duì)的，因?yàn)樗∪チ薃rrayList插入數(shù)據(jù)可能的數(shù)組擴(kuò)容和數(shù)據(jù)元素移動(dòng)時(shí)所造成的開(kāi)銷(xiāo)，但數(shù)據(jù)擴(kuò)容和數(shù)據(jù)元素移動(dòng)卻并不是時(shí)時(shí)刻刻都在發(fā)生的。

3. remove(Object o) 和 remove(int index)

這里removeFirst()和removeLast()就不多說(shuō)了，會(huì)用到類中定義的first和last變量，非常簡(jiǎn)單，我們看一下remove(Object o) 和 remove(int index)源碼

//刪除某個(gè)對(duì)象public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) {unlink(x);return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) {unlink(x);return true; } } } return false;}//刪除某個(gè)位置的元素public E remove(int index) { checkElementIndex(index); return unlink(node(index));}//刪除某節(jié)點(diǎn)，并將該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)（如果有）和下一個(gè)節(jié)點(diǎn)（如果有）關(guān)聯(lián)起來(lái)E unlink(Node<E> x) { 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;}

其實(shí)實(shí)現(xiàn)都非常簡(jiǎn)單，先找到要?jiǎng)h除的節(jié)點(diǎn)，remove(Object o)方法遍歷整個(gè)集合，通過(guò) == 或 equals方法進(jìn)行判斷；remove(int index)通過(guò)node(index)方法。

4. LinkedList遍歷

我們主要列舉一下三種常用的遍歷方式，

普通for循環(huán)，增強(qiáng)for循環(huán)，Iterator迭代器

public static void main(String[] args) { LinkedList<Integer> list = getLinkedList(); //通過(guò)快速隨機(jī)訪問(wèn)遍歷LinkedList listByNormalFor(list); //通過(guò)增強(qiáng)for循環(huán)遍歷LinkedList listByStrengThenFor(list); //通過(guò)快迭代器遍歷LinkedList listByIterator(list);}/** * 構(gòu)建一個(gè)LinkedList集合,包含元素50000個(gè) * @return */private static LinkedList<Integer> getLinkedList() { LinkedList list = new LinkedList(); for (int i = 0; i < 50000; i++){ list.add(i); } return list;}/** * 通過(guò)快速隨機(jī)訪問(wèn)遍歷LinkedList */private static void listByNormalFor(LinkedList<Integer> list) { // 記錄開(kāi)始時(shí)間 long start = System.currentTimeMillis(); int size = list.size(); for (int i = 0; i < size; i++) { list.get(i); } // 記錄用時(shí) long interval = System.currentTimeMillis() - start; System.out.println('listByNormalFor：' + interval + ' ms');}/** * 通過(guò)增強(qiáng)for循環(huán)遍歷LinkedList * @param list */public static void listByStrengThenFor(LinkedList<Integer> list){ // 記錄開(kāi)始時(shí)間 long start = System.currentTimeMillis(); for (Integer i : list) { } // 記錄用時(shí) long interval = System.currentTimeMillis() - start; System.out.println('listByStrengThenFor：' + interval + ' ms');}/** * 通過(guò)快迭代器遍歷LinkedList */private static void listByIterator(LinkedList<Integer> list) { // 記錄開(kāi)始時(shí)間 long start = System.currentTimeMillis(); for(Iterator iter = list.iterator(); iter.hasNext();) { iter.next(); } // 記錄用時(shí) long interval = System.currentTimeMillis() - start; System.out.println('listByIterator：' + interval + ' ms');}

執(zhí)行結(jié)果如下：

listByNormalFor：1067 mslistByStrengThenFor：3 mslistByIterator：2 ms

通過(guò)普通for循環(huán)隨機(jī)訪問(wèn)的方式執(zhí)行時(shí)間遠(yuǎn)遠(yuǎn)大于迭代器訪問(wèn)方式，這個(gè)我們可以理解，在前面的get(int index)方法中已經(jīng)有過(guò)說(shuō)明，那么為什么增強(qiáng)for循環(huán)能做到迭代器遍歷差不多的效率？

通過(guò)反編譯工具后得到如下代碼

public static void listByStrengThenFor(LinkedList<Integer> list) { long start = System.currentTimeMillis(); Integer localInteger; for (Iterator localIterator = list.iterator(); localIterator.hasNext(); localInteger = (Integer)localIterator.next()) {} long interval = System.currentTimeMillis() - start; System.out.println('listByStrengThenFor：' + interval + ' ms');}

很明顯了，增強(qiáng)for循環(huán)遍歷時(shí)也調(diào)用了迭代器Iterator，不過(guò)多了一個(gè)賦值的過(guò)程。

還有類似于pollFirst()，pollLast()取值后刪除的方法也能達(dá)到部分的遍歷效果。

三. 總結(jié)

本文基于java8從定義一個(gè)LinkList入手，逐步展開(kāi)，從源碼角度分析LinkedList雙向鏈表的結(jié)構(gòu)是如何構(gòu)建的，同時(shí)針對(duì)其常用方法進(jìn)行分析，包括get，add，remove以及常用的遍歷方法，并簡(jiǎn)單的說(shuō)明了它的插入、刪除操作為何相對(duì)高效，而取值操作性能相對(duì)較低，若有不對(duì)之處，請(qǐng)批評(píng)指正，望共同進(jìn)步，謝謝！

到此這篇關(guān)于Java集合 LinkedList的原理及使用詳解的文章就介紹到這了,更多相關(guān)Java LinkedList內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！