文章目錄

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

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

雙向鏈表是一種數據結構，由若干個節點構成，其中每個節點均由三部分構成，分別是前驅節點，元素，后繼節點。雙向鏈表中的節點在內存中是游離狀態存在的。

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

1.1.1 如下圖，創建三個節點 ip0，ip1，ip2；ip0 無前驅節點則保存的地址為 null，保存元素為 2，后繼節點指向 ip1；ip1 前驅節點保存的地址為 ip0，保存元素為 5，后繼節點指向 ip2；ip2 前驅節點保存的地址為 ip1，保存元素為 2，無后繼節點則保存 null。

1.1.2 此外雙向鏈表還保存了兩個屬性：first 和 last 分別指向鏈表的頭節點和尾節點。當查詢節點數據時可以從后往前，也可以從前往后遍歷，提升查詢效率。

1.2 LinkedList 屬性

//節點數量
transient int size = 0;
//指向頭節點
transient Nodefirst;
//指向尾節點
transient Nodelast;

1.3 Node 節點對象

//Node為LinkedList的靜態內部類,static修飾類內部的成員。
private static class Node{//保存元素數據
    E item;
    //指向下一個節點地址
    Nodenext;
    //指向上一個節點地址
    Nodeprev;
    //創建節點并指向前后節點地址
    Node(Nodeprev, E element, Nodenext) {this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

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

2.1.1 add(E) – 在鏈表尾部添加元素，將元素封裝到節點中，創建新節點，讓新節點和前一個節點建立雙向鏈表的關系。

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

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

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

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

    if (index == size)
        //index == size 從尾部添加
        linkLast(element);
    else
        //從中間某個位置添加
        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的前驅節點pred
    final Nodepred = succ.prev;
    //新建節點,前驅節點指向pred,后繼節點指向succ
    final NodenewNode = new Node<>(pred, e, succ);
    //succ的前驅節點指向newNode新節點
    succ.prev = newNode;
    //如果前驅節點為null則first指向新節點
    if (pred == null)
        first = newNode;
    else
        //pred后繼節點指向newNode
        pred.next = newNode;
    //節點個數+1
    size++;
    modCount++;
}

2.2 刪除元素-remove

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

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

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

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

E unlink(Nodex) {//獲取下標為index的節點元素E
   final E element = x.item;
   //獲取下標為index的后繼節點
   final Nodenext = x.next;
   //獲取下標為index的前驅節點
   final Nodeprev = x.prev;
   //prev == null則表明刪除的是第一個節點
   if (prev == null) {   //first指向next
       first = next;
   } else {   //prev!=null則prev的next指向next
       prev.next = next;
       //x的前驅prev指向null
       x.prev = null;
   }
    //next==null則表明是在鏈表尾部刪除元素
   if (next == null) {   //尾節點指向prev(x的前面一個節點)
       last = prev;
   } else {//next!=null則next的prev指向prev
       next.prev = prev;
       //x的next指向null,至此x的四個鏈全部斷開
       x.next = null;
   }
   //x節點無其他引用,會被GC
   x.item = null;
   //節點-1
   size--;
   //修改次數+！
   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位置的節點
    Nodex = node(index);
    //獲取index位置的節點的元素
    E oldVal = x.item;
    //設值
    x.item = element;
    //返回index位置的節點的元素
    return oldVal;
}

2.4 查詢元素-get

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

注意點：雙向鏈表中沒有下標，index表示的是節點從頭結點開始的順序位置，index并不是雙向鏈表中的屬性。

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

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

2.5 閱讀源碼技巧

技巧：

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

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

分享名稱：LinkedList(JDK1.8)源碼+底層數據結構分析-創新互聯
標題來源：http://vcdvsql.cn/article34/cdegse.html

成都網站建設公司_創新互聯，為您提供App設計、企業建站、品牌網站制作、網站維護、商城網站、自適應網站

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯