第一章 LinkedList源碼分析

目標(biāo)：

• 理解LinkedList的底層數(shù)據(jù)結(jié)構(gòu)
• 深入源碼掌握LinkedList查詢慢，新增快的原因

一、LinkedList的簡(jiǎn)介

蒲江縣網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)公司,蒲江縣網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為蒲江縣上千多家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站制作要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的蒲江縣做網(wǎng)站的公司定做！

List接口的鏈接列表實(shí)現(xiàn)。實(shí)現(xiàn)所有可選的列表操作，并且允許所有元素（包括null)。除了實(shí)現(xiàn)List接口外，LinkedList類為在列表的開頭及結(jié)尾get、remove和insert元素提供了統(tǒng)一的命名方法。這些操作允許將鏈接列表用作堆棧、隊(duì)列或雙端隊(duì)列。

特點(diǎn)：

• 有序性：存入和取出的順序是一致的
• 元素可以重復(fù)
• 含有帶索引的方法
• 獨(dú)有特點(diǎn)：數(shù)據(jù)結(jié)構(gòu)是鏈表，可以作為棧、隊(duì)列或雙端隊(duì)列！

LinkedList是一個(gè)雙向的鏈表結(jié)構(gòu)，雙向鏈表的長(zhǎng)相，如下圖！

二、LinkedList原理分析

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

LinkedList是一個(gè)雙向鏈表！

底層數(shù)據(jù)結(jié)構(gòu)的源碼：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;
 	//雙向鏈表的頭節(jié)點(diǎn)
    transient Node<E> first;
	//雙向鏈表的最后一個(gè)節(jié)點(diǎn)
    transient Node<E> last;
    //節(jié)點(diǎn)類【內(nèi)部類】
     private static class Node<E> {
        E item;//數(shù)據(jù)元素
        Node<E> next;//下一個(gè)節(jié)點(diǎn)
        Node<E> prev;//上一個(gè)節(jié)點(diǎn)
		
         //節(jié)點(diǎn)的構(gòu)造方法
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
	//...
}

LinkedList是雙向鏈表，在代碼中是一個(gè)Node類。 內(nèi)部并沒(méi)有數(shù)組的結(jié)構(gòu)。雙向鏈表肯定存在一個(gè)頭節(jié)點(diǎn)和一個(gè)尾節(jié)點(diǎn)。node節(jié)點(diǎn)類，是以內(nèi)部類的形式存在與LinkedList中的。Node類都有兩個(gè)成員變量。

• prev：當(dāng)前節(jié)點(diǎn)上一個(gè)節(jié)點(diǎn)，頭節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)是null
• next：當(dāng)前節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)，尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是null

鏈表數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)：查詢慢，增刪快！

• 鏈表數(shù)據(jù)結(jié)構(gòu)基本構(gòu)成，是一個(gè)node類
• 每個(gè)node類中，有上一個(gè)節(jié)點(diǎn)【prev】和下一個(gè)節(jié)點(diǎn)【next】
• 鏈表一定存在至少兩個(gè)節(jié)點(diǎn)，first和last節(jié)點(diǎn)
• 如果LinkedList沒(méi)有數(shù)據(jù)，first和last都是為null

2.2LinkedList默認(rèn)容量&最大容量

沒(méi)有默認(rèn)容量，也沒(méi)有最大容量

2.3LinkedList擴(kuò)容機(jī)制

無(wú)需擴(kuò)容機(jī)制，只要你的內(nèi)存足夠大，可以無(wú)限制擴(kuò)容下去。前提是不考慮查詢的效率。

2.4為什么LinkedList查詢慢，增刪快？

LinkedList的數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，鏈表的數(shù)據(jù)結(jié)構(gòu)就是這樣的特點(diǎn)！

• 鏈表是一種查詢慢的結(jié)構(gòu)【相對(duì)于數(shù)組來(lái)說(shuō)】
• 鏈表是一種增刪快的結(jié)構(gòu)【相對(duì)于數(shù)組來(lái)說(shuō)】

2.5LinkedList源碼刨析-為什么增刪快？

新增add

//向LinkedList添加一個(gè)元素
public boolean add(E e) {
    //連接到鏈表的末尾
    linkLast(e);
    return true;
}
//連接到最后一個(gè)節(jié)點(diǎn)上去
void linkLast(E e) {
    //將全局末尾節(jié)點(diǎn)賦值給1
    final Node<E> l = last;
    //創(chuàng)建一個(gè)新節(jié)點(diǎn)：（上一個(gè)節(jié)點(diǎn)，當(dāng)前插入元素，null）
    final Node<E> newNode = new Node<>(l, e, null);
    //將當(dāng)前節(jié)點(diǎn)作為末尾節(jié)點(diǎn)
    last = newNode;
    //判斷l(xiāng)節(jié)點(diǎn)是否為null
    if (l == null)
        //即是尾節(jié)點(diǎn)也是頭節(jié)點(diǎn)
        first = newNode;
    else
        //之前的末尾節(jié)點(diǎn)，下一個(gè)節(jié)點(diǎn)是末尾節(jié)點(diǎn)
        l.next = newNode;
    size++;//當(dāng)前集合的元素?cái)?shù)量+1
    modCount++;//操作集合數(shù)+1，modCount屬性是修改計(jì)數(shù)器
}
//-----------------------------------------------------------------
//向鏈表的中部添加
//參數(shù)1，添加的索引位置，添加元素
public void add(int index, E element) {
    //檢查索引位是否符合要求
    checkPositionIndex(index);
	//判斷當(dāng)前索引位是否存儲(chǔ)元素個(gè)數(shù)
    if (index == size)//true,最后一個(gè)元素
        linkLast(element);
    else
        //連接到指定節(jié)點(diǎn)的后面【鏈表中部插入】
        linkBefore(element, node(index));
}
//根據(jù)索引查詢鏈表中節(jié)點(diǎn)！
Node<E> node(int index) {
	//判斷索引是否小于  已經(jīng)存儲(chǔ)元素個(gè)數(shù)的1/2
    if (index < (size >> 1)) {//二分法查找：提高查找節(jié)點(diǎn)效率
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
//將當(dāng)前元素添加到指定節(jié)點(diǎn)之前
void linkBefore(E e, Node<E> succ) {
    //取出當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
    final Node<E> pred = succ.prev;
    //創(chuàng)建當(dāng)前元素的節(jié)點(diǎn)：上一個(gè)節(jié)點(diǎn)，當(dāng)前元素，下一個(gè)節(jié)點(diǎn)
    final Node<E> newNode = new Node<>(pred, e, succ);
    //為指定節(jié)點(diǎn)上一個(gè)節(jié)點(diǎn)重賦新值
    succ.prev = newNode;
    //判斷當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)是否為null
    if (pred == null)
        first = newNode;//當(dāng)前節(jié)點(diǎn)作為頭部節(jié)點(diǎn)
    else
        pred.next = newNode;//將新插入節(jié)點(diǎn)作為上一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
    size++;//新增元素+1
    modCount++;//操作次數(shù)+1
}

remove刪除指定索引元素

//刪除指定索引位置元素
public E remove(int index) {
    //檢查元素索引
    checkElementIndex(index);
    //刪除元素節(jié)點(diǎn)
    //node(index) 根據(jù)索引查到要?jiǎng)h除的節(jié)點(diǎn)
    //unlink()刪除節(jié)點(diǎn)
    return unlink(node(index));
}
//根據(jù)索引查詢鏈表中節(jié)點(diǎn)！
Node<E> node(int index) {
	//判斷索引是否小于  已經(jīng)存儲(chǔ)元素個(gè)數(shù)的1/2
    if (index < (size >> 1)) {//二分法查找：提高查找節(jié)點(diǎn)效率
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
//刪除一個(gè)指定節(jié)點(diǎn)
E unlink(Node<E> x) {
    //獲取當(dāng)前節(jié)點(diǎn)的元素
    final E element = x.item;
    //獲取當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
    final Node<E> next = x.next;
    //獲取當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
    final Node<E> prev = x.prev;
	//判斷上一個(gè)節(jié)點(diǎn)是否為null
    if (prev == null) {
        //如果為null,說(shuō)明當(dāng)前節(jié)點(diǎn)為頭部節(jié)點(diǎn)
        first = next;
    } else {
        //上一個(gè)節(jié)點(diǎn) 的下一個(gè)節(jié)點(diǎn)改為下下節(jié)點(diǎn)
        prev.next = next;
        //將當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)置空
        x.prev = null;
    }
	//判斷下一個(gè)節(jié)點(diǎn)是否為null
    if (next == null) {
        //如果為null，說(shuō)明當(dāng)前節(jié)點(diǎn)為尾部節(jié)點(diǎn)
        last = prev;
    } else {
        //下一個(gè)節(jié)點(diǎn)的上節(jié)點(diǎn)，改為上上節(jié)點(diǎn)
        next.prev = prev;
        //當(dāng)前節(jié)點(diǎn)的上節(jié)點(diǎn)置空
        x.next = null;
    }
	//刪除當(dāng)前節(jié)點(diǎn)內(nèi)的元素
    x.item = null;
    size--;//集合中的元素個(gè)數(shù)-1
    modCount++;//當(dāng)前集合操作數(shù)+1，modCount計(jì)數(shù)器，記錄當(dāng)前集合操作數(shù)次數(shù)
    return element;//返回刪除的元素
}

2.6LinkedList源碼刨析-為什么查詢慢？

查詢快和慢是一個(gè)相對(duì)概念！相對(duì)于數(shù)組來(lái)說(shuō)

//根據(jù)索引查詢一個(gè)元素
public E get(int index) {
    //檢查索引是否存在
    checkElementIndex(index);
    //node(index)獲取索引對(duì)應(yīng)節(jié)點(diǎn)，獲取節(jié)點(diǎn)中的數(shù)據(jù)item
    return node(index).item;
}
//根據(jù)索引獲取對(duì)應(yīng)節(jié)點(diǎn)對(duì)象
Node<E> node(int index) {
    //二分法查找索引對(duì)應(yīng)的元素
    if (index < (size >> 1)) {
        Node<E> x = first;
        //前半部分查找【遍歷節(jié)點(diǎn)】
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        //后半部分查找【遍歷】
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
//查看ArrayList里的數(shù)組獲取元素的方式
public E get(int index) {
    rangeCheck(index);//檢查范圍
    return elementData(index);//獲取元素
}
E elementData(int index) {
    return (E) elementData[index];//一次性操作
}

第二章 經(jīng)典面試題

1、ArrayList的JDK1.8之前與之后的實(shí)現(xiàn)區(qū)別？

• JDK1.6：ArrayList像餓漢模式，直接創(chuàng)建一個(gè)初始化容量為10的數(shù)組。缺點(diǎn)就是占用空間較大。

• JDK1.7&JDK1.8：ArrayList像懶漢式，一開始創(chuàng)建一個(gè)長(zhǎng)度為0的數(shù)組，當(dāng)添加第一個(gè)元素時(shí)再創(chuàng)建一個(gè)初始容量為10的數(shù)組

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

2、List和Map區(qū)別？

Map集合

• 雙列集合：一次存一對(duì)
• key是不允許重復(fù)的，value可以重復(fù)
• 一個(gè)key只能對(duì)應(yīng)一個(gè)值value
• Map集合三兄弟：HashMap【無(wú)序集合】、LinkedHashMap【有序集合】、TreeMap【有序集合、自帶排序能力】

List集合

• 單列集合：一次存一個(gè)
• 有序集合
• 元素重復(fù)
• 帶索引
• List集合主要有兩個(gè)實(shí)現(xiàn)類：ArrayList和LinkedList

3、Array和ArrayList有何區(qū)別？什么時(shí)候更適合用Arry?

區(qū)別：

• Array可以容納基本類型和對(duì)象，而ArrayList只能容納對(duì)象【底層是一個(gè)對(duì)象數(shù)組】
• Array指定大小的固定不變，而ArrayList大小是動(dòng)態(tài)的，可自動(dòng)擴(kuò)容。
• Array沒(méi)有ArrayList方法多。、

盡管ArrayList明顯是更好的選擇，但也有些時(shí)候Array比較好用，比如下面的三種情況。

• 1、如果列表的大小已經(jīng)指定，大部分情況是存儲(chǔ)和遍歷它們
• 基本數(shù)據(jù)類型使用Array更合適

4、ArrayList與LinkedList區(qū)別？

ArrayList

• 優(yōu)點(diǎn)：ArrayList是實(shí)現(xiàn)了基于動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，因?yàn)榈刂愤B續(xù)，一旦數(shù)據(jù)存儲(chǔ)好了，查詢操作效率會(huì)比較高（在內(nèi)存里是連著放的）。查詢快，增刪相對(duì)慢。
• 缺點(diǎn)：因?yàn)榈刂愤B續(xù)，ArrayList要移動(dòng)數(shù)據(jù)，所以插入和刪除操作效率比較低。

LinkedList

• 優(yōu)點(diǎn)：LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)，地址是任意的，所以在開辟內(nèi)存空間的時(shí)候不需要等一個(gè)連續(xù)的地址。對(duì)于新增和刪除操作add和remove，LinkedList比較占優(yōu)勢(shì)。LinkedList使用于要頭尾操作或插入指定位置的場(chǎng)景。
• 缺點(diǎn)：因?yàn)長(zhǎng)inkedList要移動(dòng)指針，所以查詢操作性能比較低。查詢慢，增刪快。

適用場(chǎng)景分析：

• 當(dāng)需要對(duì)數(shù)據(jù)進(jìn)行隨機(jī)訪問(wèn)的情況下，選用ArrayList。
• 當(dāng)需要對(duì)數(shù)據(jù)進(jìn)行多次增加刪除修改時(shí)，采用LinkedList。
• 當(dāng)然，絕大數(shù)業(yè)務(wù)的場(chǎng)景下，使用ArrayList就夠了。主要是，注意：最好避免ArrayList擴(kuò)容，以及非順序的插入。

ArrayList是如何擴(kuò)容的？

• 如果通過(guò)無(wú)參構(gòu)造的話，初始數(shù)組容量為0，當(dāng)真正對(duì)數(shù)組進(jìn)行添加時(shí)，才真正分配容量。每次按照1.5倍（位運(yùn)算）的比率通過(guò)copyOf的方式擴(kuò)容。

重點(diǎn)是1.5倍擴(kuò)容，這是和HashMap 2倍擴(kuò)容不同的地方。

5、ArrayList集合加入10萬(wàn)條數(shù)據(jù)，應(yīng)該怎么提高效率？

ArrayList的默認(rèn)初始容量為10，要插入大量數(shù)據(jù)的時(shí)候需要不斷擴(kuò)容，而擴(kuò)容是非常影響性能的。因此，現(xiàn)在明確了10萬(wàn)條數(shù)據(jù)了，我們可以直接在初始化的時(shí)候就設(shè)置ArrayList的容量！

這樣就可以提高效率了~

6、ArrayList和Vector區(qū)別？

ArrayList和Vector都是用數(shù)組實(shí)現(xiàn)的，主要有這么三個(gè)區(qū)別：

• 1、Vector是多線程安全的，線程安全就是說(shuō)多線程訪問(wèn)同一代碼，不會(huì)產(chǎn)生不確定的結(jié)果，而ArrayList不是。這個(gè)可以從源碼中看出，Vector類中的方法很多有synchronized進(jìn)行修飾，這樣導(dǎo)致了Vector在效率上無(wú)法與ArrayList相比。

Vector是一種老的動(dòng)態(tài)數(shù)組，是線程同步的，效率很低，一般不贊成使用。

• 2、兩個(gè)都是采用的線性連續(xù)空間存儲(chǔ)元素，但是當(dāng)空間不足的時(shí)候，兩個(gè)類的增加方式是不同。
• 3、Vector可以設(shè)置增長(zhǎng)因子，而ArrayList不可以，ArrayList集合沒(méi)有增長(zhǎng)因子。

適用場(chǎng)景分析：

• 1、Vector是線程同步的，所以它也是線程安全的，而ArrayList是線程無(wú)需同步的，是不安全的。如果不考慮到線程的安全因素，一般用ArrayList效率比較高。

實(shí)際場(chǎng)景下，如果需要多線程訪問(wèn)安全的數(shù)組，使用CopyOnWriteArrayList。

網(wǎng)頁(yè)題目：LinkedList源碼分析
URL分享：http://chinadenli.net/article12/dsoiodc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計(jì)、手機(jī)網(wǎng)站建設(shè)、電子商務(wù)、用戶體驗(yàn)、微信小程序、自適應(yīng)網(wǎng)站

廣告

聲明：本網(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)