1.  雙向鏈表的簡(jiǎn)介&概念

單鏈表在很多時(shí)候已經(jīng)可以勝任很多優(yōu)秀的操作了，但是，單鏈表任然存在不足，所謂‘單鏈表’，是指結(jié)點(diǎn)中只有一個(gè)指向其后繼的指針，具有單向性，有時(shí)需要搜索大量數(shù)據(jù)的時(shí)候，就必須要多次進(jìn)行從頭開始的遍歷，這樣的搜索不是很便利。

圖：?jiǎn)捂湵硎疽鈭D

對(duì)此在單鏈表的基礎(chǔ)上，產(chǎn)生了雙向鏈表的概念，即： 在單鏈表的基礎(chǔ)上，對(duì)于每一個(gè)結(jié)點(diǎn)設(shè)計(jì)一個(gè)前驅(qū)結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)與前一個(gè)結(jié)點(diǎn)相互連接，構(gòu)成一個(gè)鏈表。

雙向鏈表可以簡(jiǎn)稱為雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很方便地訪問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。

圖：雙向鏈表示意圖

一個(gè)完整的雙向鏈表應(yīng)該是頭結(jié)點(diǎn)的pre指針指為空，尾結(jié)點(diǎn)的next指針指向空，其余結(jié)點(diǎn)前后相鏈。

2. 雙向鏈表的結(jié)點(diǎn)設(shè)計(jì)

對(duì)于每一個(gè)結(jié)點(diǎn)而言，有：

其中，DATA表示數(shù)據(jù)，其可以是簡(jiǎn)單的類型（如int,double等等），也可以是復(fù)雜的結(jié)構(gòu)體（struct類型）；

pre代表的是前驅(qū)指針，它永遠(yuǎn)指向當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，注意，如果當(dāng)前結(jié)點(diǎn)是頭結(jié)點(diǎn)，則pre指針為空；

next代表的是后繼指針，它永遠(yuǎn)指向當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，注意，如果當(dāng)前結(jié)點(diǎn)是尾結(jié)點(diǎn)，則next指針為空

其代碼設(shè)計(jì)可以為：

typedef struct line{
    int data;           //data
    struct line *pre;   //pre node
    struct line *next;  //next node
}line,*a;
//分別表示該結(jié)點(diǎn)的前驅(qū)(pre)，后繼(next)，以及當(dāng)前數(shù)據(jù)(data)

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

對(duì)于創(chuàng)建雙向鏈表，我們需要先創(chuàng)建頭結(jié)點(diǎn)再逐步的進(jìn)行添加，請(qǐng)注意，雙向鏈表的頭結(jié)點(diǎn)是有數(shù)據(jù)元素的，也就是頭結(jié)點(diǎn)的data域中是存有數(shù)據(jù)的，這與一般的單鏈表是不同的。

對(duì)于逐步添加數(shù)據(jù)，我們采取的做法是，開辟一段新的內(nèi)存空間作為新的結(jié)點(diǎn)，為這個(gè)結(jié)點(diǎn)進(jìn)行的data進(jìn)行賦值，然后將已成鏈表的上一個(gè)結(jié)點(diǎn)的next指針指向自身，自身的pre指針指向上一個(gè)結(jié)點(diǎn)。

其代碼可以設(shè)計(jì)為：

//創(chuàng)建雙鏈表
line* initLine(line * head){
    int number,pos=1,input_data;
    //三個(gè)變量分別代表結(jié)點(diǎn)數(shù)量，當(dāng)前位置，輸入的數(shù)據(jù)
    printf("請(qǐng)輸入創(chuàng)建結(jié)點(diǎn)的大小\n");
    scanf("%d",&number);
    if(number<1){return NULL;} //輸入非法直接結(jié)束
    //////頭結(jié)點(diǎn)創(chuàng)建///////
    head=(line*)malloc(sizeof(line));
    head->pre=NULL;
    head->next=NULL;
    printf("輸入第%d個(gè)數(shù)據(jù)\n",pos++);
    scanf("%d",&input_data);
    head->data=input_data;
 
    line * list=head;
    while (pos<=number) {
        line * body=(line*)malloc(sizeof(line));
        body->pre=NULL;
        body->next=NULL;
        printf("輸入第%d個(gè)數(shù)據(jù)\n",pos++);
        scanf("%d",&input_data);
        body->data=input_data;
       
        list->next=body;
        body->pre=list;
        list=list->next;
    }
    return head;
}

初步看起來(lái)雙向鏈表似乎比單鏈表的兩種創(chuàng)建方法要復(fù)雜，其實(shí)將過(guò)程逐步拆解為 創(chuàng)建頭結(jié)點(diǎn)----創(chuàng)建一個(gè)新的結(jié)點(diǎn)----將頭結(jié)點(diǎn)和新結(jié)點(diǎn)相互鏈接----再度創(chuàng)建新結(jié)點(diǎn)……這樣的過(guò)程去思考，再反過(guò)頭多看幾遍代碼會(huì)有助于理解。