Java集合 LinkedList的原理及使用
1.LinkedList的概述
2.LinkedList的常用方法
3.LinkedList的三種便利方式
4.LinkedList的總結
1.LinkedList的概述
LinkedList和ArrayList一樣是集合List的實現類，雖然較之ArrayList，其使用場景并不多，但同樣有用到的時候，那么接下來，我們來認識一下它。
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); }上面代碼中采用了兩種方式來定義LinkedList，可以定義一個空集合，也可以傳遞已有的集合，將其轉化為LinkedList。我們看一下源碼
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類，實現了List接口，AbstractSequentialList中已經實現了很多方法，如get(int index)、set(int index, E element)、add(int index, E element)和 remove(int index)，這些方法是我們集合操作時使用最多的，不過這些方法在LinkedList中都已經被重寫了，而抽象方法在LinkedList中有了具體實現。因此我們回到LinkedList類
LinkedList類中定義了三個變量
size：集合的長度
first：雙向鏈表頭部節點
last：雙向鏈表尾部節點
針對first變量和last變量，我們看到是Node類的實體，這是一個靜態內部類，關于靜態內部類的講解，我們在static五大應用場景一章已經有說明
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是通過雙向鏈表實現的，而雙向鏈表就是通過Node類來體現的，類中通過item變量保存了當前節點的值，通過next變量指向下一個節點，通過prev變量指向上一個節點。
2.LinkedList常用方法
1.get方法
1 . get(int index)我們知道隨機讀取元素不是LinkedList所擅長的，讀取效率比起ArrayList也低得多，那么我來看一下為什么
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(int index)方法是通過node(int index)來實現的，它的實現機制是：
比較傳入的索引參數index與集合長度size/2，如果是index小，那么從第一個順序循環，直到找到為止；如果index大，那么從最后一個倒序循環，直到找到為止。也就是說越靠近中間的元素，調用get(int index)方法遍歷的次數越多，效率也就越低，而且隨著集合的越來越大，get(int index)執行性能也會指數級降低。因此在使用LinkedList的時候，我們不建議使用這種方式讀取數據，可以使用getFirst()，getLast()方法，將直接用到類中的first和last變量。
2.add方法
2 . add(E e)和 add(int index, E element)大家都在說LinkedList插入、刪除操作效率比較高，以
stringList.add(“豬八戒”)為例來看到底發生了什么？在LinkedList中我們找到add(E e)方法的源碼public boolean add(E e) {linkLast(e);return true; }/*** 設置元素e為最后一個元素 */ 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;elsel.next = newNode;size++;modCount++; }很好理解：
情況1：假如stringList為空，那么添加進來的node就是first，也是last，這個node的prev和next都為null;
情況2：假如stringList不為空，那么添加進來的node就是last，node的prev指向以前的最后一個元素，node的next為null；同時以前的最后一個元素的next.
而如果通過stringList.add(1, “豬八戒”)這種方式將元素添加到集合中呢？
//在指定位置添加一個元素 public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index)); }/*** 在一個非空節點前插入一個元素*/ 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;elsepred.next = newNode;size++;modCount++; }其實從代碼中看到和add(E e)的代碼實現沒有本質區別，都是通過新建一個Node實體，同時指定其prev和next來實現，不同點在于需要調用node(int index)通過傳入的index來定位到要插入的位置，這個也是比較耗時的，參考上面的get(int index)方法。
其實看到這里，大家也都明白了。
LinkedList插入效率高是相對的，因為它省去了ArrayList插入數據可能的數組擴容和數據元素移動時所造成的開銷，但數據擴容和數據元素移動卻并不是時時刻刻都在發生的。
3 .remove(Object o)和 remove(int index)這里removeFirst()和removeLast()就不多說了，會用到類中定義的first和last變量，非常簡單，我們看一下remove(Object o) 和 remove(int index)源碼
//刪除某個對象 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; } //刪除某個位置的元素 public E remove(int index) {checkElementIndex(index);return unlink(node(index)); } //刪除某節點，并將該節點的上一個節點（如果有）和下一個節點（如果有）關聯起來 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; } 其實實現都非常簡單，先找到要刪除的節點，remove(Object o)方法遍歷整個集合，通過 == 或 equals方法進行判斷；remove(int index)通過node(index)方法。4. LinkedList遍歷
我們主要列舉一下三種常用的遍歷方式，
普通for循環，增強for循環，Iterator迭代器
通過普通for循環隨機訪問的方式執行時間遠遠大于迭代器訪問方式，這個我們可以理解，在前面的get(int index)方法中已經有過說明，那么為什么增強for循環能做到迭代器遍歷差不多的效率？
通過反編譯工具后得到如下代碼：
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"); }很明顯了，增強for循環遍歷時也調用了迭代器Iterator，不過多了一個賦值的過程。
還有類似于pollFirst()，pollLast()取值后刪除的方法也能達到部分的遍歷效果。
本文參考：Java集合 LinkedList的原理及使用
總結
以上是生活随笔為你收集整理的Java集合 LinkedList的原理及使用的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： System.arraycopy()和
- 下一篇： Java集合入门总结