1.引子

假如已經(jīng)從A走到E了， 現(xiàn)在要求從E走到D,用時(shí)最短怎么辦？
傳統(tǒng)的循環(huán)鏈表只是從A->E->A->D, 但是現(xiàn)在明明可以只要E回退一步就到了D,何必那么麻煩呢  
這就需要用到一個(gè)指針 告訴E下一步需要走到D， 這個(gè)指針就是前驅(qū)指針.
也就引入了今天要介紹的雙向鏈表

雙向鏈表是在單鏈表的每個(gè)結(jié)點(diǎn)中，再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針。

雙向鏈表

2.代碼

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

typedef int ElementType;
typedef struct node {
    ElementType data;
    struct node *prior,*next;
} Node, *DoubleLinkList;


void InitDLLinkList(DoubleLinkList *list) {
    *list = (DoubleLinkList)malloc(sizeof(Node));
    (*list)->next = NULL;
    (*list)->prior = NULL;
}


void createDLinkList(DoubleLinkList list, int n) {
    DoubleLinkList p;
    p = list;
    for (int i = 1; i <= n; i++) {
        DoubleLinkList tempNode = (DoubleLinkList)malloc(sizeof(Node));
        tempNode->data = i;
        //將新結(jié)點(diǎn)的next和pror指針 與先后結(jié)點(diǎn)都建立關(guān)系
        p->next = tempNode;
        tempNode->prior = p;
        p = tempNode;
    }
    //將最后一個(gè)結(jié)點(diǎn)的next指向鏈表的頭部， 并將鏈表的前驅(qū)指針指向最后一個(gè)指針 形成雙向循環(huán)鏈表
    p->next = list;
    list->prior = p;
}

//求雙向鏈表的長(zhǎng)度  - 最后一個(gè)結(jié)點(diǎn)不等于頭結(jié)點(diǎn)
int DLLinkLength(DoubleLinkList list) {
    int allCount = 0;
    DoubleLinkList moveNode = list->next;
    while (moveNode != list) {
        moveNode = moveNode->next;
        allCount++;
    }
    return allCount;
}

//遍歷 - 正序
void IteratorDLLinkList(DoubleLinkList list) {
    DoubleLinkList moveNode = list->next;
    int k = 0;
    while (moveNode != list) {
        printf("current is %d\n",moveNode->data);
        moveNode = moveNode->next;
        k++;
    }
}

//遍歷 - 倒序
void reverse_itemratorList(DoubleLinkList list) {
    DoubleLinkList move = list->prior;
    int k = 0;
    while (move != list) {
        printf("current is %d\n",move->data);
        move = move->prior;
        k++;
    }
}


/** 插入情況是考慮已經(jīng)初始化和創(chuàng)建過(guò)鏈表了*/
Status insert_Node_DLList(DoubleLinkList list, int i, ElementType e) {
    int length = DLLinkLength(list);
    DoubleLinkList insertNode = malloc(sizeof(Node));
    insertNode->data = e;
    
    if (i < 0 || i > length+1) {
        return ERROR;
    }
    
    if (i == 0) {
        
        //1.將新結(jié)點(diǎn)的next指向 頭結(jié)點(diǎn)的next（即第一個(gè)存放數(shù)據(jù)的結(jié)點(diǎn)，此處可能為null）
        insertNode->next = list->next;
        //2.將頭結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)的前驅(qū)指針  指向當(dāng)前的插入結(jié)點(diǎn)
        list->next->prior = insertNode;
        //3.將頭結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)
        list->next = insertNode;
        //4.將新節(jié)點(diǎn)的前驅(qū)指針指向頭結(jié)點(diǎn)
        insertNode->prior = list;
    } else if (i == length+1) {
        
        //0.通過(guò)鏈表的前驅(qū)結(jié)點(diǎn)找到最后一個(gè)結(jié)點(diǎn)
        DoubleLinkList currentLast = list->prior;
        //1.將最后一個(gè)結(jié)點(diǎn)的next指針指向新節(jié)點(diǎn)
        currentLast->next = insertNode;
        //2.將新結(jié)點(diǎn)的前驅(qū)指針 指向當(dāng)前最后一個(gè)結(jié)點(diǎn)
        insertNode->prior = currentLast;
        //3.因?yàn)楫?dāng)前新節(jié)點(diǎn)成為了最后一個(gè)結(jié)點(diǎn)了， 所以新結(jié)點(diǎn)的next指針指向頭結(jié)點(diǎn)
        insertNode->next = list;
        //4.將頭結(jié)點(diǎn)的前驅(qū)指針 指向新結(jié)點(diǎn)
        list->prior = insertNode;
        
    } else {
        int currentIndex;
        DoubleLinkList currentNode = list;
        
        //0. 找到第i-1個(gè)位置的結(jié)點(diǎn)
        for (currentIndex = 1; currentIndex < i; currentIndex++) {
            currentNode = currentNode->next;
        }
        //1.將新結(jié)點(diǎn)的next指針  指向當(dāng)前i位置的結(jié)點(diǎn)
        insertNode->next = currentNode->next;
        //2.將當(dāng)前i位置結(jié)點(diǎn)的前驅(qū)指針 指向要插入的結(jié)點(diǎn)
        currentNode->next->prior = insertNode;
        //3.將第i-1個(gè)位置的next指針 指向新創(chuàng)建的結(jié)點(diǎn)
        currentNode->next = insertNode;
        //4.將新創(chuàng)建結(jié)點(diǎn)的前驅(qū)指針 指向第i-1個(gè)位置的結(jié)點(diǎn)
        insertNode->prior = currentNode;
    }
    return OK;
}


/** 刪除（i）結(jié)點(diǎn) 相當(dāng)于直接將 (i-1)結(jié)點(diǎn)的指針直接指向第 (i+1)個(gè)結(jié)點(diǎn)*/
int delete_node(DoubleLinkList list, int k) {
    int allCount = DLLinkLength(list);
    if (k < 0 || allCount < k) {
        return ERROR;
    }
    
    DoubleLinkList moveNode = list;
    DoubleLinkList deleteNode = list->next;
    if (k == 0) {
        //頭結(jié)點(diǎn)的next指針 直接指向刪除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
        moveNode->next = deleteNode->next;
        deleteNode->next->prior = moveNode;
    } else if(k == allCount) {
        
        //因?yàn)橐獎(jiǎng)h除最后一個(gè)結(jié)點(diǎn)  所以直接通過(guò)頭結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)找到要?jiǎng)h除的結(jié)點(diǎn)
        deleteNode = list->prior;
        //根據(jù)要?jiǎng)h除的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) 找到第k-1個(gè)結(jié)點(diǎn)
        moveNode = deleteNode->prior;
        //剩下兩步是綁定next和前驅(qū)指針
        moveNode->next = deleteNode->next;
        deleteNode->next->prior = moveNode->next;
        printf("刪除了");
    } else {
        
        //找到第k-1個(gè)結(jié)點(diǎn)
        for (int i = 1; i < k; i++) {
            moveNode = moveNode->next;
        }
        //找到要?jiǎng)h除的第k個(gè)結(jié)點(diǎn)
        deleteNode = moveNode->next;
        moveNode->next = deleteNode->next;
        deleteNode->next->prior = moveNode;
    }
    return OK;
}

void print_data(DoubleLinkList list) {
    IteratorDLLinkList(list);
    printf("length is %d\n",DLLinkLength(list));
    printf("\n\n");
}

void print_reverse_data(DoubleLinkList list) {
    reverse_itemratorList(list);
    printf("length is %d\n",DLLinkLength(list));
    printf("\n\n");
}

#pragma mark - 使用
void k_check_DoubleLink(void) {
    
    DoubleLinkList list;
    InitDLLinkList(&list);
    createDLinkList(list, 9);
   
    insert_Node_DLList(list, 0, 12);
    print_data(list);

    insert_Node_DLList(list, 5, 22);
    print_reverse_data(list);
    
    delete_node(list, 9);
    IteratorDLLinkList(list);
}