双链表

单链表：无法逆向检索，有时候不太方便
双链表：可进可退，但存储密度要更低一点

双链表的初始化、插入、删除(带头结点)：

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

typedef struct DNode{
    int data;  //数据域
    struct DNode *prior,*next;  //指针域
}DNode,*DLinklist;  //DLinklist等价于DNode *

//初始化双链表
bool InitDLinkList(DLinklist *L){
    (*L)=(DNode *)malloc(sizeof(DNode));  //分配一个头结点
    if((*L) == NULL){  //内存不足，分配失败
        return false;
    }
    
    (*L)->prior=NULL;  //头结点的prior永远指向NULL
    (*L)->next=NULL;  //头结点之后暂时还没有结点
    return true;
}

//判断双链表是否为空(带头结点)
bool Empty(DLinklist *L){
    if((*L)->next == NULL){
        return true;
    }
    else{
        return false;
    }
}

//双链表的插入
//在p结点之后插入s结点
//如果要按位序插入，只需要从头结点找到这个位序的前驱结点，然后对这个前驱结点进行后插操作
//前插操作也是找到该结点的前驱结点，然后对这个前驱结点进行后插操作
bool InsertNextDNode(DNode *p,DNode *s){
    if(p == NULL || s == NULL){  //非法参数
        return false;
    }
    
    s->next=p->next;  //将结点*s插入到结点*p之后
    if(p->next != NULL){  //如果p结点有后继结点[如果是循环双链表，没有这个条件判断也是正确的]
        p->next->prior=s;
    }
    s->prior=p;
    p->next=s;
    return true;
}

//双链表的删除
//删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
    if(p == NULL){
        return false;
    }
    DNode *q=p->next;  //找到p的后继结点q
    if(q == NULL){
        return false;  //p没有后继
    }
    
    p->next=q->next;
    if(q->next != NULL){  //q结点不是最后一个结点
        q->next->prior=p;
    }
    free(q);  //释放结点空间
    return true;
}

//销毁一个双链表
void DestoryList(DLinklist *L){
    //循环释放各个数据结点
    while((*L)->next != NULL){
        DeleteNextDNode(*L);
    }
    free(L);  //释放头结点
    L=NULL;  //头指针指向NULL
}

int main(){
    
    DLinklist L;
    InitDLinkList(&L);  //初始化双链表
    
    //...后续代码
}

双链表的遍历[双链表不可随机存取，按位查找，按值查找操作都只能用遍历的方式实现，时间复杂度O(n)]

//后向遍历
while(p != NULL){
    p=p->next;
}
//前向遍历
while(p != NULL){
    p=p->prior;
}
//前向遍历，跳过头结点
while(p->prior != NULL){
    p=p->prior;
}