线性表 - 双向链表

1.引子

假如已经从A走到E了， 现在要求从E走到D,用时最短怎么办？
传统的循环链表只是从A->E->A->D, 但是现在明明可以只要E回退一步就到了D,何必那么麻烦呢  
这就需要用到一个指针 告诉E下一步需要走到D， 这个指针就是前驱指针.
也就引入了今天要介绍的双向链表

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针。

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;
        //将新结点的next和pror指针 与先后结点都建立关系
        p->next = tempNode;
        tempNode->prior = p;
        p = tempNode;
    }
    //将最后一个结点的next指向链表的头部， 并将链表的前驱指针指向最后一个指针 形成双向循环链表
    p->next = list;
    list->prior = p;
}

//求双向链表的长度  - 最后一个结点不等于头结点
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++;
    }
}


/** 插入情况是考虑已经初始化和创建过链表了*/
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.将新结点的next指向 头结点的next（即第一个存放数据的结点，此处可能为null）
        insertNode->next = list->next;
        //2.将头结点下一个结点的前驱指针  指向当前的插入结点
        list->next->prior = insertNode;
        //3.将头结点的next指针指向新结点
        list->next = insertNode;
        //4.将新节点的前驱指针指向头结点
        insertNode->prior = list;
    } else if (i == length+1) {
        
        //0.通过链表的前驱结点找到最后一个结点
        DoubleLinkList currentLast = list->prior;
        //1.将最后一个结点的next指针指向新节点
        currentLast->next = insertNode;
        //2.将新结点的前驱指针 指向当前最后一个结点
        insertNode->prior = currentLast;
        //3.因为当前新节点成为了最后一个结点了， 所以新结点的next指针指向头结点
        insertNode->next = list;
        //4.将头结点的前驱指针 指向新结点
        list->prior = insertNode;
        
    } else {
        int currentIndex;
        DoubleLinkList currentNode = list;
        
        //0. 找到第i-1个位置的结点
        for (currentIndex = 1; currentIndex < i; currentIndex++) {
            currentNode = currentNode->next;
        }
        //1.将新结点的next指针  指向当前i位置的结点
        insertNode->next = currentNode->next;
        //2.将当前i位置结点的前驱指针 指向要插入的结点
        currentNode->next->prior = insertNode;
        //3.将第i-1个位置的next指针 指向新创建的结点
        currentNode->next = insertNode;
        //4.将新创建结点的前驱指针 指向第i-1个位置的结点
        insertNode->prior = currentNode;
    }
    return OK;
}


/** 删除（i）结点 相当于直接将 (i-1)结点的指针直接指向第 (i+1)个结点*/
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) {
        //头结点的next指针 直接指向删除结点的下一个结点
        moveNode->next = deleteNode->next;
        deleteNode->next->prior = moveNode;
    } else if(k == allCount) {
        
        //因为要删除最后一个结点  所以直接通过头结点的前驱结点找到要删除的结点
        deleteNode = list->prior;
        //根据要删除的结点的前驱结点 找到第k-1个结点
        moveNode = deleteNode->prior;
        //剩下两步是绑定next和前驱指针
        moveNode->next = deleteNode->next;
        deleteNode->next->prior = moveNode->next;
        printf("删除了");
    } else {
        
        //找到第k-1个结点
        for (int i = 1; i < k; i++) {
            moveNode = moveNode->next;
        }
        //找到要删除的第k个结点
        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);
}