1.   雙向鏈表的插入操作

如圖所示：

對(duì)于每一次的雙向鏈表的插入操作，我們首先需要?jiǎng)?chuàng)建一個(gè)獨(dú)立的結(jié)點(diǎn)并通過(guò)malloc操作開(kāi)辟相應(yīng)的空間，其次我們選中這個(gè)新創(chuàng)建的獨(dú)立節(jié)點(diǎn)，將其的pre指針指向所需插入位置的前一個(gè)結(jié)點(diǎn)，同時(shí)，其所需插入的前一個(gè)結(jié)點(diǎn)的next指針修改指向?yàn)樵撔碌慕Y(jié)點(diǎn)，同理，該新的結(jié)點(diǎn)的next指針將會(huì)指向一個(gè)原本的下一個(gè)結(jié)點(diǎn)，而修改下一個(gè)結(jié)點(diǎn)的pre指針為指向新結(jié)點(diǎn)自身，這樣的一個(gè)操作我們稱(chēng)之為雙向鏈表的插入操作。

其代碼可以表示為：

//插入數(shù)據(jù)
line * insertLine(line * head,int data,int add){
    //三個(gè)參數(shù)分別為：進(jìn)行此操作的雙鏈表，插入的數(shù)據(jù)，插入的位置
    //新建數(shù)據(jù)域?yàn)閐ata的結(jié)點(diǎn)
    line * temp=(line*)malloc(sizeof(line));
    temp->data=data;
    temp->pre=NULL;
    temp->next=NULL;
    //插入到鏈表頭，要特殊考慮
    if (add==1) {
        temp->next=head;
        head->pre=temp;
        head=temp;
    }else{
        line * body=head;
        //找到要插入位置的前一個(gè)結(jié)點(diǎn)
        for (int i=1; i<add-1; i++) {
            body=body->next;
        }
        //判斷條件為真，說(shuō)明插入位置為鏈表尾
        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;
}

2.   雙向鏈表的刪除操作

如圖：

刪除操作的過(guò)程是：選擇需要?jiǎng)h除的結(jié)點(diǎn)，選中這個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，將前一個(gè)結(jié)點(diǎn)的next指針指向自己的下一個(gè)結(jié)點(diǎn)，同時(shí)，選中該節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，將下一個(gè)結(jié)點(diǎn)的pre指針修改指向?yàn)樽约旱纳弦粋€(gè)結(jié)點(diǎn)，這樣產(chǎn)生的效果就是在進(jìn)行遍歷的時(shí)候直接將這一個(gè)結(jié)點(diǎn)給跳過(guò)了。

在這樣的指針修改操作之后，我們釋放刪除結(jié)點(diǎn)，歸還空間給內(nèi)存，這樣的操作我們稱(chēng)之為雙鏈表的刪除操作。

其代碼可以表示為：

//刪除元素
line * deleteLine(line * head,int data){
    //輸入的參數(shù)分別為進(jìn)行此操作的雙鏈表，需要?jiǎng)h除的數(shù)據(jù)
    line * list=head;
    //遍歷鏈表
    while (list) {
        //判斷是否與此元素相等
        //刪除該點(diǎn)方法為將該結(jié)點(diǎn)前一結(jié)點(diǎn)的next指向該節(jié)點(diǎn)后一結(jié)點(diǎn)
        //同時(shí)將該結(jié)點(diǎn)的后一結(jié)點(diǎn)的pre指向該節(jié)點(diǎn)的前一結(jié)點(diǎn)
        if (list->data==data) {
            list->pre->next=list->next;
            list->next->pre=list->pre;
            free(list);
            printf("--刪除成功--\n");
            return head;
        }
        list=list->next;
    }
    printf("Error:沒(méi)有找到該元素，沒(méi)有產(chǎn)生刪除\n");
    return head;
}

3   雙向鏈表的遍歷

如同單鏈表的遍歷一樣，利用next指針逐步向后進(jìn)行索引即可，注意判斷這里，我們既可以用while(list)的操作直接判斷是否鏈表為空，也可以使用while(list->next)的操作判斷該鏈表是否為空，其下一節(jié)點(diǎn)為空和本結(jié)點(diǎn)是否為空的判斷條件是一樣的效果，當(dāng)然了，善用雙向鏈表的pre指針進(jìn)行有效的遍歷也是值得去嘗試的。

其簡(jiǎn)單的代碼可以表示為：

//遍歷雙鏈表,同時(shí)打印元素?cái)?shù)據(jù)
void printLine(line *head){
    line *list = head;
    int pos=1;
    while(list){
        printf("第%d個(gè)數(shù)據(jù)是:%d\n",pos++,list->data);
        list=list->next;
    }
}

4.   配套練習(xí)題目

雙向鏈表的單獨(dú)訓(xùn)練數(shù)據(jù)并不是很多，在網(wǎng)上的資料相比單鏈表也是偏少，不過(guò)我們?cè)谑煜ぴ碇罂梢酝瑔捂湵淼念}目，可以嘗試使用雙鏈表進(jìn)行做題，如下題：

1676題    1585題  

5.   本題目案例代碼

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

//遍歷雙鏈表,同時(shí)打印元素?cái)?shù)據(jù)
void printLine(line *head){
    line *list = head;
    int pos=1;
    while(list){
        printf("第%d個(gè)數(shù)據(jù)是:%d\n",pos++,list->data);
        list=list->next;
    }
}

//創(chuàng)建雙鏈表
line* initLine(line * head){
    int number,pos=1,input_data;
    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;
}

//插入數(shù)據(jù)
line * insertLine(line * head,int data,int add){
    //三個(gè)參數(shù)分別為：進(jìn)行此操作的雙鏈表，插入的數(shù)據(jù)，插入的位置
    //新建數(shù)據(jù)域?yàn)閐ata的結(jié)點(diǎn)
    line * temp=(line*)malloc(sizeof(line));
    temp->data=data;
    temp->pre=NULL;
    temp->next=NULL;
    //插入到鏈表頭，要特殊考慮
    if (add==1) {
        temp->next=head;
        head->pre=temp;
        head=temp;
    }else{
        line * body=head;
        //找到要插入位置的前一個(gè)結(jié)點(diǎn)
        for (int i=1; i<add-1; i++) {
            body=body->next;
        }
        //判斷條件為真，說(shuō)明插入位置為鏈表尾
        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;
}

//刪除元素
line * deleteLine(line * head,int data){
    //輸入的參數(shù)分別為進(jìn)行此操作的雙鏈表，需要?jiǎng)h除的數(shù)據(jù)
    line * list=head;
    //遍歷鏈表
    while (list) {
        //判斷是否與此元素相等
        //刪除該點(diǎn)方法為將該結(jié)點(diǎn)前一結(jié)點(diǎn)的next指向該節(jié)點(diǎn)后一結(jié)點(diǎn)
        //同時(shí)將該結(jié)點(diǎn)的后一結(jié)點(diǎn)的pre指向該節(jié)點(diǎn)的前一結(jié)點(diǎn)
        if (list->data==data) {
            list->pre->next=list->next;
            list->next->pre=list->pre;
            free(list);
            printf("--刪除成功--\n");
            return head;
        }
        list=list->next;
    }
    printf("Error:沒(méi)有找到該元素，沒(méi)有產(chǎn)生刪除\n");
    return head;
}

int main(){
    line *head=NULL;
    printf("創(chuàng)建雙鏈表操作\n"); 
    head=initLine(head);
    printLine(head);
//////////create line////////////
	printf("插入操作\n"); 
    head=insertLine(head,40,2);     //為了簡(jiǎn)化直接寫(xiě)參數(shù)了
    printLine(head);
//////////insert Line////////////
	printf("刪除操作\n"); 
    head=deleteLine(head,2);       //為了簡(jiǎn)化直接寫(xiě)參數(shù)了
    printLine(head);
//////////delete Line////////////  
    return 0;
}