LinkedList簡介

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

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

?LinkedList是一個繼承與AbatractSequentialList的雙向鏈表臼疫。它也可以被當(dāng)作堆棧、隊列或雙端隊列進行操作艇抠。

?LinkedList實現(xiàn)了List接口樟氢，能對它進行隊列操作。

? LinkedList實現(xiàn)了Deque接口镇饺，即能將LinkedList當(dāng)作雙端隊列使用乎莉。

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

? LinkedList是非同步的。

??????? 這里插一句监右，簡單說一下AbstractSequentialList边灭，因為LinkedList是其子類。

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

??????? 此外，如果我們需要通過AbstractSequentialList實現(xiàn)一個自己的列表频轿，只需要擴展此類垂涯，并提供listIterator()和size()方法的實現(xiàn)即可烁焙。若要實現(xiàn)不可修改的列表，則需要實現(xiàn)列表迭代器的hashNext耕赘、next骄蝇、hashPrevious、previous和index方法即可操骡。

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

? LinkedList包含三個重要的成員：first九火、last和size：first是雙向鏈表的表頭，last是雙向鏈表的尾節(jié)點册招，size是雙向鏈表中的節(jié)點個數(shù)岔激。

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

package java.util;

/*雙向鏈表*

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

/*** 這里先說一下transient關(guān)鍵字的用法：* 一個對象只要實現(xiàn)了Serilizable接口，這個對象就可以被序列化是掰，java的這種序列化模式為開發(fā)者提供了很多便利虑鼎，可以不必關(guān)系具體序列化的過程，* 只要這個類實現(xiàn)了Serilizable接口键痛，這個的所有屬性和方法都會自動序列化炫彩。但是有種情況是有些屬性是不需要序列號的，所以就用到這個關(guān)鍵字絮短。* 只需要實現(xiàn)Serilizable接口媒楼，將不需要序列化的屬性前添加關(guān)鍵字transient，序列化對象的時候戚丸，這個屬性就不會序列化到指定的目的地中。*/?

?transient int size = 0;?

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

?transient Nodefirst;?

//鏈表的頭結(jié)點 transient Nodelast; //鏈表的尾節(jié)點 public LinkedList() { //默認構(gòu)造函數(shù)扔嵌，創(chuàng)建一個空鏈表 } //按照c中的元素生成一個LinkedList public LinkedList(Collection? extends Ec) { this(); addAll(c); //將c中的元素添加到空鏈表的尾部 } /***************************** 添加頭結(jié)點 ********************************/public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { final Nodef = first; //f指向頭結(jié)點//生成一個新結(jié)點e限府，其前向指針為null，后向指針為f final NodenewNode = new Node<>(null, e, f); first = newNode; //first指向新生成的結(jié)點痢缎，f保存著老的頭結(jié)點信息 if (f == null) last = newNode; //如果f為null胁勺，則表示整個鏈表目前是空的，則尾結(jié)點也指向新結(jié)點 else f.prev = newNode; size++; modCount++; //修改次數(shù)+1 } /****************** 添加尾節(jié)點独旷，與上面添加頭結(jié)點原理一樣 ******************/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é)點succ之前插入新節(jié)點e ************************/ void linkBefore(E e, Nodesucc) { // assert succ != null; //外界調(diào)用需保證succ不為null,否則程序會拋出空指針異常 final Nodepred = succ.prev; //生成一個新結(jié)點e,其前向指針指向pred署穗，后向指針指向succ final NodenewNode = new Node<>(pred, e, succ); succ.prev = newNode; //succ的前向指針指向newNode if (pred == null)//如果pred為null，則表示succ為頭結(jié)點嵌洼，此時頭結(jié)點指向最新生成的結(jié)點newNode first = newNode; else//pred的后向指針指向新生成的結(jié)點案疲，此時已經(jīng)完成了結(jié)點的插入操作 pred.next = newNode; size++; modCount++; } /*********************** 刪除頭結(jié)點,并返回頭結(jié)點的值 *********************/ 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é)點,且鏈表不為Null final E element = f.item; //獲得節(jié)點的值 final Nodenext = f.next; //獲得頭結(jié)點下一個節(jié)點 f.item = null; f.next = null; // help GC first = next; if (next == null)//如果next為null，則表示f為last結(jié)點麻养，此時鏈表即為空鏈表 last = null; else//修改next的前向指針褐啡，因為first結(jié)點的前向指針為null next.prev = null; size--; modCount++; return element; } /********************** 刪除尾節(jié)點，并返回尾節(jié)點的值 ********************/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é)點x鳖昌，并返回該節(jié)點的值 ******************/ E unlink(Nodex) { // assert x != null; //需確保x不為null备畦，否則后續(xù)操作會拋出空指針異常 final E element = x.item; final Nodenext = x.next; final Nodeprev = x.prev; if (prev == null) {//如果prev為空低飒，則x結(jié)點為first結(jié)點，此時first結(jié)點指向next結(jié)點（x的后向結(jié)點） first = next; } else { prev.next = next; //x的前向結(jié)點的后向指針指向x的后向結(jié)點 x.prev = null; //釋放x的前向指針 } if (next == null) {//如果next結(jié)點為空懂盐，則x結(jié)點為尾部結(jié)點褥赊，此時last結(jié)點指向prev結(jié)點(x的前向結(jié)點) last = prev; } else { next.prev = prev; //x的后向結(jié)點的前向指針指向x的前向結(jié)點 x.next = null; //釋放x的后向指針 } x.item = null; //釋放x的值節(jié)點,此時x節(jié)點可以完全被GC回收 size--; modCount++; return element; } /********************** 獲得頭結(jié)點的值 ********************/ public E getFirst() { final Nodef = first; if (f == null) throw new NoSuchElementException(); return f.item; } /********************** 獲得尾結(jié)點的值 ********************/ 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; //定位元素 } //返回元素個數(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個節(jié)點在尾節(jié)點后面 succ = null; pred = last; //pred指向尾節(jié)點 } else { succ = node(index); //succ指向第index個節(jié)點 pred = succ.prev; //pred指向succ的前向節(jié)點 }//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é)點 else pred.next = newNode; //pred的后向指針指向新節(jié)點 pred = newNode; //pred指向新節(jié)點类垫，即往后移動一個節(jié)點司光，用于下一次循環(huán) } if (succ == null) { //succ為null表示index為尾節(jié)點之后 last = pred; } else {//pred表示所有元素添加好之后的最后那個節(jié)點，此時pred的后向指針指向之前記錄的節(jié)點悉患，即index處的節(jié)點 pred.next = succ; succ.prev = pred; //之前記錄的結(jié)點指向添加元素之后的最后結(jié)點 } size += numNew; modCount++; return true; } /******************** 清空鏈表 *************************/ public void clear() { for (Nodex = first; x != null; ) { Nodenext = x.next; x.item = null; //釋放值結(jié)點残家，便于GC回收 x.next = null; //釋放前向指針 x.prev = null; //釋放前后指針 x = next; //后向遍歷 } first = last = null; //釋放頭尾節(jié)點 size = 0; modCount++; } /******************* Positional Access Operations ***********************/ //獲得第index個節(jié)點的值 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個節(jié)點之前添加新的節(jié)點 public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } //刪除第index個節(jié)點 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é)點 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時，從尾開始找 Nodex = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } /*************************** Search Operations *************************/ //返回首次出現(xiàn)指定元素值o的節(jié)點索引 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é)點索引 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 ***********************/ //下面是與棧和隊列相關(guān)的操作了 //實現(xiàn)棧的操作陪捷，返回第一個元素的值 public E peek() { final Nodef = first; return (f == null) ? null : f.item; //不刪除 } //實現(xiàn)隊列操作回窘，返回第一個節(jié)點 public E element() { return getFirst(); } //實現(xiàn)棧的操作，彈出第一個節(jié)點 public E poll() { final Nodef = first; return (f == null) ? null : unlinkFirst(f); //刪除 } //實現(xiàn)隊列操作市袖，刪除節(jié)點 public E remove() { return removeFirst(); } //添加節(jié)點 public boolean offer(E e) { return add(e); } /************************* Deque operations **********************/ //下面都是和雙端隊列相關(guān)的操作了//添加頭結(jié)點 public boolean offerFirst(E e) { addFirst(e); return true; } //添加尾節(jié)點 public boolean offerLast(E e) { addLast(e); return true; } //返回頭結(jié)點的值 public E peekFirst() { final Nodef = first; return (f == null) ? null : f.item; } //返回尾節(jié)點的值 public E peekLast() { final Nodel = last; return (l == null) ? null : l.item; } //彈出頭結(jié)點 public E pollFirst() { final Nodef = first; return (f == null) ? null : unlinkFirst(f); //刪除 } //彈出尾節(jié)點 public E pollLast() { final Nodel = last; return (l == null) ? null : unlinkLast(l); //刪除 } //棧操作啡直，添加頭結(jié)點 public void push(E e) { addFirst(e); } //棧操作，刪除頭結(jié)點 public E pop() { return removeFirst(); } //刪除第一次出現(xiàn)o的節(jié)點 public boolean removeFirstOccurrence(Object o) { return remove(o); } //刪除最后一次出現(xiàn)o的節(jié)點 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是一個雙向迭代器 } //實現(xiàn)雙向迭代器 private class ListItr implements ListIterator{ private NodelastReturned = null;//記錄當(dāng)前節(jié)點信息 private Nodenext; //當(dāng)前節(jié)點的后向節(jié)點 private int nextIndex; //當(dāng)前節(jié)點的索引 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é)點 next = next.next; //向后移動一個位置 nextIndex++; //節(jié)點索引+1 return lastReturned.item; //返回當(dāng)前節(jié)點的值 } public boolean hasPrevious() { return nextIndex > 0; }//返回前向節(jié)點的值 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é)點的索引 return nextIndex; } public int previousIndex() { //返回當(dāng)前節(jié)點的前一個索引 return nextIndex - 1; } public void remove() { //刪除當(dāng)前節(jié)點 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é)點的值 if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; }//在當(dāng)前節(jié)點前面插入新節(jié)點信息 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ù)組舷丹，存儲在a中 @SuppressWarnings("unchecked") publicT[] toArray(T[] a) { if (a.length < size)//如果a的大小 < LinkedList的元素個數(shù)，意味著數(shù)組a不能容納LinkedList的全部元素//則新建一個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是通過雙向鏈表去實現(xiàn)的症概。

??????? 2）.?從LinkedList的實現(xiàn)方式中可以看出，它不存在容量不足的問題早芭，因為是鏈表穴豫。

?3）. LinkedList實現(xiàn)java.io.Serializable的方式。當(dāng)寫入到輸出流時，先寫入“容量”精肃，再依次寫出“每一個元素”秤涩；當(dāng)讀出輸入流時，先讀取“容量”司抱，再依次讀取“每一個元素”筐眷。

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

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

??????? 6）. LinkedList可以作為FIFO（先進先出）的隊列，作為FIFO的隊列時溶锭，下標(biāo)的方法等價：

LinkedList遍歷方式

? LinkedList支持多種遍歷方式宝恶，建議不要采用隨機訪問的方式去遍歷LinkedList，而采用逐個遍歷的方式趴捅。下面我們來看看每種遍歷方式：

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

??? 2）.?通過快速隨機訪問遍歷

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

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

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

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

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

??????? LinkedList源碼就討論這么多额各，如果錯誤，歡迎留言指正~