Java線(xiàn)性結(jié)構(gòu)中的雙向鏈表實(shí)現(xiàn)原理

更新時(shí)間：2023年07月10日 11:49:24 作者：一一哥Sun

這篇文章將給大家詳細(xì)講解雙向鏈表的內(nèi)容，尤其是會(huì)通過(guò)代碼來(lái)進(jìn)行鏈表的操作，文中的代碼示例介紹的非常詳細(xì)，具有一定的參考價(jià)值,需要的朋友可以參考下

一. 雙向鏈表簡(jiǎn)介

1. 概念

在上一篇文章中，我們?cè)诮榻B鏈表的種類(lèi)時(shí)，曾經(jīng)提到過(guò)雙向鏈表。雙向鏈表相比較于單鏈表，除數(shù)據(jù)域外，還具前和后兩個(gè)指向指針。

雙向鏈表中的結(jié)構(gòu)術(shù)語(yǔ)可以解釋為：

data：鏈表每個(gè)結(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)域；
next：鏈表每個(gè)結(jié)點(diǎn)中包含的指向下一個(gè)結(jié)點(diǎn)地址的指針域；
prev：鏈表每個(gè)結(jié)點(diǎn)中包含的前一個(gè)結(jié)點(diǎn)地址的指針域。

2. 編碼定義

根據(jù)上述對(duì)雙向鏈表結(jié)點(diǎn)的定義，我們給出雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)的Java定義實(shí)現(xiàn)：

class DNode{
    Object data;
    Node prev;
    Node next;
}

雙向鏈表是一條真實(shí)存在的鏈表，由多個(gè)結(jié)點(diǎn)組成。在實(shí)際的編程中，通常會(huì)標(biāo)記鏈表的兩個(gè)特殊結(jié)點(diǎn)，分別為：頭結(jié)點(diǎn)、尾結(jié)點(diǎn)。用另外一個(gè)變量size表示鏈表中元素的個(gè)數(shù)。

頭結(jié)點(diǎn)：鏈表中的第一個(gè)結(jié)點(diǎn)
尾結(jié)點(diǎn)：鏈表中的最后一個(gè)元素

因此有如下鏈表類(lèi)的定義：

public class DoubleLinkList{
    private int size;//大小
    private DNode head;//頭結(jié)點(diǎn)
    private DNode last;//尾結(jié)點(diǎn)
}

在本篇文章接下來(lái)的內(nèi)容中，我們將利用該DNode、DoubleLinkList兩個(gè)定義來(lái)實(shí)現(xiàn)雙向鏈表的各項(xiàng)操作。

二. 常見(jiàn)操作

因?yàn)殡p向鏈表是單鏈表的基礎(chǔ)上擴(kuò)展出來(lái)的結(jié)構(gòu)，因此雙向鏈表的很多操作與單鏈表的操作都是相同的，比如：查找元素、更新元素、插入元素、刪除元素。

1. 查找元素

1.1 查找頭結(jié)點(diǎn)

因?yàn)镈oubleLinkList中已經(jīng)記錄了頭結(jié)點(diǎn)head，因此頭結(jié)點(diǎn)的查找非常簡(jiǎn)單，如下：

public Object getHead(){
    if(head == null){
        return null;
    }
    return head.data;
}

時(shí)間復(fù)雜度為O(1)。

1.2 查找尾結(jié)點(diǎn)

與頭結(jié)點(diǎn)同理，查找尾結(jié)點(diǎn)的時(shí)間復(fù)雜度同樣為O(1），編碼如下：

public Object getLast(){
    if(last == null){
        return null;
    }
    return last.data;
}

1.3 查找指定位置結(jié)點(diǎn)

當(dāng)需要查找指定位置的結(jié)點(diǎn)元素時(shí)，雙向鏈表比單鏈表的實(shí)現(xiàn)方式有所不同，原因是：?jiǎn)捂湵硪驗(yàn)槭菃蜗虻?，因此只能從頭結(jié)點(diǎn)向后單向查找；但雙向鏈表前后均可查找，因此在進(jìn)行指定位置查找時(shí)，為了提高查找效率，會(huì)首先判斷要查找的位置處于鏈表的前半段還是后半段，若前半段則從頭結(jié)點(diǎn)向后查找，若后半段則從尾結(jié)點(diǎn)向前查找，具體編程如下所示：

public Object get(int index){
    //排除邊界異常
    if(index <0 || index>=size){
        return null;
    }
    //要查找的位置位于鏈表前半段
    if(index < (size>>1)){
        DNode x = head;
        for(int i = 0; i < index; i++){
            x = x.next;
        }
        return x.data;
    }else {//要查找的位置位于鏈表后半段
        DNode x = last;
        for(int i = size - 1; i >= index; i--){
            x = x.prev;
        }
        return x.data;
    }
}

在上述代碼中，size >> 1 的寫(xiě)法比較少見(jiàn)，“>>”在計(jì)算機(jī)編程中代表移位操作。常見(jiàn)的移位操作有兩種：

>>：向右移位操作，將一個(gè)二進(jìn)制位的操作數(shù)按指定移動(dòng)的位數(shù)向右移動(dòng)，移出位被丟棄，左邊移出的空位一律補(bǔ)0，或者補(bǔ)符號(hào)位。

<<：向左移位操作，將一個(gè)二進(jìn)制位的操作數(shù)按指定移動(dòng)的位數(shù)向左移動(dòng)，移出位被丟棄，右邊移出的空位一律補(bǔ)0。

通過(guò)實(shí)際的編程驗(yàn)證，我們可以知道：執(zhí)行右移1位操作，變量數(shù)據(jù)會(huì)縮小為原來(lái)的1/2。左移相反。同時(shí)，我們可以分析出時(shí)間復(fù)雜度為O(n)。

2. 更新元素

更新元素操作需要兩步：

找到要更新的元素
執(zhí)行更新操作

根據(jù)位置的不同，可以將更新操作分為三種情況：更新頭結(jié)點(diǎn)，更新尾結(jié)點(diǎn)，更新指定位置結(jié)點(diǎn)。

2.1 更新頭結(jié)點(diǎn)

更新頭結(jié)點(diǎn)代碼與查找頭結(jié)點(diǎn)類(lèi)似，如下：

public boolean updateHead(Object obj){
    if(head == null){
        return false;
    }
    head.data = obj;
    return true;
}

更新頭結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)。

2.2 更新尾結(jié)點(diǎn)

public boolean updateLast(Object obj){
    if(last == null){
        return false;
    }
    last.data = obj;
}

更新尾結(jié)點(diǎn)的時(shí)間復(fù)雜度同樣是O(1)。

2.3 更新指定位置結(jié)點(diǎn)

public boolean update(int index, Object obj){
    if(index < 0 || index >= size){
        return false;
    }
    if(index < (size>>1)){
        DNode x = head;
        for(int i = 0; i < index; i++){
            x = x.next;
        }
        x.data = obj;
    }else {
        DNode x = last;
        for(int i = size-1; i >= index; i--){
            x = last.prev;
        }
        x.data = obj;
    }
    return true;
}

如上代碼所示，修改指定結(jié)點(diǎn)元素的值采用的算法也是：先判斷要操作的位置在前半段還是后半段，然后再進(jìn)行精準(zhǔn)查找，最后執(zhí)行修改操作。

指定位置修改操作的時(shí)間復(fù)雜度為O(n)。

3. 插入元素

分析過(guò)了查找元素和更新元素操作的具體情況，我們很清晰的便能分析出插入元素操作的具體情況，其實(shí)也分為三種具體情景：頭結(jié)點(diǎn)位置插入，尾結(jié)點(diǎn)位置插入，指定位置插入元素。

3.1 頭結(jié)點(diǎn)位置插入

public boolean addHead(Object data){
    DNode h = head;
	DNode newNode = new DNode(null,data,h);
	head = newNode;
	if(h == null);{
        last = newNode;
    }else {
        h.prev = newNode;
    }
    size++;
    return true;
}

根據(jù)如上代碼，我們可以看到，在頭結(jié)點(diǎn)位置插入新的元素，只需要將新添加的結(jié)點(diǎn)置為head結(jié)點(diǎn)，同時(shí)處理好新結(jié)點(diǎn)和原鏈表中頭結(jié)點(diǎn)的指向關(guān)系即可。很明顯，頭結(jié)點(diǎn)位置插入的時(shí)間復(fù)雜度為O(1)。

3.2 尾結(jié)點(diǎn)位置插入

尾結(jié)點(diǎn)插入與頭結(jié)點(diǎn)插入原理相同，只需要替換為尾結(jié)點(diǎn)以及指針的指向。如下所示：

public boolean addLast(Object data){
    DNode l = last;
	DNode newNode = new DNode(l,data,null);
	last = newNode;
	if(last == null){
        head = last;
    }else {
        l.next = newNode;
    }
    size++;
    return true;
}

時(shí)間復(fù)雜度為O(1)。

3.3 指定位置插入

在進(jìn)行指定位置插入時(shí)，編程代碼稍多些，原因是需要以下幾步完成：

判斷插入的位置是否超范圍
若插入的位置在最后，則執(zhí)行在尾結(jié)點(diǎn)的插入邏輯
先根據(jù)要插入的位置，查找并獲取到對(duì)應(yīng)位置的結(jié)點(diǎn)元素
然后執(zhí)行插入邏輯

public boolean add(int index,Object data){
    if(index < 0 || index > size){
        return false;
    }
    if(index == size){
        addLast(data);
        return true;
    }else {
        //先找到要插入的指定位置的結(jié)點(diǎn)
        DNode x = index(index);
        //執(zhí)行插入操作
        DNode prevNode = x.prev;
        DNode newNode = new DNode(prevNode,data,x);
        x.prev = newNode;
        if(prevNode == null){
            head = newNode;
        }else {
            prevNode.next = newNode;
        }
        size++;
    }
}
//查找index位置上的結(jié)點(diǎn)并返回
public DNode index(int index){
    if( index < 0 || index >= size){
        return null;
    }
    if( index < (size>>1)){
        DNode x = head;
        for(int i = 0; i < index; i++){
            x = x.next;
        }
        return x;
    }else {
        DNode x = last;
        for(int i = size-1; i >= index; i--){
            x = x.prev;
        }
        return x;
    }
}

根據(jù)上述代碼，我們可以發(fā)現(xiàn)插入指定位置的代碼，需要用到查找指定位置的操作，先查找再插入，因此時(shí)間復(fù)雜度同樣為O(n)。

4. 刪除元素

有了前面的分析經(jīng)驗(yàn)，我們可以非常自然的分析出刪除操作同樣分三種：刪除頭結(jié)點(diǎn)、刪除尾結(jié)點(diǎn)、刪除指定結(jié)點(diǎn)。接下來(lái)，一起來(lái)看看詳細(xì)的情況：

4.1 刪除頭結(jié)點(diǎn)

public Object removeHead(){
    if(head == null){
        return null;
    }
    DNode h = head;
    Object data = h.data;
    DNode next = h.next;
    //將原來(lái)頭結(jié)點(diǎn)的數(shù)據(jù)域和指針域均賦值為null置空
    h.data = null;
    h.next = null;
    //將當(dāng)前結(jié)點(diǎn)的next作為新的頭結(jié)點(diǎn)
    head = next;
    //如果next為null，則說(shuō)明當(dāng)前鏈表只有一個(gè)節(jié)點(diǎn)，刪除該節(jié)點(diǎn)，則鏈表的first、last都為null
    if(next == null){
        last = null;
    }else {
        // next要作為新的頭節(jié)點(diǎn)，則其prev屬性為null
        next.prev = null;
    }
    size--;
    return data;
}

刪除頭結(jié)點(diǎn)只涉及頭結(jié)點(diǎn)的邏輯判斷和操作，因此刪除頭結(jié)點(diǎn)時(shí)間復(fù)雜度為O(1)。

4.2 刪除尾結(jié)點(diǎn)

與刪除頭結(jié)點(diǎn)原理相同，操作尾結(jié)點(diǎn)。代碼如下：

public Object removeLast(){
    DNode l = last;
    if(l == null){
        return null;
    }
    Object data = l.data;
    DNode prev = l.prev;
	//將當(dāng)前尾節(jié)點(diǎn)的屬性賦值為null，為了GC清理
    l.data = null;
    l.prev = null;
	// 讓當(dāng)前尾節(jié)點(diǎn)的prev作為新的尾節(jié)點(diǎn)，賦值給last屬性
    last = prev;
	// 如果prev為null，則說(shuō)明當(dāng)前鏈表只有一個(gè)節(jié)點(diǎn)，刪除該節(jié)點(diǎn)，則鏈表的first、last都為null
    if(prev == null){
        head = null;
    }else {
        // prev要作為新的尾節(jié)點(diǎn)，則其next屬性為null
        prev.next = null;
    }
    size--;
    return data;
}

很明顯，刪除尾結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)。

4.3 刪除指定結(jié)點(diǎn)

刪除指定結(jié)點(diǎn)的編碼實(shí)現(xiàn)如下：

public Object remove(int index){
    if(index < 0 || index >= size){
        return null;
    }
	//首先通過(guò)查找方法，查找到
	DNode node = index(index;
	//執(zhí)行刪除操作
	Object data = node.data;
	DNode next = node.next;
	DNode prev = node.prev;
	// 如果prev是null，則說(shuō)明刪除的是當(dāng)前頭節(jié)點(diǎn)，則將next作為新的頭節(jié)點(diǎn)，賦值給head
	if(prev == null){
        head = prev;
    }else {
        // 如果刪除的不是當(dāng)前頭節(jié)點(diǎn)，則將要?jiǎng)h除節(jié)點(diǎn)的prev與next連接一起，即將prev的next屬性賦值成next
        prev.next = next;
        // 如果prev不是null，則賦值為null
        node.prev = null;
    }
	// 如果next是null，則說(shuō)明刪除的是當(dāng)前尾節(jié)點(diǎn)，則將prev作為新的尾節(jié)點(diǎn)，賦值給last
	if(next == null){
        last = prev;
    }else {
        // 如果刪除的不是當(dāng)前尾節(jié)點(diǎn)，則將要?jiǎng)h除節(jié)點(diǎn)的prev與next連接一起，即將next的prev賦值成prev
        next.prev = prev;
        // 如果next不是null，則賦值為null
        node.next = null;
    }
	//將要?jiǎng)h除的結(jié)點(diǎn)的data數(shù)據(jù)域設(shè)置為null
	node.data = null;
	//鏈表的結(jié)點(diǎn)個(gè)數(shù)-1操作
	size--;
	return data;
}

如上代碼所示，刪除指定位置的結(jié)點(diǎn)元素也需要先執(zhí)行index(index)查找算法，至于index的實(shí)現(xiàn)，在前文介紹指定位置插入結(jié)點(diǎn)操作時(shí)，已經(jīng)進(jìn)行了實(shí)現(xiàn)，此處直接進(jìn)行使用。

我們不難分析得到，刪除指定位置的結(jié)點(diǎn)的時(shí)間復(fù)雜度是O(n)。

三. 其他操作

作為一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，除了對(duì)自身結(jié)點(diǎn)元素的一些操作，還有一些對(duì)鏈表狀態(tài)的獲取，比如鏈表的長(zhǎng)度，鏈表是否為空等，這里給大家介紹一下雙向鏈表的一些其他操作。

1. 鏈表的大小(元素結(jié)點(diǎn)的個(gè)數(shù))

public int size(){
    return size;
}

2. 判斷鏈表是否為空

public boolean isEmpty(){
    return size == 0;
}

3. 獲取鏈表元素組成的數(shù)組

public Object[] toArray(){
    Object[] result = new Object[size];
    int i = 0;
    for(DNode node = head; node != null; node = node.next){
        resunt[i++] = node.data;
    }
    return result;
}

4. 清空鏈表

public void clear(){
    for(DNode node = head; node != null; ){
        DNode next = node.next;
        node.data = null;
        node.next = null;
        node.prev = null;
        node = next;
    }
    head = last = null;
    size = 0;
}

四. 結(jié)語(yǔ)

至此，已經(jīng)連續(xù)用兩篇文章給大家介紹了鏈表的相關(guān)知識(shí)。在上一篇文章中，我們主要介紹了鏈表的基礎(chǔ)知識(shí)和單鏈表的常規(guī)操作，同時(shí)輔以圖示來(lái)說(shuō)明各種操作情況。在本篇文章中，主要是從Java編程角度作為切入點(diǎn)，來(lái)進(jìn)一步講解雙向鏈表的一些操作。特別是本篇文章中的大量代碼實(shí)踐，需要大家能夠理清邏輯關(guān)系，希望你可以動(dòng)手練起來(lái)哦。

以上就是Java線(xiàn)性結(jié)構(gòu)中的雙向鏈表實(shí)現(xiàn)原理的詳細(xì)內(nèi)容，更多關(guān)于Java 雙向鏈表實(shí)現(xiàn)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: