LinkedList簡介
LinkedList是基于雙向循環連結清單(從源碼中可以很容易看出)實作的，除了可以當做連結清單來操作外，它還可以當做棧、隊列和雙端隊列來使用。
LinkedList同樣是非線程安全的，隻在單線程下适合使用。
LinkedList實作了Serializable接口，是以它支援序列化，能夠通過序列化傳輸，實作了Cloneable接口，能被克隆。
LinkedList源碼
以下是linkedList源碼(加入簡單代碼注釋)：
package java.util;
public class LinkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable
{
// 連結清單的表頭，表頭不包含任何資料。Entry是個連結清單類資料結構。
private transient Entry header = new Entry(null, null, null);
// LinkedList中元素個數
private transient int size = 0;
// 預設構造函數：建立一個空的連結清單
public LinkedList() {
header.next = header.previous = header;
}
// 包含“集合”的構造函數:建立一個包含“集合”的LinkedList
public LinkedList(Collection extends E> c) {
this();
addAll(c);
}
// 擷取LinkedList的第一個元素
public E getFirst() {
if (size==0)
throw new NoSuchElementException();
// 由于LinkedList是雙向連結清單；連結清單的表頭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);
}
// 添加元素到起始位置
public void addFirst(E e) {
addBefore(e, header.next);
}
// 添加元素到最後一個位置
public void addLast(E e) {
addBefore(e, header);
}
// 是否包含元素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;
}
// 删除元素o
// 從連結清單開始查找，如存在元素(o)則删除該元素并傳回true；否則，傳回false。
public boolean remove(Object o) {
if (o==null) {
for (Entry e = header.next; e != header; e = e.next) {
if (e.element==null) {
remove(e);
return true;
}
}
} else {
for (Entry 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 successor = (index==size ? header : entry(index));
// 設定“目前要插入節點的前一個節點”
Entry predecessor = successor.previous;
// 将集合(c)全部插入雙向連結清單中
for (int i=0; i
Entry e = new Entry((E)a[i], successor, predecessor);
predecessor.next = e;
predecessor = e;
}
successor.previous = predecessor;
// 調整LinkedList的實際大小
size += numNew;
return true;
}
// 清空雙向連結清單
public void clear() {
Entry e = header.next;
// 從表頭開始，逐個向後周遊；對周遊到的節點執行一下操作;
// (01) 設定前一個節點為null
// (02) 設定目前節點的内容為null
// (03) 設定後一個節點為“新的目前節點”
while (e != header) {
Entry next = e.next;
e.next = e.previous = null;
e.element = null;
e = next;
}
header.next = header.previous = header;
size = 0;
modCount++;
}
// Positional Access Operations
// 傳回LinkedList指定位置的元素
public E get(int index) {
return entry(index).element;
}
// 設定index位置對應的節點的值為element
public E set(int index, E element) {
Entry e = entry(index);
E oldVal = e.element;
e.element = element;
return oldVal;
}
// 在index前添加節點，且節點的值為element
public 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 entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry 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;
}
// Search Operations
// 從前向後查找，傳回“值為對象(o)的節點對應的索引”
// 不存在就傳回-1
public 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)的節點對應的索引”
// 不存在就傳回-1
public 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;
}
// Queue operations.
// 傳回第一個節點
// 若LinkedList的大小為0,則傳回null
public E peek() {
if (size==0)
return null;
return getFirst();
}
// 傳回第一個節點
// 若LinkedList的大小為0,則抛出異常
public E element() {
return getFirst();
}
// 删除并傳回第一個節點
// 若LinkedList的大小為0,則傳回null
public E poll() {
if (size==0)
return null;
return removeFirst();
}
// 删除并傳回第一個節點
// 若LinkedList的大小為0,則抛出異常
public E remove() {
return removeFirst();
}
// 将e添加雙向連結清單末尾
public boolean offer(E e) {
return add(e);
}
// Deque operations
// 将e添加雙向連結清單開頭
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
// 将e添加雙向連結清單末尾
public boolean offerLast(E e) {
addLast(e);
return true;
}
// 傳回第一個節點
// 若LinkedList的大小為0,則傳回null
public E peekFirst() {
if (size==0)
return null;
return getFirst();
}
// 傳回最後一個節點
// 若LinkedList的大小為0,則傳回null
public E peekLast() {
if (size==0)
return null;
return getLast();
}
// 删除并傳回第一個節點
// 若LinkedList的大小為0,則傳回null
public E pollFirst() {
if (size==0)
return null;
return removeFirst();
}
// 删除并傳回最後一個節點
// 若LinkedList的大小為0,則傳回null
public 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)的節點
public boolean removeLastOccurrence(Object o) {
if (o==null) {
for (Entry e = header.previous; e != header; e = e.previous) {
if (e.element==null) {
remove(e);
return true;
}
}
} else {
for (Entry e = header.previous; e != header; e = e.previous) {
if (o.equals(e.element)) {
remove(e);
return true;
}
}
}
return false;
}
// 傳回“index到末尾的全部節點”對應的ListIterator對象(List疊代器)
public ListIterator listIterator(int index) {
return new ListItr(index);
}
// List疊代器
private class ListItr implements ListIterator {
// 上一次傳回的節點
private Entry lastReturned = header;
// 下一個節點
private Entry 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
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();
// next指向連結清單的下一個元素
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.element;
}
public boolean hasPrevious() {
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 lastNext = lastReturned.next;
try {
LinkedList.this.remove(lastReturned);
} catch (NoSuchElementException e) {
throw new IllegalStateException();
}
if (next==lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = header;
expectedModCount++;
}
// 設定目前節點為e
public 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 element;
// 下一節點
Entry next;
// 上一節點
Entry previous;
Entry(E element, Entry next, Entry previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
// 将節點(節點資料是e)添加到entry節點之前。
private Entry addBefore(E e, Entry entry) {
// 建立節點newEntry，将newEntry插入到節點e之前；并且設定newEntry的資料是e
Entry newEntry = new Entry(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) {
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 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的克隆對象。
public Object clone() {
LinkedList clone = null;
// 克隆一個LinkedList克隆對象
try {
clone = (LinkedList) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
// 建立LinkedList表頭節點
clone.header = new Entry(null, null, null);
clone.header.next = clone.header.previous = clone.header;
clone.size = 0;
clone.modCount = 0;
// 将連結清單中所有節點的資料都添加到克隆對象中
for (Entry e = header.next; e != header; e = e.next)
clone.add(e.element);
return clone;
}
// 傳回LinkedList的Object[]數組
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Entry e = header.next; e != header; e = e.next)
result[i++] = e.element;
return result;
}
// 傳回LinkedList的模闆數組。所謂模闆數組，即可以将T設為任意的資料類型
public 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);
int i = 0;
// 将連結清單中所有節點的資料都添加到數組a中
Object[] result = a;
for (Entry e = header.next; e != header; e = e.next)
result[i++] = e.element;
if (a.length > size)
a[size] = null;
return a;
}
private static final long serialVersionUID = 876323262645176354L;
// java.io.Serializable的寫入函數
// 将LinkedList的“容量，所有的元素值”都寫入到輸出流中
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.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 magic
s.defaultReadObject();
// 從輸入流中讀取“容量”
int size = s.readInt();
// 建立連結清單表頭節點
header = new Entry(null, null, null);
header.next = header.previous = header;
// 從輸入流中将“所有的元素值”并逐個添加到連結清單中
for (int i=0; i
addBefore((E)s.readObject(), header);
}
}
LinkedList詳細分析
一、什麼是連結清單
連結清單是由一系列非連續的節點組成的存儲結構，簡單分下類的話，連結清單又分為單向連結清單和雙向連結清單，而單向/雙向連結清單又可以分為循環連結清單和非循環連結清單，下面簡單就這四種連結清單進行圖解說明。
1.單向連結清單
單向連結清單就是通過每個結點的指針指向下一個結點進而連結起來的結構，最後一個節點的next指向null。
2.單向循環連結清單
單向循環連結清單和單向清單的不同是，最後一個節點的next不是指向null，而是指向head節點，形成一個“環”。
3.雙向連結清單
從名字就可以看出，雙向連結清單是包含兩個指針的，pre指向前一個節點，next指向後一個節點，但是第一個節點head的pre指向null，最後一個節點的tail指向null。
4.雙向循環連結清單
雙向循環連結清單和雙向連結清單的不同在于，第一個節點的pre指向最後一個節點，最後一個節點的next指向第一個節點，也形成一個“環”。而LinkedList就是基于雙向循環連結清單設計的。
二、定義
看一下LinkedList的定義部分：
public class LinkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable
可以看出LinkedList 繼承AbstractSequentialList 抽象類，實作了List，Deque，Cloneable，Serializable 幾個接口，AbstractSequentialList 繼承 AbstractList，是對其中方法的再抽象，其主要作用是最大限度地減少了實作受“連續通路”資料存儲(如連結清單)支援的此接口所需的工作，簡單說就是，如果需要快速的添加删除資料等，用AbstractSequentialList抽象類，若是需要快速随機的通路資料等用AbstractList抽象類。
Deque 是一個雙向隊列，也就是既可以先入先出，又可以先入後出，再直白一點就是既可以在頭部添加元素又在尾部添加元素，既可以在頭部擷取元素又可以在尾部擷取元素。看下Deque的源碼(已删除注釋)：
package java.util;
public interface Deque extends Queue {
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
void push(E e);
E pop();
boolean remove(Object o);
boolean contains(Object o);
public int size();
Iterator iterator();
Iterator descendingIterator();
}
三、内部類
LinkedList總共有三個内部類，ListItr，Entry和DescendingIterator，這三個内部類分别實作了List疊代器，雙向連結清單的節點所對應的資料結構和反向疊代器。
3.1内部類ListItr
源碼在上面的代碼中已經給出，這裡不再給出，分析一下
3.1.1構造函數
ListItr(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
if (index < (size >> 1)) {
next = header.next;
for (nextIndex=0; nextIndex
next = next.next;
} else {
next = header;
for (nextIndex=size; nextIndex>index; nextIndex--)
next = next.previous;
}
}
在這裡，這個構造函數隻做了一件事情，就是加速查找，重點是這句話if (index < 0 || index >size)如果給出的index索引小于雙向連結清單長度的一半，則從頭向後查找，如果大于，則從尾向前查找。
3.1.2成員變量
這個内部類當中的其他方法這裡就不介紹了，set()，get()，add()等等這些方法，在最開始的注釋代碼中寫的很清晰了，這裡說其中的一個成員變量private int expectedModCount = modCount;
首先來看一下這個modCount是個什麼東西：它是LinkedList繼承的父類的父類AbstractList中的一個成員變量protected transient int modCount = 0;它是用來記錄AbstractList結構性變化的次數。
在AbstractList的所有涉及結構變化的方法中都增加modCount的值，包括：add()、remove()、addAll()、removeRange()及clear()方法。這些方法每調用一次，modCount的值就加1。
而在這裡ListItr自己同時維護了一個expectedModCount，初始值是取的modCount，而當ListItr結構性變化的時候expectedModCount也會自動修改，包括next()，previous()，remove()，add(E e)等方法，而同樣在這些方法裡面的第一步都會去調用checkForComodification()這個方法進行修改的同步檢查，如果不同步将會抛出ConcurrentModificationException()這個異常。
3.2内部類Entry
3.2.1構造方法
Entry(E element, Entry next, Entry previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
這個構造函數使用到了三個參數，分别是目前節點值，下一節點和上一節點。
3.2.2addBefore(E e, Entry entry)
在這個内部類中，實作了将将節點e添加到entry節點之前的這個方法，這個方法在LinkedList所有添加操作相關的方法中都調用了，源碼：
private Entry addBefore(E e, Entry entry) {
Entry newEntry = new Entry(e, entry, entry.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
在這個方法一開始的地方就new了一個新的Entry對象出來，經典的雙向清單固定位置添加新節點，并且更新前驅結點的next域和後驅結點的previous域，并且将記錄操作數的modCount自增1。
3.3内部類DescendingIterator
反向疊代器實作類，這個類比較簡單，直接調用的ListItr的方法，在此不再贅述。
四、增加
public boolean add(E e) {
addBefore(e, header);
return true;
}
public void add(int index, E element) {
addBefore(element, (index==size ? header : entry(index)));
}
第一個add在尾部增加元素比較好了解：在header前添加元素e，header前就是最後一個結點，就是在最後一個結點的後面添加元素e；而第二個增加就不是那麼簡單了，同樣都是調用Entry的addBefore方法，第二個方法增加了一句判斷條件index==size ? header : entry(index)，這個條件實際上的意思就是如果index等于list元素個數，則在隊尾添加元素(header之前)，否則在index節點前添加元素。
到這裡可以發現一點，header作為雙向循環連結清單的頭結點是不儲存資料的，也就是說hedaer中的element永遠等于null。
public boolean addAll(Collection extends E> c) {
return addAll(size, 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 successor = (index==size ? header : entry(index));
Entry predecessor = successor.previous;
for (int i=0; i
Entry e = new Entry((E)a[i], successor, predecessor);
predecessor.next = e;
predecessor = e;
}
successor.previous = predecessor;
size += numNew;
return true;
}
第一個addAll方法是調用了第二個，仔細研究一下第二個addAll的方法，首先第一句話是越界檢查，第二局判斷是對添加的Collection做非0校驗，Entry successor = (index==size ? header : entry(index));這句話的含義是：擷取要插入index位置的下一個節點，如果index正好是lsit尾部的位置那麼下一個節點就是header，否則需要查找index位置的節點，而Entry predecessor = successor.previous;這句話的含義是：擷取要插入index位置的上一個節點，因為是插入，是以上一個點選就是未插入前下一個節點的上一個。
五、删除、修改、查詢
5.1删除
private E remove(Entry 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;
}
在這裡删除本質上的意思就是前一節點和後一節點組合在一起就好了，互相修改一下前驅結點和後置節點
5.2修改
public E set(int index, E element) {
Entry e = entry(index);
E oldVal = e.element;
e.element = element;
return oldVal;
}
set方法看起來簡單了很多，隻要修改該節點上的元素就好了。
5.3查找
private Entry entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry e = header;
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;
}
LinkedList是通過從header開始index計為0，然後一直往下周遊(next)，直到到底index位置。為了優化查詢效率，LinkedList采用了二分查找(這裡說的二分隻是簡單的一次二分)，判斷index與size中間位置的距離，采取從header向後還是向前查找。
基于雙向循環連結清單實作的LinkedList，通過索引Index的操作時低效的，index所對應的元素越靠近中間所費時間越長。而向連結清單兩端插入和删除元素則是非常高效的(如果不是兩端的話，都需要對連結清單進行周遊查找)。
六、是否包含
public boolean contains(Object o) {
return indexOf(o) != -1;
}
public 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;
}
public 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;
}
indexOf查詢元素位于容器的索引位置，都是需要對連結清單進行周遊操作，也都是低效的操作，慎用。
七、LinkedList實作的雙端隊列
public E peek() {
if (size==0)
return null;
return getFirst();
}
public E element() {
return getFirst();
}
public E poll() {
if (size==0)
return null;
return removeFirst();
}
public E remove() {
return removeFirst();
}
public boolean offer(E e) {
return add(e);
}
// Deque operations
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
public E peekFirst() {
if (size==0)
return null;
return getFirst();
}
public E peekLast() {
if (size==0)
return null;
return getLast();
}
public E pollFirst() {
if (size==0)
return null;
return removeFirst();
}
public E pollLast() {
if (size==0)
return null;
return removeLast();
}
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}
很簡單，邏輯都是基于上面講的連結清單操作的。
八、總結
8.1從源碼中很明顯可以看出，LinkedList的實作是基于雙向循環連結清單的，且頭結點中不存放資料
8.2注意兩個不同的構造方法。無參構造方法直接建立一個僅包含head節點的空連結清單，包含Collection的構造方法，先調用無參構造方法建立一個空連結清單，而後将Collection中的資料加入到連結清單的尾部後面。
8.3在查找和删除某元素時，源碼中都劃分為該元素為null和不為null兩種情況來處理，LinkedList中允許元素為null。
8.4LinkedList是基于連結清單實作的，是以不存在容量不足的問題，是以這裡沒有擴容的方法。
8.5注意源碼中的Entry entry(int index)方法。該方法傳回雙向連結清單中指定位置處的節點，而連結清單中是沒有下标索引的，要指定位置出的元素，就要周遊該連結清單，從源碼的實作中，我們看到這裡有一個加速動作。源碼中先将index與長度size的一半比較，如果indexsize/2，就隻從位置size往前周遊到位置index處。這樣可以減少一部分不必要的周遊，進而提高一定的效率(實際上效率還是很低)。
8.6注意連結清單類對應的資料結構Entry。
8.7LinkedList是基于連結清單實作的，是以插入删除效率高，查找效率低(雖然有一個加速動作)。
8.8要注意源碼中還實作了棧和隊列的操作方法，是以也可以作為棧、隊列和雙端隊列來使用。
————————————————————————————————————————————————————
參考資料：