@

1.雙向鏈表的定義

上一節(jié)學(xué)習(xí)了單向鏈表單鏈表詳解。今天學(xué)習(xí)雙鏈表。學(xué)習(xí)之前先對單向鏈表和雙向鏈表做個回顧。
單向鏈表特點：
??1.我們可以輕松的到達(dá)下一個節(jié)點, 但是回到前一個節(jié)點是很難的.
??2.只能從頭遍歷到尾或者從尾遍歷到頭(一般從頭到尾)
雙向鏈表特點
??1.每次在插入或刪除某個節(jié)點時, 需要處理四個節(jié)點的引用, 而不是兩個. 實現(xiàn)起來要困難一些
??2.相對于單向鏈表, 必然占用內(nèi)存空間更大一些.
??3.既可以從頭遍歷到尾, 又可以從尾遍歷到頭
雙向鏈表的定義:
??雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。下圖為雙向鏈表的結(jié)構(gòu)圖。

??從上中可以看到，雙向鏈表中各節(jié)點包含以下 3 部分信息：
??指針域：用于指向當(dāng)前節(jié)點的直接前驅(qū)節(jié)點；
??數(shù)據(jù)域：用于存儲數(shù)據(jù)元素。
??指針域：用于指向當(dāng)前節(jié)點的直接后繼節(jié)點；

雙向循環(huán)鏈表的定義:
??雙向鏈表也可以進(jìn)行首尾連接，構(gòu)成雙向循環(huán)鏈表,如下圖所示
在創(chuàng)建鏈表時，只需要在最后將收尾相連即可（創(chuàng)建鏈表代碼中已經(jīng)標(biāo)出）。其他代碼稍加改動即可。

雙鏈表的節(jié)點結(jié)構(gòu)用 C 語言實現(xiàn)為：

/*隨機(jī)數(shù)的范圍*/
#define MAX 100
/*節(jié)點結(jié)構(gòu)*/
typedef struct Node{
    struct Node *pre;
    int data;
    struct Node *next;
}Node;

2.雙向鏈表的創(chuàng)建

??同單鏈表相比，雙鏈表僅是各節(jié)點多了一個用于指向直接前驅(qū)的指針域。因此，我們可以在單鏈表的基礎(chǔ)輕松實現(xiàn)對雙鏈表的創(chuàng)建。
??需要注意的是，與單鏈表不同，雙鏈表創(chuàng)建過程中，每創(chuàng)建一個新節(jié)點，都要與其前驅(qū)節(jié)點建立兩次聯(lián)系，分別是：
??將新節(jié)點的 prior 指針指向直接前驅(qū)節(jié)點；
??將直接前驅(qū)節(jié)點的 next 指針指向新節(jié)點；
??這里給出創(chuàng)建雙向鏈表的 C 語言實現(xiàn)代碼：

Node* CreatList(Node * head,int length)
{
    if (length == 1)
    {
        
        return( head = CreatNode(head));
    }
    else
    {
        head = CreatNode(head);
        Node * list=head;
        for (int i=1; i<length; i++) 
        /*創(chuàng)建并初始化一個新結(jié)點*/
        {
            Node * body=(Node*)malloc(sizeof(Node));
            body->pre=NULL;
            body->next=NULL;
            body->data=rand()%MAX;
			/*直接前趨結(jié)點的next指針指向新結(jié)點*/
            list->next=body;
            /*新結(jié)點指向直接前趨結(jié)點*/
            body->pre=list;
            /*把body指針給list返回*/
            list=list->next;
        }
         
    }
    /*加上以下兩句就是雙向循環(huán)鏈表*/
    // list->next=head;
    // head->prior=list;
    return head;
}

3.雙向鏈表的插入

??根據(jù)數(shù)據(jù)添加到雙向鏈表中的位置不同，可細(xì)分為以下 3 種情況：
1.添加至表頭
??將新數(shù)據(jù)元素添加到表頭，只需要將該元素與表頭元素建立雙層邏輯關(guān)系即可。
??換句話說，假設(shè)新元素節(jié)點為 temp，表頭節(jié)點為 head，則需要做以下 2 步操作即可：
??temp->next=head; head->prior=temp;
??將 head 移至 temp，重新指向新的表頭；
??將新元素 7 添加至雙鏈表的表頭，則實現(xiàn)過程如下圖所示：

2.添加至表的中間位置
??同單鏈表添加數(shù)據(jù)類似，雙向鏈表中間位置添加數(shù)據(jù)需要經(jīng)過以下 2 個步驟，如下圖所示：
??新節(jié)點先與其直接后繼節(jié)點建立雙層邏輯關(guān)系；
??新節(jié)點的直接前驅(qū)節(jié)點與之建立雙層邏輯關(guān)系；

3.添加至表尾
??與添加到表頭是一個道理，實現(xiàn)過程如下：
??找到雙鏈表中最后一個節(jié)點；
??讓新節(jié)點與最后一個節(jié)點進(jìn)行雙層邏輯關(guān)系；

/*在第add位置的前面插入data節(jié)點*/
Node * InsertListHead(Node * head,int add,int data)
{
    /*新建數(shù)據(jù)域為data的結(jié)點*/
    Node * temp=(Node*)malloc(sizeof(Node));
    if(head == NULL)
    {
        printf("malloc error!\r\n");
        return NULL;
    }    
    else
    {
        temp->data=data;
        temp->pre=NULL;
        temp->next=NULL; 
    }
    /*插入到鏈表頭，要特殊考慮*/
    if (add==1)
    {
        temp->next=head;
        head->pre=temp;
        head=temp;
    }
    else
    {
        Node * body=head;
        /*找到要插入位置的前一個結(jié)點*/
        for (int i=1; i<add-1; i++)
        {
            body=body->next;
        }
        /*判斷條件為真，說明插入位置為鏈表尾*/
        if (body->next==NULL)
        {
            body->next=temp;
            temp->pre=body;
        }
        else
        {
            body->next->pre=temp;
            temp->next=body->next;
            body->next=temp;
            temp->pre=body;
        }
    }
    return head;
}

```c
/*在第add位置的后面插入data節(jié)點*/
Node * InsertListEnd(Node * head,int add,int data)
{
    int i = 1;
    /*新建數(shù)據(jù)域為data的結(jié)點*/
    Node * temp=(Node*)malloc(sizeof(Node));
    temp->data=data;
    temp->pre=NULL;
    temp->next=NULL;

    Node * body=head;
    while ((body->next)&&(i<add+1))
    {
        body=body->next;
        i++;
    }
    
    /*判斷條件為真，說明插入位置為鏈表尾*/
    if (body->next==NULL)
    {
        body->next=temp;
        temp->pre=body;
        temp->next=NULL;
    }
    else
    {
        temp->next=body->pre->next;
        temp->pre=body->pre;
        temp->pre=body->pre;
        body->pre->next=temp;

    }

    return head;
}

4.雙向鏈表的刪除

??雙鏈表刪除結(jié)點時，只需遍歷鏈表找到要刪除的結(jié)點，然后將該節(jié)點從表中摘除即可。
??例如，刪除元素 2 的操作過程如圖 所示：

Node * DeleteList(Node * head,int data)
{
    Node * temp=head;
    /*遍歷鏈表*/
    while (temp)
    {
        /*判斷當(dāng)前結(jié)點中數(shù)據(jù)域和data是否相等，若相等，摘除該結(jié)點*/
        if (temp->data==data) 
        {
            /*判斷是否是頭結(jié)點*/
            if(temp->pre == NULL)
            {
                head=temp->next;
                temp->next = NULL;
                free(temp);
                return head;
            }
            /*判斷是否是尾節(jié)點*/
            else if(temp->next == NULL)
            {
                temp->pre->next=NULL;
                free(temp);
                return head;
            }
            else
            {
                temp->pre->next=temp->next;
                temp->next->pre=temp->pre;
                free(temp);
                return head;   
            }
            

        }
        temp=temp->next;
    }
    printf("Can not find %d!\r\n",data);
    return head;
}

5.雙向鏈表更改節(jié)點數(shù)據(jù)

??更改雙鏈表中指定結(jié)點數(shù)據(jù)域的操作是在查找的基礎(chǔ)上完成的。實現(xiàn)過程是：通過遍歷找到存儲有該數(shù)據(jù)元素的結(jié)點，直接更改其數(shù)據(jù)域即可。

/*更新函數(shù)，其中，add 表示更改結(jié)點在雙鏈表中的位置，newElem 為新數(shù)據(jù)的值*/
Node *ModifyList(Node * p,int add,int newElem)
{
    Node * temp=p;
    /*遍歷到被刪除結(jié)點*/
    for (int i=1; i<add; i++) 
    {
        temp=temp->next;
    }
    temp->data=newElem;
    return p;
}

6.雙向鏈表的查找

??通常，雙向鏈表同單鏈表一樣，都僅有一個頭指針。因此，雙鏈表查找指定元素的實現(xiàn)同單鏈表類似，都是從表頭依次遍歷表中元素。

/*head為原雙鏈表，elem表示被查找元素*/
int FindList(Node * head,int elem)
{
/*新建一個指針t，初始化為頭指針 head*/
    Node * temp=head;
    int i=1;
    while (temp) 
    {
        if (temp->data==elem)
        {
            return i;
        }
        i++;
        temp=temp->next;
    }
    /*程序執(zhí)行至此處，表示查找失敗*/
    return -1;
}

7.雙向鏈表的打印

/*輸出鏈表的功能函數(shù)*/
void PrintList(Node * head)
{
    Node * temp=head;
    while (temp) 
    {
        /*如果該節(jié)點無后繼節(jié)點，說明此節(jié)點是鏈表的最后一個節(jié)點*/
        if (temp->next==NULL) 
        {
            printf("%d\n",temp->data);
        }
        else
        {
            printf("%d->",temp->data);
        }
        temp=temp->next;
    }
}

8.測試函數(shù)及結(jié)果

int main() 
{
    Node * head=NULL;
    //創(chuàng)建雙鏈表
    head=CreatList(head,5);
    printf("新創(chuàng)建雙鏈表為\t");
    PrintList(head);
    //在表中第 5 的位置插入元素 1
    head=InsertListHead(head, 5,1);
    printf("在表中第 5 的位置插入元素 1\t");
    PrintList(head);
    //在表中第 3 的位置插入元素 7
    head=InsertListEnd(head, 3, 7);
    printf("在表中第 3 的位置插入元素 7\t");
    PrintList(head);
    // //表中刪除元素 7
    head=DeleteList(head, 7);
    printf("表中刪除元素 7\t\t\t");
    PrintList(head);
    printf("元素 1 的位置是\t：%d\n",FindList(head,1));
    //表中第 3 個節(jié)點中的數(shù)據(jù)改為存儲 6
    head = ModifyList(head,3,6);
    printf("表中第 3 個節(jié)點中的數(shù)據(jù)改為存儲6\t");
    PrintList(head);
    return 0;
}

??大家的鼓勵是我繼續(xù)創(chuàng)作的動力，如果覺得寫的不錯，歡迎關(guān)注，點贊，收藏，轉(zhuǎn)發(fā)，謝謝！
以上代碼均為測試后的代碼。如有錯誤和不妥的地方，歡迎指出。
部分內(nèi)容參考網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系刪除。
如遇到排版錯亂的問題，可以通過以下鏈接訪問我的CSDN。