LinkedList源碼分析--jdk1.8

JDK1.8

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

創(chuàng)新互聯(lián)主要從事成都做網(wǎng)站、網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)柘榮,十多年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來(lái)電咨詢建站服務(wù):18980820575

LinkedList概述

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

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

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

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

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

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

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

LinkedList源碼分析

/**
 * LinkedList 使用 iterator迭代器更加 快速
 * 用鏈表實(shí)現(xiàn)的集合，元素有序且可以重復(fù)
 * 雙向鏈表
 */
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    /**
     * 實(shí)際元素個(gè)數(shù)
     */
    transient int size = 0;
    /**
     * 頭結(jié)點(diǎn)
     */
    transient Node<E> first;
    /**
     * 尾結(jié)點(diǎn)
     */
    transient Node<E> last;
    /**
     * 無(wú)參構(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;   // 下一個(gè)
        Node<E> prev;   // 上一個(gè)

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

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

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

LinkedList核心方法分析

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

LinkedList源碼分析--jdk1.8 LinkedList中特有的新增方法
Deque中要實(shí)現(xiàn)的新增方法

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

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

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

/**
 * 在index位置插入節(jié)點(diǎn)
 * 1.如果index等于size，則在末尾新增元素，原因:size為實(shí)際元素個(gè)數(shù)，index為下標(biāo)，所以index=size時(shí)，說(shuō)明要在末尾插入元素
 * 2.如果index不等于size，則根據(jù)index下標(biāo)找到節(jié)點(diǎn)，在節(jié)點(diǎn)前插入元素，原因：需要占用index下標(biāo)位置。
 */
public void add(int index, E element) {
            //查看下標(biāo)是否越界
    checkPositionIndex(index);
    //如果指定下標(biāo)等于實(shí)際元素個(gè)數(shù)，則添加到末尾
    if (index == size)
        linkLast(element);
    else //否則，找到index位置元素添加到index后
        linkBefore(element, node(index));
}
 /**
 * 判斷下標(biāo)是否越界
 */
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
 * 根據(jù)index下標(biāo)找到節(jié)點(diǎn)
 * 優(yōu)化：由于是雙向鏈表，所以判斷索引位置（size/2），前半段從頭節(jié)點(diǎn)開始查找，后半段從尾節(jié)點(diǎn)開始查找
 */
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é)點(diǎn)開始正向遍歷
            x = x.next;
        return x;
    } else {// 插入位置在后半段
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
/**
 * 在非空節(jié)點(diǎn)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類型元素

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

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

/**
 * 從指定的位置開始，將指定collection中的所有元素插入到此列表中，新元素的順序?yàn)橹付╟ollection的迭代器所返回的元素順序
 */
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; //上一個(gè) 下一個(gè)
    if (index == size) { // 如果插入位置為鏈表末尾，則后繼為null，上一個(gè)為尾結(jié)點(diǎn)
        succ = null;
        pred = last;
    } else { // 插入位置為其他某個(gè)位置
        succ = node(index); // 尋找到該結(jié)點(diǎn)
        pred = succ.prev; // 保存該結(jié)點(diǎn)的上一個(gè)
    }
    for (Object o : a) {  // 遍歷數(shù)組
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);  // 生成新結(jié)點(diǎn)
        if (pred == null)  // 表示在第一個(gè)元素之前插入(索引為0的結(jié)點(diǎn))
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }
    if (succ == null) { // 表示在最后一個(gè)元素之后插入
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
    // 修改實(shí)際元素個(gè)數(shù)
    size += numNew;
    // 結(jié)構(gòu)性修改加1
    modCount++;
    return true;
}

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

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

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

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

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

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

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

LinkedList源碼分析--jdk1.8 LinkedList中特有的刪除方法
Deque中要實(shí)現(xiàn)的刪除方法

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

 /**
 * 刪除頭結(jié)點(diǎn)
 */
public E remove() {
    return removeFirst();
}
/**
 * 刪除頭結(jié)點(diǎn)
 */
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
 /**
 * 頭結(jié)點(diǎn)設(shè)置為下一個(gè)節(jié)點(diǎn)
 */
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ù)下標(biāo)刪除元素?

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

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

/**
 * 刪除元素o?
 */
public boolean remove(Object o) {
//判斷o是否為null，付過為null用equals，會(huì)報(bào)空指針
    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é)點(diǎn)

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

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

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

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

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

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

 /**
 * 刪除此列表中最后一次出現(xiàn)的元素o（從頭到尾遍歷列表時(shí)）
 */
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é)點(diǎn)

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

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

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

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

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

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

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

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

3.set方法--改

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

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

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

LinkedList源碼分析--jdk1.8 LinkedList中特有的查詢方法
Deque中要實(shí)現(xiàn)的查詢方法

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

/**
 * 返回指定下標(biāo)的值
 */
public E get(int index) {
    //判斷下標(biāo)是否越界
    checkElementIndex(index);
    return node(index).item;
}
 /**
 * 判斷下標(biāo)是否越界
 */
private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
 * 判斷下標(biāo)是否越界
 */
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}
    /**
 * 根據(jù)index下標(biāo)找到節(jié)點(diǎn)
 * 優(yōu)化：由于是雙向鏈表，所以判斷索引位置（size/2），前半段從頭節(jié)點(diǎn)開始查找，后半段從尾節(jié)點(diǎn)開始查找
 */
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é)點(diǎn)開始正向遍歷
            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é)點(diǎn)的元素值

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

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

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

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

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

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

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

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

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

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

/**
 * 查找下標(biāo)， 如果為null,直接和null比較，返回下標(biāo)
 * 通過o查找下標(biāo)，從頭到尾查找
 */
public int indexOf(Object o) {
    int index = 0;
    //判斷o是否為null，付過為null用equals，會(huì)報(bào)空指針
    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查找下標(biāo)，從尾到頭查找

/**
 * 通過o查找下標(biāo)，從尾到頭查找
 */
public int lastIndexOf(Object o) {
    int index = size;
    //判斷o是否為null，付過為null用equals，會(huì)報(bào)空指針
    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方法--克隆

 /**
 * 克隆
 * 復(fù)制，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)部類--存儲(chǔ)存儲(chǔ)元素的對(duì)象

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

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

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

/**
 * 返回index位置的interator
 */
public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}
/**
 * 內(nèi)部類，類似Iterator，可以幫我們對(duì)List進(jìn)行遍歷，增刪改查等
 */
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
 * 實(shí)例化一個(gè)DescendingIterator對(duì)象，并返回
 */
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
 * 實(shí)例化一個(gè)LLSpliterator對(duì)象，并返回
 */
@Override
public Spliterator<E> spliterator() {
    return new LLSpliterator<E>(this, -1, 0);
}

/** A customized variant of Spliterators.IteratorSpliterator
 * 實(shí)例化一個(gè)LLSpliterator對(duì)象，并返回。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é)點(diǎn)遍歷找到元素，移動(dòng)數(shù)據(jù)只需要修改相鄰節(jié)點(diǎn)元素，效率高。
3）LinkedList父類繼承了Iterable，所以在遍歷它的時(shí)候推薦使用iterator循環(huán)，效率更高。
4）LinkedList操作頭/尾結(jié)點(diǎn)有對(duì)應(yīng)First/Last方法，效率高，查詢也類似二分法的遍歷。
5）LinkedList實(shí)現(xiàn)Deque<E>雙端隊(duì)列，有相關(guān)隊(duì)列出棧/入棧方法。

網(wǎng)頁(yè)標(biāo)題：LinkedList源碼分析--jdk1.8
網(wǎng)址分享：http://aaarwkj.com/article40/gdseho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計(jì)、搜索引擎優(yōu)化、網(wǎng)站改版、軟件開發(fā)、標(biāo)簽優(yōu)化、Google

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

欧美一级特黄大片做受成人-亚洲成人一区二区电影-激情熟女一区二区三区-日韩专区欧美专区国产专区