LinkedList簡介

? ???????????首先看看LinkedList與Collection的關(guān)系：

LinkedList的繼承關(guān)系如下：

?LinkedList是一個(gè)繼承與AbatractSequentialList的雙向鏈表。它也可以被當(dāng)作堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行操作。

?LinkedList實(shí)現(xiàn)了List接口，能對(duì)它進(jìn)行隊(duì)列操作。

? LinkedList實(shí)現(xiàn)了Deque接口，即能將LinkedList當(dāng)作雙端隊(duì)列使用。

?LinkedList實(shí)現(xiàn)了java.io.Serializable接口，這意味著LinkedList支持序列化，能通過序列化去傳輸。

? LinkedList是非同步的。

??????? 這里插一句，簡單說一下AbstractSequentialList，因?yàn)長inkedList是其子類。

??????? AbstractSequentialList實(shí)現(xiàn)了get(int index)、set(int index, E element)、add(int index, E element)和remove(int index)這些方法。這些接口都是隨機(jī)訪問List的，LinkedList是雙向鏈表，既然它繼承與AbstractSequentialList，就相當(dāng)于已經(jīng)實(shí)現(xiàn)了“get(int index)”這些接口，可以支持隨機(jī)訪問了。

??????? 此外，如果我們需要通過AbstractSequentialList實(shí)現(xiàn)一個(gè)自己的列表，只需要擴(kuò)展此類，并提供listIterator()和size()方法的實(shí)現(xiàn)即可。若要實(shí)現(xiàn)不可修改的列表，則需要實(shí)現(xiàn)列表迭代器的hashNext、next、hashPrevious、previous和index方法即可。

????下面先總覽一下LinkedList的構(gòu)造函數(shù)和API:

? LinkedList包含三個(gè)重要的成員：first、last和size：first是雙向鏈表的表頭，last是雙向鏈表的尾節(jié)點(diǎn)，size是雙向鏈表中的節(jié)點(diǎn)個(gè)數(shù)。

LinkedList源碼分析（基于JDK1.7）

package java.util;

/*雙向鏈表*

/public class LinkedListextends AbstractSequentialListimplements List, Deque, Cloneable, java.io.Serializable{

/*** 這里先說一下transient關(guān)鍵字的用法：* 一個(gè)對(duì)象只要實(shí)現(xiàn)了Serilizable接口，這個(gè)對(duì)象就可以被序列化，java的這種序列化模式為開發(fā)者提供了很多便利，可以不必關(guān)系具體序列化的過程，* 只要這個(gè)類實(shí)現(xiàn)了Serilizable接口，這個(gè)的所有屬性和方法都會(huì)自動(dòng)序列化。但是有種情況是有些屬性是不需要序列號(hào)的，所以就用到這個(gè)關(guān)鍵字。* 只需要實(shí)現(xiàn)Serilizable接口，將不需要序列化的屬性前添加關(guān)鍵字transient，序列化對(duì)象的時(shí)候，這個(gè)屬性就不會(huì)序列化到指定的目的地中。*/?

?transient int size = 0;?

//LinkedList中元素的個(gè)數(shù)?

?transient Nodefirst;?

//鏈表的頭結(jié)點(diǎn) transient Nodelast; //鏈表的尾節(jié)點(diǎn) public LinkedList() { //默認(rèn)構(gòu)造函數(shù)，創(chuàng)建一個(gè)空鏈表 } //按照c中的元素生成一個(gè)LinkedList public LinkedList(Collection? extends Ec) { this(); addAll(c); //將c中的元素添加到空鏈表的尾部 } /***************************** 添加頭結(jié)點(diǎn) ********************************/public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { final Nodef = first; //f指向頭結(jié)點(diǎn)//生成一個(gè)新結(jié)點(diǎn)e，其前向指針為null，后向指針為f final NodenewNode = new Node<>(null, e, f); first = newNode; //first指向新生成的結(jié)點(diǎn)，f保存著老的頭結(jié)點(diǎn)信息 if (f == null) last = newNode; //如果f為null，則表示整個(gè)鏈表目前是空的，則尾結(jié)點(diǎn)也指向新結(jié)點(diǎn) else f.prev = newNode; size++; modCount++; //修改次數(shù)+1 } /****************** 添加尾節(jié)點(diǎn)，與上面添加頭結(jié)點(diǎn)原理一樣 ******************/public void addLast(E e) { linkLast(e); } void linkLast(E e) { final Nodel = last; final NodenewNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } /****************** 在非空節(jié)點(diǎn)succ之前插入新節(jié)點(diǎn)e ************************/ void linkBefore(E e, Nodesucc) { // assert succ != null; //外界調(diào)用需保證succ不為null,否則程序會(huì)拋出空指針異常 final Nodepred = succ.prev; //生成一個(gè)新結(jié)點(diǎn)e,其前向指針指向pred，后向指針指向succ final NodenewNode = new Node<>(pred, e, succ); succ.prev = newNode; //succ的前向指針指向newNode if (pred == null)//如果pred為null，則表示succ為頭結(jié)點(diǎn)，此時(shí)頭結(jié)點(diǎn)指向最新生成的結(jié)點(diǎn)newNode first = newNode; else//pred的后向指針指向新生成的結(jié)點(diǎn)，此時(shí)已經(jīng)完成了結(jié)點(diǎn)的插入操作 pred.next = newNode; size++; modCount++; } /*********************** 刪除頭結(jié)點(diǎn),并返回頭結(jié)點(diǎn)的值 *********************/ public E removeFirst() { final Nodef = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); //private方法 } private E unlinkFirst(Nodef) { // assert f == first && f != null; //需確保f為頭結(jié)點(diǎn),且鏈表不為Null final E element = f.item; //獲得節(jié)點(diǎn)的值 final Nodenext = f.next; //獲得頭結(jié)點(diǎn)下一個(gè)節(jié)點(diǎn) f.item = null; f.next = null; // help GC first = next; if (next == null)//如果next為null，則表示f為last結(jié)點(diǎn)，此時(shí)鏈表即為空鏈表 last = null; else//修改next的前向指針，因?yàn)閒irst結(jié)點(diǎn)的前向指針為null next.prev = null; size--; modCount++; return element; } /********************** 刪除尾節(jié)點(diǎn)，并返回尾節(jié)點(diǎn)的值 ********************/public E removeLast() { final Nodel = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); //private方法 } private E unlinkLast(Nodel) { // assert l == last && l != null; final E element = l.item; final Nodeprev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; } /******************** 刪除為空節(jié)點(diǎn)x，并返回該節(jié)點(diǎn)的值 ******************/ E unlink(Nodex) { // assert x != null; //需確保x不為null，否則后續(xù)操作會(huì)拋出空指針異常 final E element = x.item; final Nodenext = x.next; final Nodeprev = x.prev; if (prev == null) {//如果prev為空，則x結(jié)點(diǎn)為first結(jié)點(diǎn)，此時(shí)first結(jié)點(diǎn)指向next結(jié)點(diǎn)（x的后向結(jié)點(diǎn)） first = next; } else { prev.next = next; //x的前向結(jié)點(diǎn)的后向指針指向x的后向結(jié)點(diǎn) x.prev = null; //釋放x的前向指針 } if (next == null) {//如果next結(jié)點(diǎn)為空，則x結(jié)點(diǎn)為尾部結(jié)點(diǎn)，此時(shí)last結(jié)點(diǎn)指向prev結(jié)點(diǎn)(x的前向結(jié)點(diǎn)) last = prev; } else { next.prev = prev; //x的后向結(jié)點(diǎn)的前向指針指向x的前向結(jié)點(diǎn) x.next = null; //釋放x的后向指針 } x.item = null; //釋放x的值節(jié)點(diǎn),此時(shí)x節(jié)點(diǎn)可以完全被GC回收 size--; modCount++; return element; } /********************** 獲得頭結(jié)點(diǎn)的值 ********************/ public E getFirst() { final Nodef = first; if (f == null) throw new NoSuchElementException(); return f.item; } /********************** 獲得尾結(jié)點(diǎn)的值 ********************/ public E getLast() { final Nodel = last; if (l == null) throw new NoSuchElementException(); return l.item; } /*************** 判斷元素（值為o）是否在鏈表中 *************/ public boolean contains(Object o) { return indexOf(o) != -1; //定位元素 } //返回元素個(gè)數(shù) public int size() { return size; } //向鏈表尾部添加元素e public boolean add(E e) { linkLast(e); return true; } /*************** 刪除值為o的元素 *************/ public boolean remove(Object o) { if (o == null) { for (Nodex = first; x != null; x = x.next) { if (x.item == null) { //找到即返回 unlink(x); return true; } } } else {//o不為空 for (Nodex = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } /*************** 將集合e中所有元素添加到鏈表中 *************/ public boolean addAll(Collection? extends Ec) { return addAll(size, c); }//從index開始，向后添加的 public boolean addAll(int index, Collection? extends Ec) { checkPositionIndex(index); //判斷index是否越界 Object[] a = c.toArray(); //將集合c轉(zhuǎn)換為數(shù)組 int numNew = a.length; if (numNew == 0) return false; Nodepred, succ; if (index == size) {//即index個(gè)節(jié)點(diǎn)在尾節(jié)點(diǎn)后面 succ = null; pred = last; //pred指向尾節(jié)點(diǎn) } else { succ = node(index); //succ指向第index個(gè)節(jié)點(diǎn) pred = succ.prev; //pred指向succ的前向節(jié)點(diǎn) }//for循環(huán)結(jié)束后，a里面的元素都添加到當(dāng)前鏈表里了，向后添加 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; NodenewNode = new Node<>(pred, e, null); if (pred == null) first = newNode; //如果pred為null，則succ為頭結(jié)點(diǎn) else pred.next = newNode; //pred的后向指針指向新節(jié)點(diǎn) pred = newNode; //pred指向新節(jié)點(diǎn)，即往后移動(dòng)一個(gè)節(jié)點(diǎn)，用于下一次循環(huán) } if (succ == null) { //succ為null表示index為尾節(jié)點(diǎn)之后 last = pred; } else {//pred表示所有元素添加好之后的最后那個(gè)節(jié)點(diǎn)，此時(shí)pred的后向指針指向之前記錄的節(jié)點(diǎn)，即index處的節(jié)點(diǎn) pred.next = succ; succ.prev = pred; //之前記錄的結(jié)點(diǎn)指向添加元素之后的最后結(jié)點(diǎn) } size += numNew; modCount++; return true; } /******************** 清空鏈表 *************************/ public void clear() { for (Nodex = first; x != null; ) { Nodenext = x.next; x.item = null; //釋放值結(jié)點(diǎn)，便于GC回收 x.next = null; //釋放前向指針 x.prev = null; //釋放前后指針 x = next; //后向遍歷 } first = last = null; //釋放頭尾節(jié)點(diǎn) size = 0; modCount++; } /******************* Positional Access Operations ***********************/ //獲得第index個(gè)節(jié)點(diǎn)的值 public E get(int index) { checkElementIndex(index); return node(index).item; } //設(shè)置第index元素的值 public E set(int index, E element) { checkElementIndex(index); Nodex = node(index); E oldVal = x.item; x.item = element; return oldVal; } //在index個(gè)節(jié)點(diǎn)之前添加新的節(jié)點(diǎn) public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } //刪除第index個(gè)節(jié)點(diǎn) public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } //判斷index是否為鏈表中的元素下標(biāo) private boolean isElementIndex(int index) { return index >= 0 && index < size; } //判斷index是否為鏈表中的元素下標(biāo)。。。包含了size private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //定位index處的節(jié)點(diǎn) Nodenode(int index) { // assert isElementIndex(index);//index> 1)) { Nodex = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //index>=size/2時(shí)，從尾開始找 Nodex = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } /*************************** Search Operations *************************/ //返回首次出現(xiàn)指定元素值o的節(jié)點(diǎn)索引 public int indexOf(Object o) { int index = 0; if (o == null) { for (Nodex = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Nodex = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; //沒有則返回-1 } //返回最后一次出現(xiàn)指定元素值o的節(jié)點(diǎn)索引 public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Nodex = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Nodex = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; } /***************************** Queue operations ***********************/ //下面是與棧和隊(duì)列相關(guān)的操作了 //實(shí)現(xiàn)棧的操作，返回第一個(gè)元素的值 public E peek() { final Nodef = first; return (f == null) ? null : f.item; //不刪除 } //實(shí)現(xiàn)隊(duì)列操作，返回第一個(gè)節(jié)點(diǎn) public E element() { return getFirst(); } //實(shí)現(xiàn)棧的操作，彈出第一個(gè)節(jié)點(diǎn) public E poll() { final Nodef = first; return (f == null) ? null : unlinkFirst(f); //刪除 } //實(shí)現(xiàn)隊(duì)列操作，刪除節(jié)點(diǎn) public E remove() { return removeFirst(); } //添加節(jié)點(diǎn) public boolean offer(E e) { return add(e); } /************************* Deque operations **********************/ //下面都是和雙端隊(duì)列相關(guān)的操作了//添加頭結(jié)點(diǎn) public boolean offerFirst(E e) { addFirst(e); return true; } //添加尾節(jié)點(diǎn) public boolean offerLast(E e) { addLast(e); return true; } //返回頭結(jié)點(diǎn)的值 public E peekFirst() { final Nodef = first; return (f == null) ? null : f.item; } //返回尾節(jié)點(diǎn)的值 public E peekLast() { final Nodel = last; return (l == null) ? null : l.item; } //彈出頭結(jié)點(diǎn) public E pollFirst() { final Nodef = first; return (f == null) ? null : unlinkFirst(f); //刪除 } //彈出尾節(jié)點(diǎn) public E pollLast() { final Nodel = last; return (l == null) ? null : unlinkLast(l); //刪除 } //棧操作，添加頭結(jié)點(diǎn) public void push(E e) { addFirst(e); } //棧操作，刪除頭結(jié)點(diǎn) public E pop() { return removeFirst(); } //刪除第一次出現(xiàn)o的節(jié)點(diǎn) public boolean removeFirstOccurrence(Object o) { return remove(o); } //刪除最后一次出現(xiàn)o的節(jié)點(diǎn) public boolean removeLastOccurrence(Object o) { if (o == null) { for (Nodex = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); return true; } } } else { for (Nodex = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } /************************* ListIterator ***********************/ public ListIteratorlistIterator(int index) { checkPositionIndex(index); return new ListItr(index); //ListItr是一個(gè)雙向迭代器 } //實(shí)現(xiàn)雙向迭代器 private class ListItr implements ListIterator{ private NodelastReturned = null;//記錄當(dāng)前節(jié)點(diǎn)信息 private Nodenext; //當(dāng)前節(jié)點(diǎn)的后向節(jié)點(diǎn) private int nextIndex; //當(dāng)前節(jié)點(diǎn)的索引 private int expectedModCount = modCount; //修改次數(shù) ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; //記錄當(dāng)前節(jié)點(diǎn) next = next.next; //向后移動(dòng)一個(gè)位置 nextIndex++; //節(jié)點(diǎn)索引+1 return lastReturned.item; //返回當(dāng)前節(jié)點(diǎn)的值 } public boolean hasPrevious() { return nextIndex > 0; }//返回前向節(jié)點(diǎn)的值 public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item; } public int nextIndex() { //返回當(dāng)前節(jié)點(diǎn)的索引 return nextIndex; } public int previousIndex() { //返回當(dāng)前節(jié)點(diǎn)的前一個(gè)索引 return nextIndex - 1; } public void remove() { //刪除當(dāng)前節(jié)點(diǎn) checkForComodification(); if (lastReturned == null) throw new IllegalStateException(); NodelastNext = lastReturned.next; unlink(lastReturned); if (next == lastReturned) next = lastNext; else nextIndex--; lastReturned = null; expectedModCount++; } public void set(E e) { //設(shè)置當(dāng)前節(jié)點(diǎn)的值 if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; }//在當(dāng)前節(jié)點(diǎn)前面插入新節(jié)點(diǎn)信息 public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount++; } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } private static class Node{ E item; Nodenext; Nodeprev; Node(Nodeprev, E element, Nodenext) { this.item = element; this.next = next; this.prev = prev; } } //返回前向迭代器 public IteratordescendingIterator() { return new DescendingIterator(); } //通過ListItr.previous來提供前向迭代器，方向與原來相反 private class DescendingIterator implements Iterator{ private final ListItr itr = new ListItr(size()); public boolean hasNext() { return itr.hasPrevious(); } public E next() { return itr.previous(); } public void remove() { itr.remove(); } } @SuppressWarnings("unchecked") private LinkedListsuperClone() { try { return (LinkedList) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } } //克隆操作，執(zhí)行淺拷貝，只復(fù)制引用，沒有復(fù)制引用指向的內(nèi)存 public Object clone() { LinkedListclone = superClone(); // Put clone into "virgin" state clone.first = clone.last = null; clone.size = 0; clone.modCount = 0; // Initialize clone with our elements for (Nodex = first; x != null; x = x.next) clone.add(x.item); return clone; } /*************************** toArray ****************************/ //返回LinkedList的Object[]數(shù)組public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Nodex = first; x != null; x = x.next) result[i++] = x.item; return result; } //返回LinkedList的模板數(shù)組，存儲(chǔ)在a中 @SuppressWarnings("unchecked") publicT[] toArray(T[] a) { if (a.length < size)//如果a的大小 < LinkedList的元素個(gè)數(shù)，意味著數(shù)組a不能容納LinkedList的全部元素//則新建一個(gè)T[]數(shù)組，T[]的大小為LinkedList大小，并將T[]賦給a a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size);//如果a大小夠容納LinkedList的全部元素 int i = 0; Object[] result = a; for (Nodex = first; x != null; x = x.next) result[i++] = x.item; if (a.length > size) a[size] = null; return a; } private static final long serialVersionUID = 876323262645176354L; /************************* Serializable **************************/ //java.io.Serializable的寫入函數(shù) //將LinkedList的“容量，所有元素值”寫入到輸出流中 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic s.defaultWriteObject(); // Write out size s.writeInt(size); //寫入容量 // Write out all elements in the proper order. for (Node x = first; x != null; x = x.next) //寫入所有數(shù)據(jù)

? ? ? ? ? ? s.writeObject(x.item);

? ? }

? ? //java.io.Serializable的讀取函數(shù)：根據(jù)寫入方式反向讀出

? ? //先將LinkedList的“容量”讀出，然后將“所有元素值”讀出

? ? @SuppressWarnings("unchecked")

? ? private void readObject(java.io.ObjectInputStream s)

? ? ? ? throws java.io.IOException, ClassNotFoundException {

? ? ? ? // Read in any hidden serialization magic

? ? ? ? s.defaultReadObject();

? ? ? ? // Read in size

? ? ? ? int size = s.readInt(); //讀出容量

? ? ? ? // Read in all elements in the proper order.

? ? ? ? for (int i = 0; i < size; i++) //讀出所有元素值

? ? ? ? ? ? linkLast((E)s.readObject());

? ? }

}

總結(jié)一下：

??????? 1）. LinkedList是通過雙向鏈表去實(shí)現(xiàn)的。

??????? 2）.?從LinkedList的實(shí)現(xiàn)方式中可以看出，它不存在容量不足的問題，因?yàn)槭擎湵怼?/p>

?3）. LinkedList實(shí)現(xiàn)java.io.Serializable的方式。當(dāng)寫入到輸出流時(shí)，先寫入“容量”，再依次寫出“每一個(gè)元素”；當(dāng)讀出輸入流時(shí)，先讀取“容量”，再依次讀取“每一個(gè)元素”。

??????? 4）. LinkdedList的克隆函數(shù)，即是將全部元素克隆到一個(gè)新的LinkedList中。

??????? 5）.?由于LinkedList實(shí)現(xiàn)了Deque，而Deque接口定義了在雙端隊(duì)列兩端訪問元素的方法。提供插入、移除和檢查元素的方法。

??????? 6）. LinkedList可以作為FIFO（先進(jìn)先出）的隊(duì)列，作為FIFO的隊(duì)列時(shí)，下標(biāo)的方法等價(jià)：

LinkedList遍歷方式

? LinkedList支持多種遍歷方式，建議不要采用隨機(jī)訪問的方式去遍歷LinkedList，而采用逐個(gè)遍歷的方式。下面我們來看看每種遍歷方式：

1）.?通過Iterator迭代器遍歷

??? 2）.?通過快速隨機(jī)訪問遍歷

?? 3）.?通過for循環(huán)遍歷

??? 4）. 通過pollFirst()或pollLast()來遍歷

??? 5）.?通過removeFirst()或removeLast()來遍歷

由此可見，遍歷LinkedList時(shí)，使用removeFirst()或removeLast()效率最高。但是用它們遍歷會(huì)刪除原始數(shù)據(jù)；若只是單純的取數(shù)據(jù)，而不刪除，建議用迭代器方式或者for-each方式。

??????? 無論如何，千萬不要用隨機(jī)訪問去遍歷LinkedList！除非腦門兒被驢給踢了... ...

??????? LinkedList源碼就討論這么多，如果錯(cuò)誤，歡迎留言指正~