双链表

双链表的定义

typedef struct DNode{
    int data;
    struct DNode *prior,*next;
}*DLinkList;

双链表的初始化(带头结点)

bool InitList(DLinkLIst &L){
    DNode L=(DNode*)malloc(sizeof(DNode));
    if(L==NULL)return false;
    L->next=NULL;
    L->prior=NULL;
    return true;
    }

双链表的插入

在p结点后插入s结点

bool InsertNextDNode(DNode *p,DNode *s){
    if(p==NULL||s==NULL)return false;
    s->prior=p;
    if(p->next!=NULL){
        p->next->prior=s;
    }
    s->next=p->next;
    p->next=s;
    return true;
}

双链表的删除

删除p的后继结点q

bool DeleteNextDNode(DNode *p){
    if(p->next==NULL)return false;
    DNode *q=p->next;
    if(q->next!=NULL){
    q->next->prior=p;
    }
    p->next=q->next;
    free(q);
    return true;
}

销毁双链表

void DestoryList(DLinkList &L){
    while(L->next!=NULL){ //循环释放各个数据结点
        DeleteNextDNode(L);
        free(L);
        L=NULL;
    }
}

遍历双链表

向后遍历

while(p!=NULL){
    p=p->next;
}

向前遍历

跳过头结点

while(p->prior!=NULL){
    p=p->prior;
}

知识回顾与重要考点