【数据结构】双链表

阅读本文，需要对C语言的知识有所掌握，参考我的C语言合集。

C语言合集

双链表

这里讨论的双链表是带头结点的情况。

1. 双链表的定义与初始化

相比于单链表，双链表多了一个指向前驱的指针。这样既可以向后查找，也可以向前查找。

定义一个双链表

typedef struct DNode{
    ElemType data;  // 数据域
    struct DNode *prior;  // 指向前驱结点
    struct DNode *next;  // 指向后继结点
}DNode,*DLinklist;

初始化双链表

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

注意：双链表的头结点前驱指针永远指向NULL。

2. 双链表的插入

// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
    if(p==NULL || s==NULL){
        return false;
    }
    s->next=p->next;
    if(p->next!=NULL){  // 如果p有后继结点，加这一步是防止如果p是最后一点结点报空指针的错误
        p->next->prior=s;
    }
    s->prior=p;
    p->next=s;
    return true;
}

3. 双链表的删除

// 删除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;
}

注意：对于插入和删除操作一定要注意执行语句的顺序。

4. 双链表的遍历

后向遍历

while(p!=NULL){
    // 对结点p做相应处理，如打印
    p=p->next;
}

前向遍历

while(p!=NULL){
    // 对结点p做相应处理
    p=p->prior;
}

前向遍历（跳过头结点）

while(p->prior!=NULL){
    // 对结点p做相应处理
    p=p->prior;
}

5. 判空操作

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

6. 销毁双链表

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

说明：

• 这个方法结合调用双链表的删除方法执行。
• 销毁表时才能删除头结点。

7. 小结

如需完整代码，微信公众号后台回复“线性表”即可领取。