双向链表

单链表总是从头到尾来寻找结点，有了next指针，需要查找下一个结点的时间复杂度为O（1），但是如果要查找的是上一个结点的话，最坏的时间复杂度是O（n），原因是因为每次都必须要从头开始遍历查找

双向链表是在单链表的每个结点中，再设置一个指针，因此每个结点都有指针，分别指向直接后继和直接前驱，所以从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱和后继结点

双向链表数据结构

typedef struct DulNode {

    Elemtype data;

    struct DulNode *prior;

    struct DulNode *next;

}DulNode;

双向链表，所以某一个结点p，它的后继的前驱结点或者前驱的后继结点都是自己，即：

p->next->prior = p = p->prior->next

双向链表比单链表多了可以反向遍历查找等，但是在插入和删除的时候，也需要更改两个指针变量；插入和删除过程关键就地址转移过程，赋值的时候不要弄反了，可以动手画一画~！

#include <stdio.h>
#include <malloc.h>

typedef struct DouNode{
    int data;
    struct DouNode *prior;
    struct DouNode *next;
}DouNode;

DouNode* InitDouLinkList(int length){
    DouNode *d;
    d = (DouNode *)malloc(sizeof(DouNode));
    d->prior = NULL;
    d->next = NULL;
    d->data = 0;

    return d;
}

DouNode* AddNode(DouNode *d, int length){
    int i;
    i = 0;
    DouNode *p, *tmp;
    tmp = d;
    while (i < length){
        p = (DouNode *)malloc(sizeof(DouNode));
        p->prior = NULL;
        p->next = NULL;
        p->data = i;
        p->prior = tmp;
        tmp->next = p;
        tmp = tmp->next;
        i++;
    }
    return d;
}

DouNode* InsertNode(DouNode *d, int pos){
    DouNode *node, *tmp;
    node = (DouNode *)malloc(sizeof(DouNode));
    node->prior = NULL;
    node->next = NULL;
    node->data = 100;
    tmp = d;
    int i;
    i = 0;
    while (i < pos){
        tmp = tmp->next;
        i++;
    }
    node->next = tmp->next;
    tmp->next->prior = node;
    node->prior = tmp;
    tmp->next = node;

    return d;
}

DouNode* DeleteNode(DouNode *d, int pos){
    DouNode *tmp;
    int i;
    i = 0;
    tmp = d;
    while (i < pos){
        tmp = tmp->next;
        i++;
    }
    tmp->next->next->prior = tmp;
    tmp->next = tmp->next->next;

    return d;
}

int main(){
    DouNode *head, *DLinkList, *InsertLinkList, *DeleteLinkList;
    int len;
    len = 5;

    //create
    head = InitDouLinkList(len);

    //add node
    DLinkList = AddNode(head, 5);

    //insert node
    InsertLinkList = InsertNode(DLinkList, 3);

    //delete node
    DeleteLinkList = DeleteNode(InsertLinkList, 1);
    while (DeleteLinkList){
        printf(“%d “, DeleteLinkList->data);
        DeleteLinkList = DeleteLinkList->next;
    }
    printf(“\n”);
   
    return 0;
}