【Java1.7.5集合源碼剖析】LinkedList源碼剖析

LinkedList特點 

1.内部通過雙向連結清單存儲資料 

2.插入、删除不需要移動元素，隻需要修改指針 

3.實作了隊列、雙端隊列、棧 

4.插入、删除操作比較多的時候，推薦使用 

5.擷取指定index位置的值效率低（雖然有一個加速動作）

6.LinkedList同樣是非線程安全的，隻在單線程下适合使用。

7、無參構造方法直接建立一個僅包含head節點的空連結清單，包含Collection的構造方法，先調用無參構造方法建立一個空連結清單，而後将Collection中的資料加入到連結清單的尾部後面。

8.LinkedList是基于連結清單實作的，是以不存在容量不足的問題，是以這裡沒有擴容的方法。

繼承AbstractSequentialList抽象類 

實作List、Deque、Cloneable、java.io.Serializable 

Deque是雙端隊列接口

public class LinkedList
   
    
    extends AbstractSequentialList
    
     
    implements List
     
      , Deque
      
       , Cloneable, java.io.Serializable
{
	// 元素個數
    transient int size = 0;

    //第一個節點
    transient Node
       
         first; //最後一個節點 transient Node
        
          last; //空構造器 public LinkedList() { } //集合c中元素加入的LinkedList中 public LinkedList(Collection
          c) { this(); // 集合c中元素加入的LinkedList中 addAll(c); } //插入節點e作為第一個節點 private void linkFirst(E e) { final Node
         
           f = first; final Node
          
            newNode = new Node<>(null, e, f); // f 前插入 值為e的節點 first = newNode;// first指針指向目前新的節點 if (f == null) // f 為空所有沒有元素，則last指向目前新的節點 last = newNode; else f.prev = newNode; // 建立f節點的前驅節點 size++; // 個數+1 modCount++; } //插入節點e作為最後一個節點 void linkLast(E e) { final Node
           
             l = last; final Node
            
              newNode = new Node<>(l, e, null); // l 後 插入節點值為 e的節點 last = newNode; // last指針指向目前新的最後節點 if (l == null) // null 說明沒有元素，first指向目前新的節點 first = newNode; else l.next = newNode; // 建立l 的後繼節點 size++; modCount++; } //succ 前插入節點 void linkBefore(E e, Node
             
               succ) { final Node
              
                pred = succ.prev; final Node
               
                 newNode = new Node<>(pred, e, succ); // 建立節點 newNode.next = succ newNode.prev = pred succ.prev = newNode; // 建立前驅 if (pred == null) // 空時候 first = newNode; else // 建立後繼 pred.next = newNode; size++; modCount++; } //删除第一個節點，并傳回節點值 private E unlinkFirst(Node
                
                  f) { final E element = f.item; final Node
                 
                   next = f.next; // 後繼節點 f.item = null; f.next = null; // 垃圾回收 first = next; // 更新first if (next == null) // 空 last = null; else next.prev = null; // 前驅為null size--; modCount++; return element; } // 删除最後一個節點，并傳回節點值 private E unlinkLast(Node
                  
                    l) { final E element = l.item; final Node
                   
                     prev = l.prev; // 前驅節點 l.item = null; l.prev = null; // 垃圾回收 last = prev; // 更新last if (prev == null) // null first = null; else // 後繼為null prev.next = null; size--; modCount++; return element; } //删除節點 x 并傳回節點值 E unlink(Node
                    
                      x) { final E element = x.item; final Node
                     
                       next = x.next; // next final Node
                      
                        prev = x.prev; // prev if (prev == null) { // prev == null ,first = next first = next; } else { // prev.next = next prev.next = next; x.prev = null; // 垃圾回收 } if (next == null) { // next== null ，last = prev last = prev; } else { // next.prev = prev next.prev = prev; x.next = null; // 垃圾回收 } x.item = null; // 垃圾回收 size--; modCount++; return element; } //擷取第一個節點值 public E getFirst() { final Node
                       
                         f = first; //将第一個指派 if (f == null) throw new NoSuchElementException(); return f.item; } //擷取最後一個節點值 public E getLast() { final Node
                        
                          l = last;//将最後一個指派 if (l == null) throw new NoSuchElementException(); return l.item; } //删除第一個節點，并傳回其值，可抛出異常 public E removeFirst() { final Node
                         
                           f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } //删除最後一個節點，并傳回節點值，可抛出異常 public E removeLast() { final Node
                          
                            l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } //第一個位置插入節點 public void addFirst(E e) { linkFirst(e); } // 最後一個位置插入節點 public void addLast(E e) { linkLast(e); } //是否包含元素 o public boolean contains(Object o) { return indexOf(o) != -1; } //擷取元素的個數 public int size() { return size; } //尾部加入節點 public boolean add(E e) { linkLast(e); return true; } //删除節點 o 順序周遊查找，找到後删除 public boolean remove(Object o) { if (o == null) { for (Node
                           
                             x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node
                            
                              x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } //集合c中元素插入到LinkedList中 public boolean addAll(Collection
                              c) { return addAll(size, c); } //index開始 集合c中元素加入的LinkedList中 public boolean addAll(int index, Collection
                              c) { checkPositionIndex(index);//檢查index是否合法 Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; Node
                             
                               pred, succ; // 找到插入位置的前驅 和後繼 if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node
                              
                                newNode = new Node<>(pred, e, null); // 新節點 e.prev = pred e.next = null if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } if (succ == null) { last = pred; } else { // 建立雙向連結 pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; } //清空 public void clear() { //設為null 友善GC for (Node
                               
                                 x = first; x != null; ) { Node
                                
                                  next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; } //擷取index位置的元素 public E get(int index) { checkElementIndex(index);// index合法性檢查 return node(index).item; } //index位置元素的值更新 public E set(int index, E element) { checkElementIndex(index); // index合法性檢查 Node
                                 
                                   x = node(index); E oldVal = x.item; x.item = element; return oldVal; } //index位置插入新節點 public void add(int index, E element) { checkPositionIndex(index);// index合法性檢查 if (index == size) linkLast(element);//插入節點e作為最後一個節點 else linkBefore(element, node(index)); //index 前插入節點 } //删除index位置的節點 public E remove(int index) { checkElementIndex(index); return unlink(node(index));//删除節點 x 并傳回節點值 } //是不是下标 private boolean isElementIndex(int index) { return index >= 0 && index < size; } //驗證index的合法性 不抛異常 private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } //越界輸出資訊 private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } //檢查index是否合法位置 private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //檢查index是否是合法的插入位置 private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //傳回index位置的節點 通過前後分開查找的方式 平均查找次數應該是：n/2 Node
                                  
                                    node(int index) { if (index < (size >> 1)) { Node
                                   
                                     x = first; for (int i = 0; i < index; i++) // 查找前一半 x = x.next; return x; } else { // 查找後一半 Node
                                    
                                      x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } //擷取節點o第一次出現的下标 public int indexOf(Object o) { int index = 0; if (o == null) { for (Node
                                     
                                       x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node
                                      
                                        x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } //擷取節點o最後一次出現的下标 public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node
                                       
                                         x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node
                                        
                                          x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; } //隊列的相關操作 //檢視隊頂元素 public E peek() { final Node
                                         
                                           f = first; return (f == null) ? null : f.item; } //檢視隊頂元素 public E element() { return getFirst(); } //擷取隊頂元素，并删除該元素 public E poll() { final Node
                                          
                                            f = first; return (f == null) ? null : unlinkFirst(f); } //删除隊頂元素，并傳回該值 public E remove() { return removeFirst(); } //隊尾部加入元素 public boolean offer(E e) { return add(e); } //雙端隊列相關操作 //第一個位置插入節點 public boolean offerFirst(E e) { addFirst(e); return true; } //最後一個位置插入節點 public boolean offerLast(E e) { addLast(e); return true; } //檢視隊頂元素 public E peekFirst() { final Node
                                           
                                             f = first; return (f == null) ? null : f.item; } //檢視隊尾元素 public E peekLast() { final Node
                                            
                                              l = last; return (l == null) ? null : l.item; } //隊頂元素出隊列 public E pollFirst() { final Node
                                             
                                               f = first; return (f == null) ? null : unlinkFirst(f); } // 隊尾元素出隊列 public E pollLast() { final Node
                                              
                                                l = last; return (l == null) ? null : unlinkLast(l); } //棧的相關操作 //入棧 public void push(E e) { addFirst(e); } //出棧 public E pop() { return removeFirst(); } //删除元素 o，隻删除第一次出現的那個 public boolean removeFirstOccurrence(Object o) { return remove(o); } //删除元素o，删除最後一次出現的那個 public boolean removeLastOccurrence(Object o) { if (o == null) { for (Node
                                               
                                                 x = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); return true; } } } else { for (Node
                                                
                                                  x = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } //傳回從index開始的疊代器 public ListIterator
                                                 
                                                   listIterator(int index) { checkPositionIndex(index);// 下标檢查 return new ListItr(index); } private class ListItr implements ListIterator
                                                  
                                                    { private Node
                                                   
                                                     lastReturned = null; private Node
                                                    
                                                      next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() {// hasNext 是否滿足條件 return nextIndex < size; } public E next() { // next 下一個值 checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } public boolean hasPrevious() { // hasPrevious 判斷 return nextIndex > 0; } public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item; } public int nextIndex() { //擷取目前下标 return nextIndex; } public int previousIndex() { return nextIndex - 1; } public void remove() { //删除值 checkForComodification(); if (lastReturned == null) throw new IllegalStateException(); Node
                                                     
                                                       lastNext = lastReturned.next; unlink(lastReturned); if (next == lastReturned) next = lastNext; else nextIndex--; lastReturned = null; expectedModCount++; } public void set(E e) { //替換值 if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; } 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; Node
                                                       
                                                         next; Node
                                                        
                                                          prev; Node(Node
                                                         
                                                           prev, E element, Node
                                                          
                                                            next) { this.item = element; this.next = next; // 後繼節點 this.prev = prev; // 前驅節點 } } //後向前的疊代器 public Iterator
                                                           
                                                             descendingIterator() { return new DescendingIterator(); } //後向前的疊代器 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(); } } //擷取LinkedList的clone private LinkedList
                                                             
                                                               superClone() { try { return (LinkedList
                                                              
                                                               ) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } } //擷取的一個clone public Object clone() { LinkedList
                                                               
                                                                 clone = superClone(); clone.first = clone.last = null; clone.size = 0; clone.modCount = 0; // Initialize clone with our elements for (Node
                                                                
                                                                  x = first; x != null; x = x.next) clone.add(x.item); return clone; } //轉換成數組 public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Node
                                                                 
                                                                   x = first; x != null; x = x.next) result[i++] = x.item; return result; } //LinkedList元素值更新數組a @SuppressWarnings("unchecked") public 
                                                                  
                                                                    T[] toArray(T[] a) { if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); int i = 0; Object[] result = a; for (Node
                                                                   
                                                                     x = 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; // 輸出流 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { s.defaultWriteObject(); s.writeInt(size); for (Node
                                                                    
                                                                      x = first; x != null; x = x.next) s.writeObject(x.item); } //輸入流 @SuppressWarnings("unchecked") private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { s.defaultReadObject(); int size = s.readInt(); for (int i = 0; i < size; i++) linkLast((E)s.readObject()); } }