什么是雙鏈表

本篇內(nèi)容介紹了“什么是雙鏈表”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細閱讀，能夠?qū)W有所成！

雙鏈表與單鏈表區(qū)別

邏輯上它們均是線性表的鏈式實現(xiàn)，主要的區(qū)別是節(jié)點結(jié)構(gòu)上的構(gòu)造有所區(qū)別，這個區(qū)別從而引起操作的一些差異。 單鏈表：

單鏈表的一個節(jié)點，有儲存數(shù)據(jù)的data，還有后驅(qū)節(jié)點next(指針)。也就是這個單鏈表想要一些遍歷的操作都得通過前節(jié)點—>后節(jié)點。

雙鏈表：

雙鏈表的一個節(jié)點，有存儲數(shù)據(jù)的data,也有后驅(qū)節(jié)點next(指針)，這和單鏈表是一樣的，但它還有一個前驅(qū)節(jié)點pre(指針)。

雙鏈表結(jié)構(gòu)的設(shè)計

上文講單鏈表的時候，我們當時設(shè)計的是一個帶頭結(jié)點的鏈表就錯過了不帶頭結(jié)點操作方式，這里雙鏈表咱們就不帶頭結(jié)點設(shè)計實現(xiàn)。并且上文單鏈表實現(xiàn)的時候是沒有尾指針tail的，在這里我們設(shè)計的雙鏈表帶尾指針。

所以我們構(gòu)造的這個雙鏈表是：不帶頭節(jié)點、帶尾指針(tail)、雙向鏈表。

對于node節(jié)點：

class node<t> {
  T data;
	node<t> pre;
	node<t> next;

	public node() {
	}

	public node(T data) {
		this.data = data;
	}
}

對于鏈表：

public class doubleList<t> {
  private node<t> head;// 頭節(jié)點
	private node<t> tail;// 尾節(jié)點
	private int length;
    //各種方法	
}

具體操作分析

對于一個鏈表主要的操作還是增刪。增刪的話不光需要考慮鏈表是否帶頭節(jié)點，還有頭插、尾插、中間插等多種插入刪除形式，其中的一些細節(jié)處理也是比較重要的(防止鏈表崩掉出錯)，如果你對這塊理解不夠深入很容易寫錯也很難排查出來。當然，鏈表的查找、按位修改操作相比增刪操作還是容易很多。

初始化

雙鏈表在最初的時候頭指針指向為null。那么對于這個不帶頭節(jié)點的雙鏈表而言。它的head始終指向第一個真實有效的節(jié)點。tail也指向最后一個有效的節(jié)點。在最初的時候head=null，并且tail=head，此時鏈表為空，等待節(jié)點插入。

public doubleList() {
	head = null;
	tail = head;
	length = 0;
	}

插入

空鏈表插入

• 對于空鏈表來說。增加第一個元素可以特殊考慮。因為在鏈表為空的時候head和tail均為null。但head和tail又需要實實在在指向鏈表中的真實數(shù)據(jù)(帶頭指針就不需要考慮)。所以這時候就新建一個node讓head、tail等于它。

node<t> teamNode = new node(data);
if (isEmpty()) {
	head = teamNode;
	tail = teamNode;	
}

頭插

>對于頭插入來說。步驟很簡單，只需考慮head節(jié)點的變化。

1. 新建插入節(jié)點node

2. head前驅(qū)指向node

3. node后驅(qū)指向head

4. head指向node。(這時候head只是表示第二個節(jié)點，而head需要表示第一個節(jié)點故改變指向)

尾插：

>對于尾插入來說。只需考慮尾節(jié)點tail節(jié)點的變化。

1. 新建插入節(jié)點node

2. node前驅(qū)指向tail

3. tail后驅(qū)指向node

4. tail指向node。(這時候tail只是表示倒數(shù)第二個節(jié)點，而tail需要表示最后節(jié)點故指向node)

按編號插入

>對于編號插入來說。要考慮查找和插入兩部，而插入既和head無關(guān)也和tail無關(guān)。

1 新建插入節(jié)點node

2 找到欲插入node的前一個節(jié)點preNode。和后一個節(jié)點nextNode

3 node后驅(qū)指向nextNode,nextNode前驅(qū)指向node(此時node和后面與鏈表已經(jīng)聯(lián)立，但是和前面處理分離狀態(tài))

4 preNode后驅(qū)指向node。node前驅(qū)指向preNode(此時插入完整操作完畢)

整個流程的動態(tài)圖為：

刪除

只有單個節(jié)點刪除

>無論頭刪還是尾刪，遇到單節(jié)點刪除的需要將鏈表從新初始化！

if (length == 1)// 只有一個元素
{
	head = null;
	tail = head;
	length--;
}

頭刪除

>頭刪除需要注意的就是刪除不為空時候頭刪除只和head節(jié)點有關(guān)

流程大致分為：

1 head節(jié)點的后驅(qū)節(jié)點的前指針pre改為null。(head后面節(jié)點本指向head但是要刪除第一個先讓后面那個和head斷絕關(guān)系)

2 head節(jié)點指向head.next(這樣head就指向我們需要的第一個節(jié)點了，前面節(jié)點就被刪除成功，如果有c++等語言第一個被孤立的節(jié)點刪除釋放即可，但Java會自動釋放)

尾刪除

>尾刪除需要注意的就是刪除不為空時候尾刪除只和tail節(jié)點有關(guān)。記得在普通鏈表中，我們刪除尾節(jié)點需要找到尾節(jié)點的前驅(qū)節(jié)點。需要遍歷整個表，而雙向鏈表可以直接從尾節(jié)點遍歷到前面。

尾刪除就是刪除雙向鏈表中的最后一個節(jié)點，也就是尾指針所指向的那個節(jié)點，思想和頭刪除的思想一致，具體步驟為：

1. tail.pre.next=null尾節(jié)點的前一個節(jié)點(pre)的后驅(qū)節(jié)點等于null

2. tail=tail.pre 尾節(jié)點指向它的前驅(qū)節(jié)點，此時尾節(jié)點由于步驟1next已經(jīng)為null。完成刪除

普通刪除

>普通刪除需要重點掌握，普通刪除要妥善處理好待刪除節(jié)點的前后關(guān)系，具體流程如下：

1：找打待刪除節(jié)點node的前驅(qū)節(jié)點prenode(prenode.next是要刪除的節(jié)點)

2 : prenode.next.next.pre=prenode.（將待刪除node的后驅(qū)節(jié)點aftnode的pre指針指向prenode，等價于aftnode.pre=prenode）

3: prenode.next=prenode.next.next;此時node被跳過成功刪除。

完成刪除整個流程的動態(tài)圖為：

實現(xiàn)與測試

通過上面的思路簡單的實現(xiàn)一下雙鏈表，當然有些地方命名不太規(guī)范，實現(xiàn)效率有待提升，主要目的還是帶著大家理解。

代碼：

/*
 * 不帶頭節(jié)點的
 */
public class doubleList<t> {
    class node<t> {
        T data;
        node<t> pre;
        node<t> next;

        public node() {
        }

        public node(T data) {
            this.data = data;
        }
    }

    private node<t> head;// 頭節(jié)點
    private node<t> tail;// 尾節(jié)點
    private int length;

    public doubleList() {
        head = null;
        tail = head;
        length = 0;
    }

    boolean isEmpty() {
        return length == 0 ? true : false;
    }

    void addFirst(T data) {
        node<t> teamNode = new node(data);
        if (isEmpty()) {
            head = teamNode;
            tail = teamNode;

        } else {
            teamNode.next = head;
            head = teamNode;
        }
        length++;
    }

    void add(T data)// 默認尾節(jié)點插入
    {
        node<t> teamNode = new node(data);
        if (isEmpty()) {
            head = teamNode;
            tail = teamNode;
        } else {
            tail.next = teamNode;
            teamNode.pre=tail;
            tail = teamNode;
        }
        length++;
    }
    int length()
    {
        return length;
    }
    T getElum(int index)//為了簡單統(tǒng)一從頭找
    {
        node<t> team=head;
        for(int i=0;i<index;i++) 不帶頭節(jié)點 遍歷次數(shù)-1 { team="team.next;" } return team.data; void add(int index, t data) 編號插入 if (index="=" 0) addfirst(data); else length) add(data); 重頭戲 node teampre="teampre.next;" 為插入的前驅(qū) 無頭節(jié)點，index-1位置找到前驅(qū)節(jié)點 for (int i < index -1; i++) node<t> team = new node(data);// a c 中插入B 找打a
            team.next = teampre.next;// B.next=c
            teampre.next.pre = team;// c.pre=B
            team.pre = teampre;// 關(guān)聯(lián)a B
            teampre.next = team;
            length++;
        }
    }
    void deleteFirst()// 頭部刪除
    {
        if (length == 1)// 只有一個元素
        {
            head = null;
            tail = head;
            length--;
        } else {
            head = head.next;
            length--;
        }
    }
    void deleteLast() {
        if(length==1)
        {
            head=null;
            tail=head;
            length--;
        }
        else {

            tail.pre.next=null;
            tail=tail.pre;
            length--;

        }
    }
    void delete(int index)
    {
        if(index==0)deleteFirst();
        else if (index==length-1) {
            deleteLast();
        }
        else {//刪除 為了理解統(tǒng)一從頭找那個節(jié)點
            node<t>team=head;
            for(int i=0;i<index-1;i++) { team } 此時為要刪除的前節(jié)點 a c 插入b a為team team.next.next.pre="team;//c的前驅(qū)變成a" team.next="team.next.next;//a的后驅(qū)變成c" length--; void set(int index,t data) node<t>team=head;
        for(int i=0;i<index-1;i++) { team="team.next;" } team.data="data;" @override public string tostring() node<t> team = head;
        String vaString = "";
        while (team != null) {
            vaString += team.data + " ";
            team = team.next;
        }
        return vaString;
    }
}

測試：

“什么是雙鏈表”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！