LinkedList簡介

LinkedList 是一個繼承于AbstractSequentialList的雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。
LinkedList 實現 List 接口，能對它進行隊列操作。
LinkedList 實現 Deque 接口，即能將LinkedList當作雙端隊列使用。
LinkedList 實現了Cloneable接口，即覆蓋了函數clone()，能克隆。
LinkedList 實現java.io.Serializable接口，這意味著LinkedList支持序列化，能通過序列化去傳輸。
LinkedList 是非同步的。

LinkedList構造函數

// 默認構造函數 LinkedList()// 創建一個LinkedList，保護Collection中的全部元素。 LinkedList(Collection<? extends E> collection)

LinkedList的API

LinkedList的API boolean add(E object) void add(int location, E object) boolean addAll(Collection<? extends E> collection) boolean addAll(int location, Collection<? extends E> collection) void addFirst(E object) void addLast(E object) void clear() Object clone() boolean contains(Object object) Iterator<E> descendingIterator() E element() E get(int location) E getFirst() E getLast() int indexOf(Object object) int lastIndexOf(Object object) ListIterator<E> listIterator(int location) boolean offer(E o) boolean offerFirst(E e) boolean offerLast(E e) E peek() E peekFirst() E peekLast() E poll() E pollFirst() E pollLast() E pop() void push(E e) E remove() E remove(int location) boolean remove(Object object) E removeFirst() boolean removeFirstOccurrence(Object o) E removeLast() boolean removeLastOccurrence(Object o) E set(int location, E object) int size() <T> T[] toArray(T[] contents) Object[] toArray()

AbstractSequentialList簡介

在介紹LinkedList的源碼之前，先介紹一下AbstractSequentialList。畢竟，LinkedList是AbstractSequentialList的子類。

AbstractSequentialList 實現了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)這些函數。這些接口都是隨機訪問List的，LinkedList是雙向鏈表；既然它繼承于AbstractSequentialList，就相當于已經實現了“get(int index)這些接口”。

此外，我們若需要通過AbstractSequentialList自己實現一個列表，只需要擴展此類，并提供 listIterator() 和 size() 方法的實現即可。若要實現不可修改的列表，則需要實現列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。

LinkedList數據結構

java.lang.Object

? java.util.AbstractCollection<E>

? java.util.AbstractList<E>

? java.util.AbstractSequentialList<E>

? java.util.LinkedList<E>

public class LinkedList<E>

extends AbstractSequentialList<E>

implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}

LinkedList與Collection關系如下圖：

LinkedList的本質是雙向鏈表。

(01) LinkedList繼承于AbstractSequentialList，并且實現了Dequeue接口。

(02) LinkedList包含兩個重要的成員：header和size。

header是雙向鏈表的表頭，它是雙向鏈表節點所對應的類Entry的實例。Entry中包含成員變量： previous, next, element。其中，previous是該節點的上一個節點，next是該節點的下一個節點，element是該節點所包含的值。

size是雙向鏈表中節點的個數。

LinkedList源碼解析

LinkedList實際上是通過雙向鏈表去實現的。既然是雙向鏈表，那么它的順序訪問會非常高效，而隨機訪問效率比較低。

既然LinkedList是通過雙向鏈表的，但是它也實現了List接口{也就是說，它實現了get(int location)、remove(int location)等“根據索引值來獲取、刪除節點的函數”}。LinkedList是如何實現List的這些接口的，如何將“雙向鏈表和索引值聯系起來的”？

實際原理非常簡單，它就是通過一個計數索引值來實現的。例如，當我們調用get(int location)時，首先會比較“location”和“雙向鏈表長度的1/2”；若前者大，則從鏈表頭開始往后查找，直到location位置；否則，從鏈表末尾開始先前查找，直到location位置。

這就是“雙線鏈表和索引值聯系起來”的方法。

package java.util;public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable {// 鏈表的表頭，表頭不包含任何數據。Entry是個鏈表類數據結構。private transient Entry<E> header = new Entry<E>(null, null, null);// LinkedList中元素個數private transient int size = 0;// 默認構造函數：創建一個空的鏈表public LinkedList() {header.next = header.previous = header;}// 包含“集合”的構造函數:創建一個包含“集合”的LinkedListpublic LinkedList(Collection<? extends E> c) {this();addAll(c);}// 獲取LinkedList的第一個元素public E getFirst() {if (size==0)throw new NoSuchElementException();// 鏈表的表頭header中不包含數據。// 這里返回header所指下一個節點所包含的數據。return header.next.element;}// 獲取LinkedList的最后一個元素public E getLast() {if (size==0)throw new NoSuchElementException();// 由于LinkedList是雙向鏈表；而表頭header不包含數據。// 因而，這里返回表頭header的前一個節點所包含的數據。return header.previous.element;}// 刪除LinkedList的第一個元素public E removeFirst() {return remove(header.next);}// 刪除LinkedList的最后一個元素public E removeLast() {return remove(header.previous);}// 將元素添加到LinkedList的起始位置public void addFirst(E e) {addBefore(e, header.next);}// 將元素添加到LinkedList的結束位置public void addLast(E e) {addBefore(e, header);}// 判斷LinkedList是否包含元素(o)public boolean contains(Object o) {return indexOf(o) != -1;}// 返回LinkedList的大小public int size() {return size;}// 將元素(E)添加到LinkedList中public boolean add(E e) {// 將節點(節點數據是e)添加到表頭(header)之前。// 即，將節點添加到雙向鏈表的末端。addBefore(e, header);return true;}// 從LinkedList中刪除元素(o)// 從鏈表開始查找，如存在元素(o)則刪除該元素并返回true；// 否則，返回false。public boolean remove(Object o) {if (o==null) {// 若o為null的刪除情況for (Entry<E> e = header.next; e != header; e = e.next) {if (e.element==null) {remove(e);return true;}}} else {// 若o不為null的刪除情況for (Entry<E> e = header.next; e != header; e = e.next) {if (o.equals(e.element)) {remove(e);return true;}}}return false;}// 將“集合(c)”添加到LinkedList中。// 實際上，是從雙向鏈表的末尾開始，將“集合(c)”添加到雙向鏈表中。public boolean addAll(Collection<? extends E> c) {return addAll(size, c);}// 從雙向鏈表的index開始，將“集合(c)”添加到雙向鏈表中。public boolean addAll(int index, Collection<? extends E> c) {if (index < 0 || index > size)throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);Object[] a = c.toArray();// 獲取集合的長度int numNew = a.length;if (numNew==0)return false;modCount++;// 設置“當前要插入節點的后一個節點”Entry<E> successor = (index==size ? header : entry(index));// 設置“當前要插入節點的前一個節點”Entry<E> predecessor = successor.previous;// 將集合(c)全部插入雙向鏈表中for (int i=0; i<numNew; i++) {Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);predecessor.next = e;predecessor = e;}successor.previous = predecessor;// 調整LinkedList的實際大小size += numNew;return true;}// 清空雙向鏈表public void clear() {Entry<E> e = header.next;// 從表頭開始，逐個向后遍歷；對遍歷到的節點執行一下操作：// (01) 設置前一個節點為null// (02) 設置當前節點的內容為null// (03) 設置后一個節點為“新的當前節點”while (e != header) {Entry<E> next = e.next;e.next = e.previous = null;e.element = null;e = next;}header.next = header.previous = header;// 設置大小為0size = 0;modCount++;}// 返回LinkedList指定位置的元素public E get(int index) {return entry(index).element;}// 設置index位置對應的節點的值為elementpublic E set(int index, E element) {Entry<E> e = entry(index);E oldVal = e.element;e.element = element;return oldVal;}// 在index前添加節點，且節點的值為elementpublic void add(int index, E element) {addBefore(element, (index==size ? header : entry(index)));}// 刪除index位置的節點public E remove(int index) {return remove(entry(index));}// 獲取雙向鏈表中指定位置的節點private Entry<E> entry(int index) {if (index < 0 || index >= size)throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);Entry<E> e = header;// 獲取index處的節點。// 若index < 雙向鏈表長度的1/2,則從前先后查找;// 否則，從后向前查找。if (index < (size >> 1)) {for (int i = 0; i <= index; i++)e = e.next;} else {for (int i = size; i > index; i--)e = e.previous;}return e;}// 從前向后查找，返回“值為對象(o)的節點對應的索引”// 不存在就返回-1public int indexOf(Object o) {int index = 0;if (o==null) {for (Entry e = header.next; e != header; e = e.next) {if (e.element==null)return index;index++;}} else {for (Entry e = header.next; e != header; e = e.next) {if (o.equals(e.element))return index;index++;}}return -1;}// 從后向前查找，返回“值為對象(o)的節點對應的索引”// 不存在就返回-1public int lastIndexOf(Object o) {int index = size;if (o==null) {for (Entry e = header.previous; e != header; e = e.previous) {index--;if (e.element==null)return index;}} else {for (Entry e = header.previous; e != header; e = e.previous) {index--;if (o.equals(e.element))return index;}}return -1;}// 返回第一個節點// 若LinkedList的大小為0,則返回nullpublic E peek() {if (size==0)return null;return getFirst();}// 返回第一個節點// 若LinkedList的大小為0,則拋出異常public E element() {return getFirst();}// 刪除并返回第一個節點// 若LinkedList的大小為0,則返回nullpublic E poll() {if (size==0)return null;return removeFirst();}// 將e添加雙向鏈表末尾public boolean offer(E e) {return add(e);}// 將e添加雙向鏈表開頭public boolean offerFirst(E e) {addFirst(e);return true;}// 將e添加雙向鏈表末尾public boolean offerLast(E e) {addLast(e);return true;}// 返回第一個節點// 若LinkedList的大小為0,則返回nullpublic E peekFirst() {if (size==0)return null;return getFirst();}// 返回最后一個節點// 若LinkedList的大小為0,則返回nullpublic E peekLast() {if (size==0)return null;return getLast();}// 刪除并返回第一個節點// 若LinkedList的大小為0,則返回nullpublic E pollFirst() {if (size==0)return null;return removeFirst();}// 刪除并返回最后一個節點// 若LinkedList的大小為0,則返回nullpublic E pollLast() {if (size==0)return null;return removeLast();}// 將e插入到雙向鏈表開頭public void push(E e) {addFirst(e);}// 刪除并返回第一個節點public E pop() {return removeFirst();}// 從LinkedList開始向后查找，刪除第一個值為元素(o)的節點// 從鏈表開始查找，如存在節點的值為元素(o)的節點，則刪除該節點public boolean removeFirstOccurrence(Object o) {return remove(o);}// 從LinkedList末尾向前查找，刪除第一個值為元素(o)的節點// 從鏈表開始查找，如存在節點的值為元素(o)的節點，則刪除該節點public boolean removeLastOccurrence(Object o) {if (o==null) {for (Entry<E> e = header.previous; e != header; e = e.previous) {if (e.element==null) {remove(e);return true;}}} else {for (Entry<E> e = header.previous; e != header; e = e.previous) {if (o.equals(e.element)) {remove(e);return true;}}}return false;}// 返回“index到末尾的全部節點”對應的ListIterator對象(List迭代器)public ListIterator<E> listIterator(int index) {return new ListItr(index);}// List迭代器private class ListItr implements ListIterator<E> {// 上一次返回的節點private Entry<E> lastReturned = header;// 下一個節點private Entry<E> next;// 下一個節點對應的索引值private int nextIndex;// 期望的改變計數。用來實現fail-fast機制。private int expectedModCount = modCount;// 構造函數。// 從index位置開始進行迭代ListItr(int index) {// index的有效性處理if (index < 0 || index > size)throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);// 若 “index 小于 ‘雙向鏈表長度的一半’”，則從第一個元素開始往后查找；// 否則，從最后一個元素往前查找。if (index < (size >> 1)) {next = header.next;for (nextIndex=0; nextIndex<index; nextIndex++)next = next.next;} else {next = header;for (nextIndex=size; nextIndex>index; nextIndex--)next = next.previous;}}// 是否存在下一個元素public boolean hasNext() {// 通過元素索引是否等于“雙向鏈表大小”來判斷是否達到最后。return nextIndex != size;}// 獲取下一個元素public E next() {checkForComodification();if (nextIndex == size)throw new NoSuchElementException();lastReturned = next;// next指向鏈表的下一個元素next = next.next;nextIndex++;return lastReturned.element;}// 是否存在上一個元素public boolean hasPrevious() {// 通過元素索引是否等于0，來判斷是否達到開頭。return nextIndex != 0;}// 獲取上一個元素public E previous() {if (nextIndex == 0)throw new NoSuchElementException();// next指向鏈表的上一個元素lastReturned = next = next.previous;nextIndex--;checkForComodification();return lastReturned.element;}// 獲取下一個元素的索引public int nextIndex() {return nextIndex;}// 獲取上一個元素的索引public int previousIndex() {return nextIndex-1;}// 刪除當前元素。// 刪除雙向鏈表中的當前節點public void remove() {checkForComodification();Entry<E> lastNext = lastReturned.next;try {LinkedList.this.remove(lastReturned);} catch (NoSuchElementException e) {throw new IllegalStateException();}if (next==lastReturned)next = lastNext;elsenextIndex--;lastReturned = header;expectedModCount++;}// 設置當前節點為epublic void set(E e) {if (lastReturned == header)throw new IllegalStateException();checkForComodification();lastReturned.element = e;}// 將e添加到當前節點的前面public void add(E e) {checkForComodification();lastReturned = header;addBefore(e, next);nextIndex++;expectedModCount++;}// 判斷 “modCount和expectedModCount是否相等”，依次來實現fail-fast機制。final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}}// 雙向鏈表的節點所對應的數據結構。// 包含3部分：上一節點，下一節點，當前節點值。private static class Entry<E> {// 當前節點所包含的值E element;// 下一個節點Entry<E> next;// 上一個節點Entry<E> previous;/*** 鏈表節點的構造函數。* 參數說明：* element —— 節點所包含的數據* next —— 下一個節點* previous —— 上一個節點*/Entry(E element, Entry<E> next, Entry<E> previous) {this.element = element;this.next = next;this.previous = previous;}}// 將節點(節點數據是e)添加到entry節點之前。private Entry<E> addBefore(E e, Entry<E> entry) {// 新建節點newEntry，將newEntry插入到節點e之前；并且設置newEntry的數據是eEntry<E> newEntry = new Entry<E>(e, entry, entry.previous);newEntry.previous.next = newEntry;newEntry.next.previous = newEntry;// 修改LinkedList大小size++;// 修改LinkedList的修改統計數：用來實現fail-fast機制。modCount++;return newEntry;}// 將節點從鏈表中刪除private E remove(Entry<E> e) {if (e == header)throw new NoSuchElementException();E result = e.element;e.previous.next = e.next;e.next.previous = e.previous;e.next = e.previous = null;e.element = null;size--;modCount++;return result;}// 反向迭代器public Iterator<E> descendingIterator() {return new DescendingIterator();}// 反向迭代器實現類。private class DescendingIterator implements Iterator {final ListItr itr = new ListItr(size());// 反向迭代器是否下一個元素。// 實際上是判斷雙向鏈表的當前節點是否達到開頭public boolean hasNext() {return itr.hasPrevious();}// 反向迭代器獲取下一個元素。// 實際上是獲取雙向鏈表的前一個節點public E next() {return itr.previous();}// 刪除當前節點public void remove() {itr.remove();}}// 返回LinkedList的Object[]數組public Object[] toArray() {// 新建Object[]數組Object[] result = new Object[size];int i = 0;// 將鏈表中所有節點的數據都添加到Object[]數組中for (Entry<E> e = header.next; e != header; e = e.next)result[i++] = e.element;return result;}// 返回LinkedList的模板數組。所謂模板數組，即可以將T設為任意的數據類型public <T> T[] toArray(T[] a) {// 若數組a的大小 < LinkedList的元素個數(意味著數組a不能容納LinkedList中全部元素)// 則新建一個T[]數組，T[]的大小為LinkedList大小，并將該T[]賦值給a。if (a.length < size)a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);// 將鏈表中所有節點的數據都添加到數組a中int i = 0;Object[] result = a;for (Entry<E> e = header.next; e != header; e = e.next)result[i++] = e.element;if (a.length > size)a[size] = null;return a;}// 克隆函數。返回LinkedList的克隆對象。public Object clone() {LinkedList<E> clone = null;// 克隆一個LinkedList克隆對象try {clone = (LinkedList<E>) super.clone();} catch (CloneNotSupportedException e) {throw new InternalError();}// 新建LinkedList表頭節點clone.header = new Entry<E>(null, null, null);clone.header.next = clone.header.previous = clone.header;clone.size = 0;clone.modCount = 0;// 將鏈表中所有節點的數據都添加到克隆對象中for (Entry<E> e = header.next; e != header; e = e.next)clone.add(e.element);return clone;}// java.io.Serializable的寫入函數// 將LinkedList的“容量，所有的元素值”都寫入到輸出流中private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException {// Write out any hidden serialization magics.defaultWriteObject();// 寫入“容量”s.writeInt(size);// 將鏈表中所有節點的數據都寫入到輸出流中for (Entry e = header.next; e != header; e = e.next)s.writeObject(e.element);}// java.io.Serializable的讀取函數：根據寫入方式反向讀出// 先將LinkedList的“容量”讀出，然后將“所有的元素值”讀出private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {// Read in any hidden serialization magics.defaultReadObject();// 從輸入流中讀取“容量”int size = s.readInt();// 新建鏈表表頭節點header = new Entry<E>(null, null, null);header.next = header.previous = header;// 從輸入流中將“所有的元素值”并逐個添加到鏈表中for (int i=0; i<size; i++)addBefore((E)s.readObject(), header);}}

總結：

(01)LinkedList實際上是通過雙向鏈表去實現的。

它包含一個非常重要的內部類：Entry。Entry是雙向鏈表節點所對應的數據結構，它包括的屬性有：當前節點所包含的值，上一個節點，下一個節點。

(02) 從LinkedList的實現方式中可以發現，它不存在LinkedList容量不足的問題。

(03)LinkedList的克隆函數，即是將全部元素克隆到一個新的LinkedList對象中。

(04)LinkedList實現java.io.Serializable。當寫入到輸出流時，先寫入“容量”，再依次寫入“每一個節點保護的值”；當讀出輸入流時，先讀取“容量”，再依次讀取“每一個元素”。

(05) 由于LinkedList實現了Deque，而Deque接口定義了在雙端隊列兩端訪問元素的方法。提供插入、移除和檢查元素的方法。每種方法都存在兩種形式：一種形式在操作失敗時拋出異常，另一種形式返回一個特殊值（null 或 false，具體取決于操作）

總結起來如下表格：

第一個元素（頭部） 最后一個元素（尾部）
拋出異常 特殊值 拋出異常 特殊值插入 addFirst(e) offerFirst(e) addLast(e) offerLast(e)移除 removeFirst() pollFirst() removeLast() pollLast()檢查 getFirst() peekFirst() getLast() peekLast()

(06) LinkedList可以作為FIFO(先進先出)的隊列，作為FIFO的隊列時，下表的方法等價：

隊列方法 等效方法

add(e) addLast(e)

offer(e) offerLast(e)

remove() removeFirst()

poll() pollFirst()

element() getFirst()

peek() peekFirst()

(07) LinkedList可以作為LIFO(后進先出)的棧，作為LIFO的棧時，下表的方法等價：

棧方法 等效方法

push(e) addFirst(e)

pop() removeFirst()

peek() peekFirst()

LinkedList遍歷方式

LinkedList支持多種遍歷方式。建議不要采用隨機訪問的方式去遍歷LinkedList，而采用逐個遍歷的方式。

for(Iterator iter = list.iterator(); iter.hasNext();)iter.next();

(02) 通過快速隨機訪問遍歷LinkedList

int size = list.size(); for (int i=0; i<size; i++) {list.get(i); }

(03) 通過另外一種for循環來遍歷LinkedList

for (Integer integ:list) ;

(04) 通過pollFirst()來遍歷LinkedList

while(list.pollFirst() != null);

(05) 通過pollLast()來遍歷LinkedList

while(list.pollLast() != null);

(06) 通過removeFirst()來遍歷LinkedList

try {while(list.removeFirst() != null); } catch (NoSuchElementException e) { }

(07) 通過removeLast()來遍歷LinkedList

try {while(list.removeLast() != null); } catch (NoSuchElementException e) { }

測試這些遍歷方式效率的代碼如下：

import java.util.List; import java.util.Iterator; import java.util.LinkedList; import java.util.NoSuchElementException;/** @desc 測試LinkedList的幾種遍歷方式和效率** @author skywang*/ public class LinkedListThruTest {public static void main(String[] args) {// 通過Iterator遍歷LinkedListiteratorLinkedListThruIterator(getLinkedList()) ;// 通過快速隨機訪問遍歷LinkedListiteratorLinkedListThruForeach(getLinkedList()) ;// 通過for循環的變種來訪問遍歷LinkedListiteratorThroughFor2(getLinkedList()) ;// 通過PollFirst()遍歷LinkedListiteratorThroughPollFirst(getLinkedList()) ;// 通過PollLast()遍歷LinkedListiteratorThroughPollLast(getLinkedList()) ;// 通過removeFirst()遍歷LinkedListiteratorThroughRemoveFirst(getLinkedList()) ;// 通過removeLast()遍歷LinkedListiteratorThroughRemoveLast(getLinkedList()) ;}private static LinkedList getLinkedList() {LinkedList llist = new LinkedList();for (int i=0; i<100000; i++)llist.addLast(i);return llist;}/*** 通過快迭代器遍歷LinkedList*/private static void iteratorLinkedListThruIterator(LinkedList<Integer> list) {if (list == null)return ;// 記錄開始時間long start = System.currentTimeMillis();for(Iterator iter = list.iterator(); iter.hasNext();)iter.next();// 記錄結束時間long end = System.currentTimeMillis();long interval = end - start;System.out.println("iteratorLinkedListThruIterator：" + interval+" ms");}/*** 通過快速隨機訪問遍歷LinkedList*/private static void iteratorLinkedListThruForeach(LinkedList<Integer> list) {if (list == null)return ;// 記錄開始時間long start = System.currentTimeMillis();int size = list.size();for (int i=0; i<size; i++) {list.get(i);}// 記錄結束時間long end = System.currentTimeMillis();long interval = end - start;System.out.println("iteratorLinkedListThruForeach：" + interval+" ms");}/*** 通過另外一種for循環來遍歷LinkedList*/private static void iteratorThroughFor2(LinkedList<Integer> list) {if (list == null)return ;// 記錄開始時間long start = System.currentTimeMillis();for (Integer integ:list);// 記錄結束時間long end = System.currentTimeMillis();long interval = end - start;System.out.println("iteratorThroughFor2：" + interval+" ms");}/*** 通過pollFirst()來遍歷LinkedList*/private static void iteratorThroughPollFirst(LinkedList<Integer> list) {if (list == null)return ;// 記錄開始時間long start = System.currentTimeMillis();while(list.pollFirst() != null);// 記錄結束時間long end = System.currentTimeMillis();long interval = end - start;System.out.println("iteratorThroughPollFirst：" + interval+" ms");}/*** 通過pollLast()來遍歷LinkedList*/private static void iteratorThroughPollLast(LinkedList<Integer> list) {if (list == null)return ;// 記錄開始時間long start = System.currentTimeMillis();while(list.pollLast() != null);// 記錄結束時間long end = System.currentTimeMillis();long interval = end - start;System.out.println("iteratorThroughPollLast：" + interval+" ms");}/*** 通過removeFirst()來遍歷LinkedList*/private static void iteratorThroughRemoveFirst(LinkedList<Integer> list) {if (list == null)return ;// 記錄開始時間long start = System.currentTimeMillis();try {while(list.removeFirst() != null);} catch (NoSuchElementException e) {}// 記錄結束時間long end = System.currentTimeMillis();long interval = end - start;System.out.println("iteratorThroughRemoveFirst：" + interval+" ms");}/*** 通過removeLast()來遍歷LinkedList*/private static void iteratorThroughRemoveLast(LinkedList<Integer> list) {if (list == null)return ;// 記錄開始時間long start = System.currentTimeMillis();try {while(list.removeLast() != null);} catch (NoSuchElementException e) {}// 記錄結束時間long end = System.currentTimeMillis();long interval = end - start;System.out.println("iteratorThroughRemoveLast：" + interval+" ms");}} iteratorLinkedListThruIterator：8 ms iteratorLinkedListThruForeach：3724 ms iteratorThroughFor2：5 ms iteratorThroughPollFirst：8 ms iteratorThroughPollLast：6 ms iteratorThroughRemoveFirst：2 ms iteratorThroughRemoveLast：2 ms

由此可見，遍歷LinkedList時，使用removeFist()或removeLast()效率最高。但用它們遍歷時，會刪除原始數據；若單純只讀取，而不刪除，應該使用第3種遍歷方式。無論如何，千萬不要通過隨機訪問去遍歷LinkedList！

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的java 双向链表_java集合类之LinkedList的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。