雙向鏈表是一種數(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 無(wú)前驅(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,無(wú)后繼節(jié)點(diǎn)則保存 null。
1.1.2 此外雙向鏈表還保存了兩個(gè)屬性:first 和 last 分別指向鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)。當(dāng)查詢節(jié)點(diǎn)數(shù)據(jù)時(shí)可以從后往前,也可以從前往后遍歷,提升查詢效率。
//節(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 添加元素-add2.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如果為空則表明鏈表之前無(wú)元素,那么新的節(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) – 在指定位置插入元素,其過(guò)程實(shí)際上就是斷開鏈,重新構(gòu)建鏈的過(guò)程。
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 刪除元素-remove2.2.1 remove(int index)-- 刪除指定位置的元素,其過(guò)程實(shí)際上依然是斷開鏈,重新構(gòu)建鏈的過(guò)程。
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)無(wú)其他引用,會(huì)被GC
x.item = null;
//節(jié)點(diǎn)-1
size--;
//修改次數(shù)+!
modCount++;
//返回x的元素
return element;
}
2.3 修改元素-set2.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è)?get2.4.1 獲取指定位置的節(jié)點(diǎn),返回該節(jié)點(diǎn)的元素。若查找的位置小于鏈表長(zhǎng)度的一半,則從頭結(jié)點(diǎn)開始順序查找;否則,從尾結(jié)點(diǎn)開始逆序查找,這樣做可以提高查詢效率。
注意點(diǎn):雙向鏈表中沒(méi)有下標(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的一半則說(shuō)明查詢的節(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的一半則說(shuō)明查詢的節(jié)點(diǎn)在鏈表中間的右半部分
//從last開始找效率更高
Nodex = last;
for (int i = size - 1; i >index; i--)
x = x.prev;
return x;
}
}
2.5 閱讀源碼技巧技巧:
你是否還在尋找穩(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)題來(lái)源:http://muchs.cn/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;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容
網(wǎng)頁(yè)設(shè)計(jì)公司知識(shí)