双链表(Double LinkList)

在单链表中, 无法逆向检索, 有时候不太方便, 于是有了双链表.

单链表只包含指向后继结点的指针, 双链表则是在单链表的基础上增加了一个指针域prior用于指向前驱结点.

0x01 双链表的定义

1
2
3
4
typedef struct DNode { //定义双链表结点类型
    int data; //数据域
    struct DNode* prior, * next; //前驱指针和后继指针
}DNode, * DLinklist;

或者:

1
2
3
4
5
6
struct DNode { //定义双链表结点类型
    int data; //数据域
    struct DNode* prior, * next; //前驱指针和后继指针
};
typedef struct DNode Dnode;
typedef struct DNode * DLinklist;

两者等价.

0x02 双链表的初始化

双链表中有前驱指针和后继指针, 初始化一个双链表时前驱指针和后继指针所指向的都是NULL.

双链表头指针的前驱指针和末尾结点的后继指针所指向的永远为NULL.

1
2
3
4
5
6
7
8
9
10
11
12
/***
 * @description: 初始化双链表
 * @param {DLinklist&} L
 * @return {*}
 */
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;
}

0x03 双链表的插入

以下代码演示的是双链表的后插操作, 但实际上只需要用后插操作就能完成双链表的一系列插入操作,
例如你将在某一个结点处实现前插操作时只需要在该结点的前一个结点(双链表很容易找到前驱结点)使用后插操作即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*** 
 * @description: 在p结点之后插入s结点
 * @param {DNode*} p
 * @param {DNode*} s
 * @return {*}
 */
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;
}

按位序插入可根据单链表的代码进行, 原理相同, 不再演示. (不是懒😤

0x04 双链表的删除

删除双链表其中一个结点的实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*** 
 * @description: 删除结点p
 * @param {DNode*&} p
 * @return {*}
 */
bool DeleteDNode(DNode*& p) {
    if (p->next) { //如果p不是末尾指针
        p->prior->next = p->next; //将p的前驱结点的后继指针改为指向p的后继结点
        p->next->prior = p->prior; //将p的后继结点的前驱指针改为指向p的前驱结点
        //看起来很绕,其实只是把原属于p的两个指针域让去(个人觉得这样好理解)
    }
    else { //如果p是末尾指针
        p->prior->next = NULL; //只需要把唯一与p相连的前驱结点的后继指针改为NULL即可
    }
    free(p);
    return true;
}

删除双链表其中一个结点的后继结点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*** 
 * @description: 删除p结点的后继结点
 * @param {DNode*} p
 * @return {*}
 */
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; //删除成功
}

彻底释放(销毁)一个双链表:

1
2
3
4
5
6
7
8
9
10
11
12
/*** 
 * @description: 释放(销毁)一个双链表
 * @param {DLinklist&} L
 * @return {*}
 */
void DestroyList(DLinklist& L) {
    //循环释放各个数据结点
    while (L->next != NULL)
        DeleteNextDNode(L);
    free(L); //释放头结点
    L = NULL; //头指针指向NULL
}

0x05 双链表的遍历

下方注释中的//···对结点p做相遇处理的代码行···指在次可以添加一些操作如打印、计数等.

后向遍历: 

1
2
3
4
while( p != NULL){
  //···对结点p做相遇处理的代码行···
  p = p->next;
}

前向遍历:

1
2
3
4
while( p != NULL){
  //···对结点p做相遇处理的代码行···
  p = p->prior;
}

向前遍历(跳过头结点):

1
2
3
4
while( p->prior !=NULL){
  //···对结点p做相遇处理的代码行···
  p = p->prior;
}

谢谢观看 😘