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

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

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

一. 雙向鏈表簡介

1. 概念

在上一篇文章中，我們在介紹鏈表的種類時，曾經(jīng)提到過雙向鏈表。雙向鏈表相比較于單鏈表，除數(shù)據(jù)域外，還具前和后兩個指向指針。

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

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

2. 編碼定義

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

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

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

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

因此有如下鏈表類的定義：

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

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

二. 常見操作

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

1. 查找元素

1.1 查找頭結(jié)點

因為DoubleLinkList中已經(jīng)記錄了頭結(jié)點head，因此頭結(jié)點的查找非常簡單，如下：

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

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

1.2 查找尾結(jié)點

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

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

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

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

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 的寫法比較少見，“>>”在計算機編程中代表移位操作。常見的移位操作有兩種：

>>：向右移位操作，將一個二進制位的操作數(shù)按指定移動的位數(shù)向右移動，移出位被丟棄，左邊移出的空位一律補0，或者補符號位。

<<：向左移位操作，將一個二進制位的操作數(shù)按指定移動的位數(shù)向左移動，移出位被丟棄，右邊移出的空位一律補0。

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

2. 更新元素

更新元素操作需要兩步：

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

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

2.1 更新頭結(jié)點

更新頭結(jié)點代碼與查找頭結(jié)點類似，如下：

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

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

2.2 更新尾結(jié)點

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

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

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

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é)點元素的值采用的算法也是：先判斷要操作的位置在前半段還是后半段，然后再進行精準查找，最后執(zhí)行修改操作。

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

3. 插入元素

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

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

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é)點位置插入新的元素，只需要將新添加的結(jié)點置為head結(jié)點，同時處理好新結(jié)點和原鏈表中頭結(jié)點的指向關(guān)系即可。很明顯，頭結(jié)點位置插入的時間復(fù)雜度為O(1)。

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

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

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;
}

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

3.3 指定位置插入

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

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

public boolean add(int index,Object data){
    if(index < 0 || index > size){
        return false;
    }
    if(index == size){
        addLast(data);
        return true;
    }else {
        //先找到要插入的指定位置的結(jié)點
        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é)點并返回
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)插入指定位置的代碼，需要用到查找指定位置的操作，先查找再插入，因此時間復(fù)雜度同樣為O(n)。

4. 刪除元素

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

4.1 刪除頭結(jié)點

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

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

4.2 刪除尾結(jié)點

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

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

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

4.3 刪除指定結(jié)點

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

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

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

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

三. 其他操作

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

1. 鏈表的大小(元素結(jié)點的個數(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é)語

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

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

您可能感興趣的文章: