目前我們所學到的鏈表筐高，無論是動態(tài)鏈表還是靜態(tài)鏈表，表中各節(jié)點中都只包含一個指針（游標）以舒，且都統(tǒng)一指向直接后繼節(jié)點，通常稱這類鏈表為單向鏈表（或單鏈表）慢哈。

雖然使用單鏈表能 100% 解決邏輯關系為 "一對一" 數據的存儲問題蔓钟，但在解決某些特殊問題時，單鏈表并不是效率最優(yōu)的存儲結構卵贱。比如說奋刽，如果算法中需要大量地找某指定結點的前趨結點瓦侮，使用單鏈表無疑是災難性的，因為單鏈表更適合 "從前往后" 找佣谐，而 "從后往前" 找并不是它的強項肚吏。

為了能夠高效率解決類似的問題，本篇文章我們一起來討論雙向鏈表（簡稱雙鏈表）狭魂。
從名字上理解雙向鏈表罚攀，即鏈表是 "雙向" 的,如下圖所示：

雙向，指的是各節(jié)點之間的邏輯關系是雙向的雌澄，但通常頭指針只設置一個斋泄，除非實際情況需要。

從上圖中可以看到镐牺，雙向鏈表中各節(jié)點包含以下 3 部分信息（如下圖 所示）：

• 指針域：用于指向當前節(jié)點的直接前驅節(jié)點炫掐；
• 數據域：用于存儲數據元素。
• 指針域：用于指向當前節(jié)點的直接后繼節(jié)點睬涧；
  
  
  因此募胃，雙鏈表的節(jié)點結構用 C 語言實現(xiàn)為:

typedef struct Node
{
    struct Node * prior;//指向直接前趨
    int data;
    struct Node * next;//指向直接后繼
}Node;

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

同單鏈表相比，雙鏈表僅是各節(jié)點多了一個用于指向直接前驅的指針域畦浓。因此痹束，我們可以在單鏈表的基礎輕松實現(xiàn)對雙鏈表的創(chuàng)建。

需要注意的是讶请，與單鏈表不同祷嘶，雙鏈表創(chuàng)建過程中，每創(chuàng)建一個新節(jié)點夺溢，都要與其前驅節(jié)點建立兩次聯(lián)系论巍，分別是：

1. 將新節(jié)點的 prior 指針指向直接前驅節(jié)點；
2. 將直接前驅節(jié)點的 next 指針指向新節(jié)點风响；

這里給出創(chuàng)建雙向鏈表的 C 語言實現(xiàn)代碼：

Node* initNode(Node * head){
    head=(Node*)malloc(sizeof(Node));//創(chuàng)建鏈表第一個結點（首元結點）
    head->prior=NULL;
    head->next=NULL;
    head->data=1;
    Node * list=head;
    for (int i=2; i<=3; i++) {
        //創(chuàng)建并初始化一個新結點
        Node * body=(Node*)malloc(sizeof(Node));
        body->prior=NULL;
        body->next=NULL;
        body->data=i;
      
        list->next=body;//直接前趨結點的next指針指向新結點
        body->prior=list;//新結點指向直接前趨結點
        list=list->next;
    }
    return head;
}

我們可以嘗試著在 main 函數中輸出創(chuàng)建的雙鏈表环壤，C 語言代碼如下：

#include <stdio.h>
#include <stdlib.h>
//節(jié)點結構
typedef struct Node{
    struct Node * prior;
    int data;
    struct Node * next;
}Node;
//雙鏈表的創(chuàng)建函數
Node* initNode(Node * head);
//輸出雙鏈表的函數
void display(Node * head);

int main() {
    //創(chuàng)建一個頭指針
    Node * head=NULL;
    //調用鏈表創(chuàng)建函數
    head=initNode(head);
    //輸出創(chuàng)建好的鏈表
    display(head);
    //顯示雙鏈表的優(yōu)點
    printf("鏈表中第 4 個節(jié)點的直接前驅是：%d",head->next->next->next->prior->data);
    return 0;
}
Node* initNode(Node * head){
    //創(chuàng)建一個首元節(jié)點，鏈表的頭指針為head
    head=(Node*)malloc(sizeof(Node));
    //對節(jié)點進行初始化
    head->prior=NULL;
    head->next=NULL;
    head->data=1;
    //聲明一個指向首元節(jié)點的指針钞诡，方便后期向鏈表中添加新創(chuàng)建的節(jié)點
    Node * list=head;
    for (int i=2; i<=5; i++) {
        //創(chuàng)建新的節(jié)點并初始化
        Node * body=(Node*)malloc(sizeof(Node));
        body->prior=NULL;
        body->next=NULL;
        body->data=i;

        //新節(jié)點與鏈表最后一個節(jié)點建立關系
        list->next=body;
        body->prior=list;
        //list永遠指向鏈表中最后一個節(jié)點
        list=list->next;
    }
    //返回新創(chuàng)建的鏈表
    return head;
}
void display(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;
    }
}

程序運行結果：

1 <-> 2 <-> 3 <-> 4 <-> 5
鏈表中第 4 個節(jié)點的直接前驅是：3

雙向鏈表基本操作

下面繼續(xù)討論有關雙向鏈表的一些基本操作，即如何在雙向鏈表中添加荧降、刪除接箫、查找或更改數據元素。

創(chuàng)建好的雙向鏈表如下圖所示：

雙向鏈表添加節(jié)點

根據數據添加到雙向鏈表中的位置不同朵诫，可細分為以下 3 種情況：
添加至表頭
將新數據元素添加到表頭辛友，只需要將該元素與表頭元素建立雙層邏輯關系即可。

換句話說，假設新元素節(jié)點為 temp废累，表頭節(jié)點為 head邓梅，則需要做以下 2 步操作即可：

1. temp->next=head; head->prior=temp;
2. 將 head 移至 temp，重新指向新的表頭邑滨；

例如日缨，將新元素 7 添加至雙鏈表的表頭，則實現(xiàn)過程如下圖 所示：

1. 新節(jié)點先與其直接后繼節(jié)點建立雙層邏輯關系；
2. 新節(jié)點的直接前驅節(jié)點與之建立雙層邏輯關系哎壳；

lxQWmd.gif

1. 找到雙鏈表中最后一個節(jié)點；
2. 讓新節(jié)點與最后一個節(jié)點進行雙層邏輯關系归榕；

lxQ2OH.gif

因此尸红，雙向鏈表添加數據的 C 語言代碼，參考代碼如下：

Node * insertNode(Node * head,int data,int add){
    //新建數據域為data的結點
    Node * temp=(Node*)malloc(sizeof(Node));
    temp->data=data;
    temp->prior=NULL;
    temp->next=NULL;
    //插入到鏈表頭刹泄，要特殊考慮
    if (add==1) {
        temp->next=head;
        head->prior=temp;
        head=temp;
    }else{
        Node * body=head;
        //找到要插入位置的前一個結點
        for (int i=1; i<add-1; i++) {
            body=body->next;
        }
        //判斷條件為真外里，說明插入位置為鏈表尾
        if (body->next==NULL) {
            body->next=temp;
            temp->prior=body;
        }else{
            body->next->prior=temp;
            temp->next=body->next;
            body->next=temp;
            temp->prior=body;
        }
    }
    return head;
}

雙向鏈表刪除節(jié)點

雙鏈表刪除結點時，只需遍歷鏈表找到要刪除的結點循签，然后將該節(jié)點從表中摘除即可。
例如疙咸，刪除上面圖中的元素2县匠，如下圖所示：

lxliX4.gif

]
雙向鏈表刪除節(jié)點的 C 語言實現(xiàn)代碼如下：

//刪除結點的函數，data為要刪除結點的數據域的值
Node * delNode(Node * head,int data){
    Node * temp=head;
    //遍歷鏈表
    while (temp) {
        //判斷當前結點中數據域和data是否相等撒轮，若相等乞旦，摘除該結點
        if (temp->data==data) {
            temp->prior->next=temp->next;
            temp->next->prior=temp->prior;
            free(temp);
            return head;
        }
        temp=temp->next;
    }
    printf("鏈表中無該數據元素");
    return head;
}

雙向鏈表查找節(jié)點

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

C 語言實現(xiàn)代碼為：

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

雙向鏈表更改節(jié)點

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

實現(xiàn)此操作的 C 語言實現(xiàn)代碼如下：

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

基本上寫到這里這篇關于C語言實現(xiàn)雙向鏈表的文章就結束了缴川，總的實現(xiàn)代碼已經push到github，喜歡的小伙伴歡迎Star描馅！傳送門把夸，小編如果有什么寫的不好的地方，歡迎大家留言提出來流昏，多多指教扎即，如果還想了解其他語言實現(xiàn)的數據結構的相關算法，歡迎來我的個人博客相逢了解更多喲况凉！明天繼續(xù)更新C++語言實現(xiàn)雙向鏈表谚鄙，堅持就是勝利！加油刁绒！