LinkedList源碼分析--jdk1.8

JDK1.8

ArrayList源碼分析--jdk1.8
LinkedList源碼分析--jdk1.8
HashMap源碼分析--jdk1.8
AQS源碼分析--jdk1.8
ReentrantLock源碼分析--jdk1.8

LinkedList概述

??1.LinkedList是用雙向鏈表實現(xiàn)的集合，基于內(nèi)部類Node<E>實現(xiàn)的集合。
??2.LinkedList支持雙向鏈表訪問、克隆、序列化，元素有序且可以重復。
??3.LinkedList沒有初始化大小，也沒有擴容機制，通過頭結(jié)點、尾節(jié)點迭代查找。

LinkedList數(shù)據(jù)結(jié)構(gòu)

??數(shù)據(jù)結(jié)構(gòu)是集合的精華所在，數(shù)據(jù)結(jié)構(gòu)往往也限制了集合的作用和側(cè)重點，了解各種數(shù)據(jù)結(jié)構(gòu)是我們分析源碼的必經(jīng)之路。
??LinkedList的數(shù)據(jù)結(jié)構(gòu)如下：

鏈表基礎(chǔ)知識補充：
1）單向鏈表：
　　　　　　element：用來存放元素
　　　　　　next：用來指向下一個節(jié)點元素
　　　　　　通過每個結(jié)點的指針指向下一個結(jié)點從而鏈接起來的結(jié)構(gòu)，最后一個節(jié)點的next指向null。

2）單向循環(huán)鏈表
　　　　　　element、next 跟前面一樣
　　　　　　在單向鏈表的最后一個節(jié)點的next會指向頭節(jié)點，而不是指向null，這樣存成一個環(huán)

3）雙向鏈表
　　　　　　element：存放元素
　　　　　　pre：用來指向前一個元素
　　　　　　next：指向后一個元素
　　　　　　雙向鏈表是包含兩個指針的，pre指向前一個節(jié)點，next指向后一個節(jié)點，但是第一個節(jié)點head的pre指向null，最后一個節(jié)點的tail指向null。

4）雙向循環(huán)鏈表
　　　　　　element、pre、next 跟前面的一樣
　　　　　　第一個節(jié)點的pre指向最后一個節(jié)點，最后一個節(jié)點的next指向第一個節(jié)點，也形成一個“環(huán)”。

LinkedList源碼分析

/**
 * LinkedList 使用 iterator迭代器更加 快速
 * 用鏈表實現(xiàn)的集合，元素有序且可以重復
 * 雙向鏈表
 */
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    /**
     * 實際元素個數(shù)
     */
    transient int size = 0;
    /**
     * 頭結(jié)點
     */
    transient Node<E> first;
    /**
     * 尾結(jié)點
     */
    transient Node<E> last;
    /**
     * 無參構(gòu)造方法.
     */
    public LinkedList() {
    }
    /**
     * 集合參數(shù)構(gòu)造方法
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    /**
     * 內(nèi)部類Node
     */
    private static class Node<E> {
        E item;         // 數(shù)據(jù)域
        Node<E> next;   // 下一個
        Node<E> prev;   // 上一個

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

LinkedList繼承和實現(xiàn)分析

?? LinkedList extends AbstractSequentialList<E>
?? AbstractSequentialList extends AbstractList
?? AbstractList extends AbstractCollection
??java中所有類都繼承Object，所以LinkedList的繼承結(jié)構(gòu)如上圖。
?? 1. AbstractSequentialList是一個抽象類，繼承了AbstractList接口，AbstractList抽象類中可以有抽象方法，還可以有具體的實現(xiàn)方法，AbstractList實現(xiàn)接口中一些通用的方法，AbstractSequentialList再繼承AbstractList，拿到通用基礎(chǔ)的方法，然后自己在重寫實現(xiàn)基于鏈表的方法:add/addAll/get/iterator/listIterator/remove/set，這樣的好處是：讓代碼更簡潔，AbstractList隨機存取功能基類，AbstractSequentialList鏈表存取功能基類，父類抽象，子類個性，父類一般是抽象類，由子類來實現(xiàn)豐富。
?? 2.LinkedList實現(xiàn)了List<E>、Deque<E>、Cloneable、Serializable接口。
?? ??1)List<E>接口，集合通用操作方法定義。
?? ??2)Deque<E>接口，雙向隊列，在Queue單項隊列的基礎(chǔ)上增加為雙向隊列，提高查詢/操作效率
?? ??3)Cloneable接口，可以使用Object.Clone()方法。
?? ??4)Serializable接口，序列化接口，表明該類可以被序列化，什么是序列化？簡單的說，就是能夠從類變成字節(jié)流傳輸，反序列化，就是從字節(jié)流變成原來的類

LinkedList核心方法分析

1. add方法(7種重載實現(xiàn))--增?? ?

LinkedList中特有的新增方法
Deque中要實現(xiàn)的新增方法

?? ??1)add(E)；//默認直接在末尾添加元素

/**
 * 新增元素
 */
 public boolean add(E e) {
            // 添加到末尾
                linkLast(e);
                return true;
        }
 /**
 * 鏈接到末尾.
 */
void linkLast(E e) {
    // 保存尾結(jié)點，l為final類型，不可更改
    final Node<E> l = last;
    // 新生成結(jié)點的上一個為l,下一個為null
    final Node<E> newNode = new Node<>(l, e, null);
    // 重新賦值尾結(jié)點
    last = newNode;
    if (l == null) // 尾結(jié)點為空
        first = newNode; // 賦值頭結(jié)點
    else
        l.next = newNode; // 尾結(jié)點的下一個為新生成的結(jié)點
    size++; // 大小加1    
    modCount++; // 結(jié)構(gòu)性修改加1
}

?? ??2)add(int index, E element)；//給指定下標，添加元素

/**
 * 在index位置插入節(jié)點
 * 1.如果index等于size，則在末尾新增元素，原因:size為實際元素個數(shù)，index為下標，所以index=size時，說明要在末尾插入元素
 * 2.如果index不等于size，則根據(jù)index下標找到節(jié)點，在節(jié)點前插入元素，原因：需要占用index下標位置。
 */
public void add(int index, E element) {
            //查看下標是否越界
    checkPositionIndex(index);
    //如果指定下標等于實際元素個數(shù)，則添加到末尾
    if (index == size)
        linkLast(element);
    else //否則，找到index位置元素添加到index后
        linkBefore(element, node(index));
}
 /**
 * 判斷下標是否越界
 */
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
 * 根據(jù)index下標找到節(jié)點
 * 優(yōu)化：由于是雙向鏈表，所以判斷索引位置（size/2），前半段從頭節(jié)點開始查找，后半段從尾節(jié)點開始查找
 */
Node<E> node(int index) {
    // assert isElementIndex(index);
     // 判斷插入的位置在鏈表前半段或者是后半段 size/2的1次方
    if (index < (size >> 1)) { // 插入位置在前半段
        Node<E> x = first;
        for (int i = 0; i < index; i++) // 從頭結(jié)點開始正向遍歷
            x = x.next;
        return x;
    } else {// 插入位置在后半段
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
/**
 * 在非空節(jié)點succ前插入數(shù)據(jù)
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

?? ??3)addAll(Collection<? extends E> c)；//添加Collection類型元素

 /**
 * 添加一個集合
 */
 public boolean addAll(Collection<? extends E> c) {
         //在末尾添加
    return addAll(size, c);
}

?? ??4)addAll(int index, Collection<? extends E> c)；//指定位置，添加Collection類型元素

/**
 * 從指定的位置開始，將指定collection中的所有元素插入到此列表中，新元素的順序為指定collection的迭代器所返回的元素順序
 */
public boolean addAll(int index, Collection<? extends E> c) {
    // 檢查插入的的位置是否合法
    checkPositionIndex(index);
    // 將集合轉(zhuǎn)化為數(shù)組
    Object[] a = c.toArray();
    // 保存集合大小
    int numNew = a.length;
    if (numNew == 0) // 集合為空，直接返回
        return false;
    Node<E> pred, succ; //上一個 下一個
    if (index == size) { // 如果插入位置為鏈表末尾，則后繼為null，上一個為尾結(jié)點
        succ = null;
        pred = last;
    } else { // 插入位置為其他某個位置
        succ = node(index); // 尋找到該結(jié)點
        pred = succ.prev; // 保存該結(jié)點的上一個
    }
    for (Object o : a) {  // 遍歷數(shù)組
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);  // 生成新結(jié)點
        if (pred == null)  // 表示在第一個元素之前插入(索引為0的結(jié)點)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }
    if (succ == null) { // 表示在最后一個元素之后插入
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
    // 修改實際元素個數(shù)
    size += numNew;
    // 結(jié)構(gòu)性修改加1
    modCount++;
    return true;
}

?? ??5)addFirst(E e)；//頭結(jié)點添加元素

/**
 * 頭結(jié)點插入元素
 */
public void addFirst(E e) {
    linkFirst(e);
}
/**
 * 鏈接頭結(jié)點
 */
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);//新建節(jié)點，頭結(jié)點為null，尾節(jié)點為first
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

?? ??6)addLast(E e)；//尾結(jié)點添加元素

 /**
 * 尾節(jié)點添加元素
 */
public void addLast(E e) {
    linkLast(e);
}
/**
 * 鏈接尾節(jié)點
 */
void linkLast(E e) {
    // 保存尾結(jié)點，l為final類型，不可更改
    final Node<E> l = last;
    // 新生成結(jié)點的上一個為l,下一個為null
    final Node<E> newNode = new Node<>(l, e, null);
    // 重新賦值尾結(jié)點
    last = newNode;
    if (l == null) // 尾結(jié)點為空
        first = newNode; // 賦值頭結(jié)點
    else
        l.next = newNode; // 尾結(jié)點的下一個為新生成的結(jié)點
    size++; // 大小加1    
    modCount++; // 結(jié)構(gòu)性修改加1
}

?? ??7)push(E e)；//添加頭結(jié)點

/**
 * addFirst，添加頭結(jié)點
 */
public void push(E e) {
    addFirst(e);
}

2.remove方法(11種重載實現(xiàn))--刪

LinkedList中特有的刪除方法
Deque中要實現(xiàn)的刪除方法

?? ??1)E remove(); //刪除頭元素?

 /**
 * 刪除頭結(jié)點
 */
public E remove() {
    return removeFirst();
}
/**
 * 刪除頭結(jié)點
 */
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
 /**
 * 頭結(jié)點設(shè)置為下一個節(jié)點
 */
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

?? ??2)E remove(int index); //根據(jù)下標刪除元素?

 /**
 * 根據(jù)下標刪除元素
 */
public E remove(int index) {
    //檢查下標是否合法
    checkElementIndex(index);
    return unlink(node(index));
}
 /**
 * 刪除指定節(jié)點元素
 */
E unlink(Node<E> x) {
    // assert x != null;
     // 保存結(jié)點的元素
    final E element = x.item;
    // 保存x的下一個
    final Node<E> next = x.next;
    // 保存x的上一個
    final Node<E> prev = x.prev;
    //如果上一個節(jié)點為null，則說明是頭結(jié)點，把next賦值first
    if (prev == null) {
        first = next;
    } else {//如果不是頭結(jié)點，則把上一個節(jié)點的next賦值為next的元素，x的上一個節(jié)點賦值為null，以便GC
        prev.next = next;
        x.prev = null;
    }
    //如果下一個節(jié)點為空，則說明是尾節(jié)點，把prev賦值為lst
    if (next == null) {
        last = prev;
    } else {//如果不是尾節(jié)點，則把下一個節(jié)點的prev賦值為prev的元素，x的一下個節(jié)點賦值為null，以便GC
        next.prev = prev;
        x.next = null;
    }
    x.item = null; // 結(jié)點元素賦值為空，以便
    size--;  // 減少元素實際個數(shù)
    modCount++;  // 結(jié)構(gòu)性修改加1
    return element;
}

?

?? ??3)boolean remove(Object o); //刪除元素o?

/**
 * 刪除元素o?
 */
public boolean remove(Object o) {
//判斷o是否為null，付過為null用equals，會報空指針
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

?? ??4)E removeFirst(); //刪除頭結(jié)點

 /**
 * 刪除頭結(jié)點
 */
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

?? ??5)E removeLast(); //刪除尾結(jié)點

 /**
 * 刪除尾結(jié)點
 */
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

?? ??6)boolean removeFirstOccurrence(Object o); //刪除此節(jié)點中第一次出現(xiàn)的o

 /**
 * 刪除此節(jié)點中第一次出現(xiàn)的o（從頭到尾遍歷列表時）
 */
public boolean removeFirstOccurrence(Object o) {
    return remove(o);
}

?? ??7)boolean removeLastOccurrence(Object o); //刪除此節(jié)點中最后一次出現(xiàn)的o

 /**
 * 刪除此列表中最后一次出現(xiàn)的元素o（從頭到尾遍歷列表時）
 */
public boolean removeLastOccurrence(Object o) {
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

?? ??8)E poll(); //刪除頭結(jié)點

 /**
 * 刪除頭結(jié)點
 */
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

?? ??9)E pollFirst(); //刪除頭結(jié)點

/**
 *  刪除頭結(jié)點
 * @since 1.6
 */
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

?? ??10)E pollLast(); //刪除尾結(jié)點

/**
 *  刪除尾結(jié)點
 * @since 1.6
 */
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

?? ??11)E pop(); //刪除頭結(jié)點

/**
 * 刪除頭結(jié)點
 * @since 1.6
 */
public E pop() {
    return removeFirst();
}

總結(jié)：
? ?remove函數(shù)用戶移除指定下標的元素，此時會把指定下標到數(shù)組末尾的元素向前移動一個單位，并且會把數(shù)組最后一個元素設(shè)置為null，這樣是為了方便之后將整個數(shù)組不被使用時，會被GC，可以作為小的技巧使用。

3.set方法--改

/**
 * 覆蓋指定下標元素
 */
    public E set(int index, E element) {
      //判斷下標是否越界
    checkElementIndex(index);
             //獲得下標節(jié)點
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}
     /**
 * 判斷下標是否越界
 */

private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

4.get方法(6種重載)--查

LinkedList中特有的查詢方法
Deque中要實現(xiàn)的查詢方法

?? ??1)E get(int index); //根據(jù)下標獲取指定節(jié)點的元素值

/**
 * 返回指定下標的值
 */
public E get(int index) {
    //判斷下標是否越界
    checkElementIndex(index);
    return node(index).item;
}
 /**
 * 判斷下標是否越界
 */
private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
 * 判斷下標是否越界
 */
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}
    /**
 * 根據(jù)index下標找到節(jié)點
 * 優(yōu)化：由于是雙向鏈表，所以判斷索引位置（size/2），前半段從頭節(jié)點開始查找，后半段從尾節(jié)點開始查找
 */
Node<E> node(int index) {
    // assert isElementIndex(index);
     // 判斷插入的位置在鏈表前半段或者是后半段 size/2的1次方
    if (index < (size >> 1)) { // 插入位置在前半段
        Node<E> x = first;
        for (int i = 0; i < index; i++) // 從頭結(jié)點開始正向遍歷
            x = x.next;
        return x;
    } else {// 插入位置在后半段
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

?? ??2)E getFirst(); //獲取頭節(jié)點的元素值

/**
 * 獲取頭結(jié)點
 */
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

?? ??3)E getFirst(); //獲取頭節(jié)點的元素值

 /**
 * 獲取尾節(jié)點
 */
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

?? ??4)E peek(); //獲取頭節(jié)點的元素值

/**
 * 獲取頭結(jié)點
 * @since 1.5
 */
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

?? ??5)E peekFirst(); //獲取頭節(jié)點的元素值

/**
 *  獲取頭節(jié)點的元素值
 * @since 1.6
 */
public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
 }

?? ??6)E peekFirst(); //獲取尾節(jié)點的元素值

/**
 * 獲取尾節(jié)點的元素值
 * @since 1.6
 */
public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

5.indexOf方法--通過o查找下標，從頭到尾查找

/**
 * 查找下標， 如果為null,直接和null比較，返回下標
 * 通過o查找下標，從頭到尾查找
 */
public int indexOf(Object o) {
    int index = 0;
    //判斷o是否為null，付過為null用equals，會報空指針
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

6.lastIndexOf方法--通過o查找下標，從尾到頭查找

/**
 * 通過o查找下標，從尾到頭查找
 */
public int lastIndexOf(Object o) {
    int index = size;
    //判斷o是否為null，付過為null用equals，會報空指針
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

7.clone方法--克隆

 /**
 * 克隆
 * 復制，LinkedList 的淺拷貝
 */
public Object clone() {
    LinkedList<E> clone = superClone();
    // Put clone into "virgin" state
    clone.first = clone.last = null;
    clone.size = 0;
    clone.modCount = 0;
    // Initialize clone with our elements
    for (Node<E> x = first; x != null; x = x.next)
        clone.add(x.item);
    return clone;
}

8.Node內(nèi)部類--存儲存儲元素的對象

 /**
 * 內(nèi)部類Node,LinkedList存儲元素的對象
 * @param <E>
 */
private static class Node<E> {
    E item;         // 數(shù)據(jù)域
    Node<E> next;   // 下一個
    Node<E> prev;   // 上一個

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

9.ListItr內(nèi)部類--類似Iterator，可以幫我們對List進行遍歷，增刪改查等

/**
 * 返回index位置的interator
 */
public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}
/**
 * 內(nèi)部類，類似Iterator，可以幫我們對List進行遍歷，增刪改查等
 */
private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned = null;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;
    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;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }
    public boolean 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<E> 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++;
    }
    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (modCount == expectedModCount && nextIndex < size) {
            action.accept(next.item);
            lastReturned = next;
            next = next.next;
            nextIndex++;
        }
        checkForComodification();
    }
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

10.DescendingIterator內(nèi)部類--逆序的ListItr

 /**
 * @since 1.6
 * 實例化一個DescendingIterator對象，并返回
 */
public Iterator<E> descendingIterator() {
    return new DescendingIterator();
}

/**
 * Adapter to provide descending iterators via ListItr.previous
 * DescendingIterator是逆序的ListItr
 */
private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

11.LLSpliterator內(nèi)部類--將元素分割成多份，分別交于不于的線程去遍歷，以提高效率

/**
 * @since 1.8
 * 實例化一個LLSpliterator對象，并返回
 */
@Override
public Spliterator<E> spliterator() {
    return new LLSpliterator<E>(this, -1, 0);
}

/** A customized variant of Spliterators.IteratorSpliterator
 * 實例化一個LLSpliterator對象，并返回。LLSpliterator是JDK1.8之后LinkedList新增的內(nèi)部類，
 * 大概用途是將元素分割成多份，分別交于不于的線程去遍歷，以提高效率
 * */
static final class LLSpliterator<E> implements Spliterator<E> {
    static final int BATCH_UNIT = 1 << 10;  // batch array size increment
    static final int MAX_BATCH = 1 << 25;  // max batch array size;
    final LinkedList<E> list; // null OK unless traversed
    Node<E> current;      // current node; null until initialized
    int est;              // size estimate; -1 until first needed
    int expectedModCount; // initialized when est set
    int batch;            // batch size for splits

    LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
        this.list = list;
        this.est = est;
        this.expectedModCount = expectedModCount;
    }

    final int getEst() {
        int s; // force initialization
        final LinkedList<E> lst;
        if ((s = est) < 0) {
            if ((lst = list) == null)
                s = est = 0;
            else {
                expectedModCount = lst.modCount;
                current = lst.first;
                s = est = lst.size;
            }
        }
        return s;
    }

    public long estimateSize() { return (long) getEst(); }

    public Spliterator<E> trySplit() {
        Node<E> p;
        int s = getEst();
        if (s > 1 && (p = current) != null) {
            int n = batch + BATCH_UNIT;
            if (n > s)
                n = s;
            if (n > MAX_BATCH)
                n = MAX_BATCH;
            Object[] a = new Object[n];
            int j = 0;
            do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
            current = p;
            batch = j;
            est = s - j;
            return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
        }
        return null;
    }

    public void forEachRemaining(Consumer<? super E> action) {
        Node<E> p; int n;
        if (action == null) throw new NullPointerException();
        if ((n = getEst()) > 0 && (p = current) != null) {
            current = null;
            est = 0;
            do {
                E e = p.item;
                p = p.next;
                action.accept(e);
            } while (p != null && --n > 0);
        }
        if (list.modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

    public boolean tryAdvance(Consumer<? super E> action) {
        Node<E> p;
        if (action == null) throw new NullPointerException();
        if (getEst() > 0 && (p = current) != null) {
            --est;
            E e = p.item;
            current = p.next;
            action.accept(e);
            if (list.modCount != expectedModCount)
                throw new ConcurrentModificationException();
            return true;
        }
        return false;
    }

    public int characteristics() {
        return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
    }
}

LinkedList總結(jié)

1）LinkedList可以存放null，本質(zhì)是泛型E類型的內(nèi)部類。
2）LinkedList插入刪除快，查詢慢，需要從頭/尾節(jié)點遍歷找到元素，移動數(shù)據(jù)只需要修改相鄰節(jié)點元素，效率高。
3）LinkedList父類繼承了Iterable，所以在遍歷它的時候推薦使用iterator循環(huán)，效率更高。
4）LinkedList操作頭/尾結(jié)點有對應First/Last方法，效率高，查詢也類似二分法的遍歷。
5）LinkedList實現(xiàn)Deque<E>雙端隊列，有相關(guān)隊列出棧/入棧方法。