雙向鏈表

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。

雙線鏈表的結(jié)點.png

雙向鏈表.png

1.雙鏈表的結(jié)構(gòu)

/* 雙向鏈表的結(jié)構(gòu) */
typedef struct List{
    int data;           //  數(shù)據(jù)域
    struct List *next;      //  向后的指針
    struct List *front;     //  向前的指針
};

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

代碼實現(xiàn)如下

Status createLinkList(LinkList *L){
    
    //*L 指向頭結(jié)點
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    
    (*L)->prior = NULL;
    (*L)->next = NULL;
    (*L)->data = -1;
    
    //新增數(shù)據(jù)
    LinkList p = *L;
    for(int i=0; i < 10;i++){
        
        //1.創(chuàng)建1個臨時的結(jié)點
        LinkList temp = (LinkList)malloc(sizeof(Node));
        temp->prior = NULL;
        temp->next = NULL;
        temp->data = i;
        
        //2.為新增的結(jié)點建立雙向鏈表關(guān)系
        //① temp 是p的后繼
        p->next = temp;
        //② temp 的前驅(qū)是p
        temp->prior = p;
        //③ p 要記錄最后的結(jié)點的位置,方便下一次插入
        p = p->next;
        
    }
    
    return OK;
}

結(jié)果輸出

創(chuàng)建雙向鏈表成功.png

3.雙向鏈表的插入

首先我們來畫圖看看雙向鏈表的插入過程：

雙向鏈表的插入流程.png

第一步：首先找到插入位置，節(jié)點 T 將插入到P結(jié)點后面
第二步：將節(jié)點P-next 的前驅(qū)指向節(jié)點T，即 P->next->prior = T;
第三步：將節(jié)點 T 的后繼指向節(jié)點P->next 即 T->next = P->next;
第四步：將節(jié)點 P 的后繼指向節(jié)點 T 即 P->next = T;
第五步：將節(jié)點T 的前驅(qū)指向節(jié)點 P 即 T->prior = P;

代碼實現(xiàn)如下

Status InsertLinkList(LinkList *L,int place,int num){
    
    //1.插入的位置不合法 為0或者復(fù)述
    if (place < 1) return ERROR;
    
    //2.新建結(jié)點
    LinkList temp = (LinkList)malloc(sizeof(Node));
    temp->next = NULL;
    temp->prior = NULL;
    temp->data = num;
    
    //3.將p指向頭結(jié)點
    LinkList p = *L;
    
    //4.找到插入位置place的結(jié)點
    for (int i = 1; i< place; i++) {
        p = p->next;
    }
    
    //5.如果插入的位置超過鏈表本身的長度
    if (p == NULL)  return ERROR ;
    
    //6.判斷插入的位置是否為鏈表的尾部(p的后驅(qū)指針式NULL)
    if (p->next == NULL) {
        p->next = temp;
        temp->prior = p;
    }else{
        // 如果不在鏈表的尾部
        //1.將p->next結(jié)點的前驅(qū)指向插入結(jié)點（temp）
        p->next->prior = temp;
        
        //2.將tem的next只想 p的next的指向
        temp->next = p->next;
        
        // 3.p->next指向temp
        p->next = temp;
        
        // 4.temp的前驅(qū)指向p
        temp->prior = p;
     }
    return OK;
}

結(jié)果輸出

雙向鏈表的插入結(jié)果.png

這里需要注意處理當插入的位置在末位時候的情況,尾結(jié)點p的后繼指向新插入的結(jié)點(p->next = temp)，新插入的結(jié)點的前驅(qū)指向尾結(jié)點(temp->prior = p);

4.雙線鏈表的刪除

雙向鏈表的結(jié)點刪除.png

第一步：首先找到刪除結(jié)點Del
第二步：將節(jié)點Del->prior->next 的后繼指向節(jié)點Del->next，即 Del->prior->next = Del->next;
第三步：將節(jié)點 Del->next 的前驅(qū)指向節(jié)點p 即 Del->next->prior = Del->prior;
第四步：釋放結(jié)點Del

代碼實現(xiàn)如下

Status ListDelete(LinkList *L,int place){
    int k = 1;
    
    LinkList p = (*L);
    
    //1.判斷雙向鏈表是否為空
    if (*L == NULL) return ERROR;
    
    //2.將指針p移動到刪除元素的前一個位置
    while (k< place && p != NULL) {
        p = p->next;
        k++;
    }
    
    //3.如果k>place 或者p == NULL 則返回ERROR
    if (k > place || p == NULL) return ERROR;
    
    //4.創(chuàng)建臨時指針delTemp 指向要刪除的結(jié)點
    LinkList delTemp = p->next;
    
    //5.p-next 等于要刪除的結(jié)點的下一個結(jié)點
    p->next = delTemp->next;
    
    //6.如果刪除結(jié)點的下一個結(jié)點不為空 則將簡要刪除的下一個結(jié)點的前驅(qū)指針賦值p
    if (delTemp->next != NULL) {
        delTemp->next->prior = p;
    }
    
    return OK;
}

結(jié)果輸出

刪除雙向鏈表結(jié)點成功.png

5.查找某個元素的位置

代碼實現(xiàn)如下

int serachData(LinkList L,int value){
    if (L == NULL) return -1;
    LinkList p = L->next;
    int i = 1;
    while (p) {
        if (p->data == value) {
            return i;
        }
        i++;
        p = p->next;
    }
    
    return -1;
}

結(jié)果輸出

查詢雙向鏈表的位置.png

6.循環(huán)雙向鏈表的操作

循環(huán)雙向鏈表可以結(jié)合雙向鏈表和單向循環(huán)鏈表的處理邏輯來進行操作，這里不再做邏輯和代碼實現(xiàn)。