LinkedList(JDK1.8)源碼+底層數(shù)據(jù)結(jié)構(gòu)分析-創(chuàng)新互聯(lián)

文章目錄

• 前言
• 一、雙向鏈表
• • 1.1 雙向鏈表示意圖
  • 1.2 LinkedList 屬性
  • 1.3 Node 節(jié)點(diǎn)對(duì)象
• 二、雙向鏈表的操作
• • 2.1 添加元素-add
  • 2.2 刪除元素-remove
  • 2.3 修改元素-set
  • 2.4 查詢?cè)?get
  • 2.5 閱讀源碼技巧

創(chuàng)新互聯(lián)從2013年開始，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元宣城做網(wǎng)站,已為上家服務(wù),為宣城各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:028-86922220前言

雙向鏈表是一種數(shù)據(jù)結(jié)構(gòu)，由若干個(gè)節(jié)點(diǎn)構(gòu)成，其中每個(gè)節(jié)點(diǎn)均由三部分構(gòu)成，分別是前驅(qū)節(jié)點(diǎn)，元素，后繼節(jié)點(diǎn)。雙向鏈表中的節(jié)點(diǎn)在內(nèi)存中是游離狀態(tài)存在的。

一、雙向鏈表 1.1 雙向鏈表示意圖

1.1.1 如下圖，創(chuàng)建三個(gè)節(jié)點(diǎn) ip0，ip1，ip2；ip0 無前驅(qū)節(jié)點(diǎn)則保存的地址為 null，保存元素為 2，后繼節(jié)點(diǎn)指向 ip1；ip1 前驅(qū)節(jié)點(diǎn)保存的地址為 ip0，保存元素為 5，后繼節(jié)點(diǎn)指向 ip2；ip2 前驅(qū)節(jié)點(diǎn)保存的地址為 ip1，保存元素為 2，無后繼節(jié)點(diǎn)則保存 null。

1.1.2 此外雙向鏈表還保存了兩個(gè)屬性：first 和 last 分別指向鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)。當(dāng)查詢節(jié)點(diǎn)數(shù)據(jù)時(shí)可以從后往前，也可以從前往后遍歷，提升查詢效率。

1.2 LinkedList 屬性

//節(jié)點(diǎn)數(shù)量
transient int size = 0;
//指向頭節(jié)點(diǎn)
transient Nodefirst;
//指向尾節(jié)點(diǎn)
transient Nodelast;

1.3 Node 節(jié)點(diǎn)對(duì)象

//Node為L(zhǎng)inkedList的靜態(tài)內(nèi)部類,static修飾類內(nèi)部的成員。
private static class Node{//保存元素?cái)?shù)據(jù)
    E item;
    //指向下一個(gè)節(jié)點(diǎn)地址
    Nodenext;
    //指向上一個(gè)節(jié)點(diǎn)地址
    Nodeprev;
    //創(chuàng)建節(jié)點(diǎn)并指向前后節(jié)點(diǎn)地址
    Node(Nodeprev, E element, Nodenext) {this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

二、雙向鏈表的操作 2.1 添加元素-add

2.1.1 add(E) – 在鏈表尾部添加元素，將元素封裝到節(jié)點(diǎn)中，創(chuàng)建新節(jié)點(diǎn)，讓新節(jié)點(diǎn)和前一個(gè)節(jié)點(diǎn)建立雙向鏈表的關(guān)系。

//在鏈表尾部添加元素
public boolean add(E e) { linkLast(e);
     return true;
}

//在鏈表尾部添加元素
void linkLast(E e) {//創(chuàng)建節(jié)點(diǎn)保存尾節(jié)點(diǎn)地址
    final Nodel = last;
    //創(chuàng)建新節(jié)點(diǎn),使其前驅(qū)指向l尾節(jié)點(diǎn)地址,next節(jié)點(diǎn)為空
    final NodenewNode = new Node<>(l, e, null);
    //last指向新節(jié)點(diǎn),newNode作為尾節(jié)點(diǎn)
    last = newNode;
    //l如果為空則表明鏈表之前無元素,那么新的節(jié)點(diǎn)也是頭節(jié)點(diǎn)
    if (l == null)
        first = newNode;
    else
        //不為空則表明之前有元素,l之前的尾節(jié)點(diǎn)的next指向newNode
        l.next = newNode;
    //新增成功,元素個(gè)數(shù)+1    
    size++;
    modCount++;
}

2.1.2 add(int index，E e) – 在指定位置插入元素，其過程實(shí)際上就是斷開鏈，重新構(gòu)建鏈的過程。

public void add(int index, E element) {//index下標(biāo)范圍檢查
    checkPositionIndex(index);

    if (index == size)
        //index == size 從尾部添加
        linkLast(element);
    else
        //從中間某個(gè)位置添加
        linkBefore(element, node(index));
}

//位置檢查
private void checkPositionIndex(int index) {if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isPositionIndex(int index) {return index >= 0 && index<= size;
}

void linkBefore(E e, Nodesucc) {// 獲取succ的前驅(qū)節(jié)點(diǎn)pred
    final Nodepred = succ.prev;
    //新建節(jié)點(diǎn),前驅(qū)節(jié)點(diǎn)指向pred,后繼節(jié)點(diǎn)指向succ
    final NodenewNode = new Node<>(pred, e, succ);
    //succ的前驅(qū)節(jié)點(diǎn)指向newNode新節(jié)點(diǎn)
    succ.prev = newNode;
    //如果前驅(qū)節(jié)點(diǎn)為null則first指向新節(jié)點(diǎn)
    if (pred == null)
        first = newNode;
    else
        //pred后繼節(jié)點(diǎn)指向newNode
        pred.next = newNode;
    //節(jié)點(diǎn)個(gè)數(shù)+1
    size++;
    modCount++;
}

2.2 刪除元素-remove

2.2.1 remove(int index)-- 刪除指定位置的元素，其過程實(shí)際上依然是斷開鏈,重新構(gòu)建鏈的過程。

public E remove(int index) {//元素下標(biāo)檢查
    checkElementIndex(index);
    return unlink(node(index));
}

元素下標(biāo)檢查
private void checkElementIndex(int index) {if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isElementIndex(int index) {//鏈表節(jié)點(diǎn)下標(biāo)從0開始,add方法index可以等于size,表明從鏈表尾部添加,刪除則不行,必須小于size。
    return index >= 0 && index< size;
}

E unlink(Nodex) {//獲取下標(biāo)為index的節(jié)點(diǎn)元素E
   final E element = x.item;
   //獲取下標(biāo)為index的后繼節(jié)點(diǎn)
   final Nodenext = x.next;
   //獲取下標(biāo)為index的前驅(qū)節(jié)點(diǎn)
   final Nodeprev = x.prev;
   //prev == null則表明刪除的是第一個(gè)節(jié)點(diǎn)
   if (prev == null) {   //first指向next
       first = next;
   } else {   //prev!=null則prev的next指向next
       prev.next = next;
       //x的前驅(qū)prev指向null
       x.prev = null;
   }
    //next==null則表明是在鏈表尾部刪除元素
   if (next == null) {   //尾節(jié)點(diǎn)指向prev(x的前面一個(gè)節(jié)點(diǎn))
       last = prev;
   } else {//next!=null則next的prev指向prev
       next.prev = prev;
       //x的next指向null,至此x的四個(gè)鏈全部斷開
       x.next = null;
   }
   //x節(jié)點(diǎn)無其他引用,會(huì)被GC
   x.item = null;
   //節(jié)點(diǎn)-1
   size--;
   //修改次數(shù)+！
   modCount++;
   //返回x的元素
   return element;
}

2.3 修改元素-set

2.3.1 set(int index，E e) – 將新元素替換指定位置的元素。

public E set(int index, E element) {//元素位置檢查
    checkElementIndex(index);
    //獲取index位置的節(jié)點(diǎn)
    Nodex = node(index);
    //獲取index位置的節(jié)點(diǎn)的元素
    E oldVal = x.item;
    //設(shè)值
    x.item = element;
    //返回index位置的節(jié)點(diǎn)的元素
    return oldVal;
}

2.4 查詢?cè)?get

2.4.1 獲取指定位置的節(jié)點(diǎn)，返回該節(jié)點(diǎn)的元素。若查找的位置小于鏈表長(zhǎng)度的一半，則從頭結(jié)點(diǎn)開始順序查找；否則，從尾結(jié)點(diǎn)開始逆序查找，這樣做可以提高查詢效率。

注意點(diǎn)：雙向鏈表中沒有下標(biāo)，index表示的是節(jié)點(diǎn)從頭結(jié)點(diǎn)開始的順序位置，index并不是雙向鏈表中的屬性。

public E get(int index) {//元素位置檢查
    checkElementIndex(index);
    return node(index).item;
}

Nodenode(int index) {//index小于size的一半則說明查詢的節(jié)點(diǎn)在鏈表中間的左半部分
    if (index< (size >>1)) {//從first開始找效率更高
        Nodex = first;
        for (int i = 0; i< index; i++)
            x = x.next;
        return x;
    } else {//index大于size的一半則說明查詢的節(jié)點(diǎn)在鏈表中間的右半部分
        //從last開始找效率更高
        Nodex = last;
        for (int i = size - 1; i >index; i--)
            x = x.prev;
        return x;
    }
}

2.5 閱讀源碼技巧

技巧：

• 先查看類的屬性，再觀察其構(gòu)造方法。
• 方法名見名知意，非核心代碼不需過度深究。
• 像類似的閱讀 Java 集合框架體系的源碼最重要的技巧就是學(xué)會(huì)畫圖，根據(jù)源碼再畫圖便豁然開朗。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享名稱：LinkedList(JDK1.8)源碼+底層數(shù)據(jù)結(jié)構(gòu)分析-創(chuàng)新互聯(lián)
標(biāo)題來源：http://www.jbt999.com/article34/cdegse.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計(jì)、企業(yè)建站、品牌網(wǎng)站制作、網(wǎng)站維護(hù)、商城網(wǎng)站、自適應(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；郵箱：[email protected]。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)