前言

我们在之前学双向带头循环链表时，结尾部分简单讲解了快速实现的方法。本篇博客将详细讲解如何迅速实现，通过思路草图的方法轻松写出带头双向循环链表，甚至都可以直接用注释画草图。本篇博客是对 "从零开始逐步实现带哨兵位循环双向链表" 的补充，之前在写那篇博客的时候不小心忘记实现销毁接口了，这里正好能进行一个补充。

一、代码讲解

如果有人叫你快速实现一个链表，我们当然首选带头双向循环链表，因为他足够简单，虽然结构很复杂，但是就是因为结构复杂，反而让我们能够轻轻松松地实现。

我们只需要把插入和删除两个接口实现，就可以把链表的头插尾插头删尾删都搞定。直接复用插入和删除两个接口即可轻松搞定。再写一些链表常见的功能就可以大功告成了！

要实现的功能如下：

链表的初始化和销毁，链表的打印和查找，链表的插入和删除，头删尾插头插尾插。

0x00 定义链表

💬 创建 DList.h 文件：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DListNodeDataType;
typedef struct DoubleListNode {
    DListNodeDataType data;  // 用来存放结点的数据
    struct DoubleListNode* next;  // 指向后继节点的指针
    struct DoubleListNode* prev;  // 指向前驱节点的指针
} DLNode;  // 重命名为DLNode
DLNode* DLNodeInit();
void DLNodeDestroy(DLNode* pHead);
void DLNodePrint(DLNode* pHead);
DLNode* DLNodeFind(DLNode* pHead, DListNodeDataType x);
void DLNodeInsert(DLNode* pos, DListNodeDataType x);
void DLNodeDelete(DLNode* pos);
void DLNodePushBack(DLNode* pHead, DListNodeDataType x);
void DLNodePushFront(DLNode* pHead, DListNodeDataType x);
void DLNodePopBack(DLNode* pHead);
void DLNodePopFront(DLNode* pHead);

0x01 初始化（DLNodeInit）

💬 创建 DList.c 文件：

#include "DList.h"
DLNode* DLNodeInit() {
    DLNode* pHead = (DLNode*)malloc(sizeof(DLNode)); // 创建哨兵位头结点
    pHead->next = pHead->prev = pHead; // 让next和prev一开始都默认指向pHead
    return pHead; // 将phead作为结果返回
}

🔑 解读：这里我们使用 malloc 函数开辟一块空间作为 "哨兵位" pHead ，next 和 prev 此时都应该指向 pHead 。最后再将 pHead 作为结果返回回去，外面就可以接收到了。

0x02 销毁（DLNodeDestroy）

💬 DList.c

void DLNodeDestroy(DLNode* pHead) {
    assert(pHead); // 防止pHead为空
    DLNode* cursor = pHead->next; // 因为pHead存的不是有效数据，所以要从pHead的下一个结点开始
    while (cursor != pHead) {  // 碰到哨兵位说明遍历完一遍了
        DLNode* next = cursor->next;  // 记录，防止free掉后cursor动不了
        free(cursor);  // 释放 cursor 当前指向的结点
        cursor = next;  // 让cursor继续往后走
    }
    free(pHead); // 干掉掉哨兵
    pHead = NULL; // 置空防野指针
}

🔑 解读：

① 这里创建一个叫 cursor 的指针，用来遍历整个链表。pHead 存的不是有效数据，所以要从pHead->next 开始。

49e15ac6b2236b23b3df3beab67ced94_25910b7ba1d348ea8aa6ecee241d593d.png

② 让 cursor 遍历每一个结点，直到碰到 pHead 结束，因为碰到 pHead 说明已经遍历完一遍了。

③ 进入循环后，创建一个 next 指针，提前记录一下 cursor->next ，可以有效阻止 free 掉之后 cursor 动不了的情况。释放完 cursor 后，再将 next 交给 cursor 就能让 cursor 继续往后走了。

④ 最后释放掉哨兵位，再把它置为空即可。

0x03 打印（DLNodePrint）

💬 DList.c

void DLNodePrint(DLNode* pHead) {
    assert(pHead);
    DLNode* cursor = pHead->next; // 因为pHead存的不是有效数据，所以要从pHead的下一个结点开始
    while (cursor != pHead) {  // 碰到哨兵位说明遍历完一遍了
        printf("%d", cursor->data); // 打印 cursor 当前指向的节点的数据
        cursor = cursor->next; // 让cursor继续往后走
    }
    printf("\n"); // 换行
}

🔑 解读：创建 cursor 指针遍历整个链表来打印数据。比较简单，这里就不过多赘述了。

0x04 查找（DLNodeFind）

💬 DList.c

DLNode* DLNodeFind(DLNode* pHead, DListNodeDataType x) {
    assert(pHead != NULL);
    DLNode* cursor = pHead->next;
    while (cursor != pHead) {
        if (cursor->data == x) {
            return cursor;    
        } else {
            cursor = cursor->next;
        }
    }
    return NULL;
}

🔑 解读：创建 cursor 指针，将 cursor->data 和 x 比较即可。

0x05 插入（DLNodeInsert）

📚 默认为 pos 位置前插入，既然是插入，我们先写好创建新结点的接口：

创建新结点（CreateNewNode）

DLNode* CreateNewNode(DListNodeDataType x) {
    DLNode* new_node = (DLNode*)malloc(sizeof(DLNode)); // 创建新结点，给一块DLNode大小的空间
    if(new_node == NULL) {  // 检查malloc
        printf("malloc failed!\n");
        exit(-1);
    }
    new_node->data = x;  // 放置数据
    new_node->next = new_node->prev = NULL;  // 默认置为空
    return new_node;
}

💬 DList.c

void DLNodeInsert(DLNode* pos, DListNodeDataType x) {
    // 思路草图： posPrev <->  new_node(待插目标) <->  pos
    assert(pos);
    DLNode* new_node = CreateNewNode(x); // 创建新节点
    DLNode* posPrev = pos->prev; // 创建pos的前驱指针
    // 把它们相互链接起来
    posPrev->next = new_node;
    new_node->prev = posPrev;
    new_node->next = pos;
    pos->prev = new_node;
}

🔑 解读：

① 首先创建新节点。因为是在 pos 位置之前插入。为了方便，我们先标出 pos 的前驱指针 posPrev，随后我们画出草图：

思路草图： posPrev <-> new_node(待插目标) <-> pos

这么一画，思路立马就清楚了，我们就可以轻轻松松把思路转换成代码：

② 将 posPrev 与 new_node 相互链接起来：

posPrev->next = new_node;
new_node->prev = posPrev;

③ 将 new_node 与 pos 相互链接起来：

new_node->next = pos;
pos->prev = new_node;

0x06 删除（DLNodeDelete）

📚 删除默认是删除 pos 位置的节点。

💬 DList.c

void DLNodeDelete(DLNode* pos) {
    // 思路草图：  posPrev   pos(待删目标）   posNext
    //               ↓_________________________↑
    assert(pos);
    DLNode* posPrev = pos->prev;
    DLNode* posNext = pos->next;
    // 把他们互相缝合起来
    posPrev->next = posNext; 
    posNext->prev = posPrev;
    // 删除pos位置的结点（释放并置空）
    free(pos);
    pos = NULL;
}

① 既然要删除 pos 位置的节点，我们先标出 pos 的前驱指针 posPrev 和 pos 的后继指针 posNext ，随后我们画出草图：

思路草图： posPrev pos(待删目标） posNext

↓_______________ ______↑

因为 pos 要被删掉了，我们需要把 posPrev 和 posNext 位置的两个节点互相缝合起来：

posPrev->next = posNext; 
posNext->prev = posPrev;

② 最后删除 pos 位置的结点，释放并置空。

0x07 尾插头插 / 尾删头删

📚 插入和删除都写好了，头插尾插和头删尾删直接复用就能轻松解决！

💬 DList.c

尾插（DLNodePushBack）
void DLNodePushBack(DLNode* pHead, DListNodeDataType x) {
    // 思路草图：  pHead   ...   end  (x)
    //            posPrev(end) <->  new_node(待插目标) <->  pos(pHead)
    assert(pHead);
    DLNodeInsert(pHead, x);
}

🔑 解读：直接调用插入接口即可。因为尾插要找到最后一个结点，所以我们传入 pHead 让它作为 pos，这样就能找到 posPrev，posPrev 就是最后一个节点。思路草图如下：

pHead   ...   end  (x)
posPrev(end) <->  new_node(待插目标) <->  pos(pHead)
头插（DLNodePushFront）
void DLNodePushFront(DLNode* pHead, DListNodeDataType x) {
    // 思路草图：  pHead     pHeadNext
    //            posPrev(pHead) <->  new_node(待插目标) <->  pos(pHeadNext)
    assert(pHead);
    DLNodeInsert(pHead->next, x);
}

🔑 解读：因为头结点是哨兵位，存得不是有效数据，所以它的头插要在哨兵位后面（即第一个有效数据前）。思路草图如下：

pHead     pHeadNext
posPrev(pHead) <->  new_node(待插目标) <->  pos(pHeadNext)
尾删（DLNodePopBack）
void DLNodePopBack(DLNode* pHead) {
    // 思路草图： pHead ... pos
    // 思路草图：  posPrev(endPrev)   pos(end / 待删目标）   posNext(pHead)
    //               ↓__________________________________________↑
    assert(pHead);
    DLNodeDelete(pHead->prev);
}

🔑 解读：尾删，默认删除的是 pos 位置的结点。所以我们直接传入要删除的结点即可。找到最后一个结点很简单，直接 pHead->prev 就是最后一个节点了，这就是结构的优势（而不像普通单链表要遍历链表找到尾指针）。思路草图如下：

pHead ... pos
posPrev(endPrev)   pos(end / 待删目标）   posNext(pHead)
   ↓_____________________________________↑
头删（DLNodePopFront）
void DLNodePopFront(DLNode* pHead) {
    // 思路草图： pHead  pos
    // 思路草图：  posPrev(pHead)   pos(pHead->next / 待删目标）   posNext(pHead->next->next)
    //               ↓_______________________________________________↑
    assert(pHead);
    DLNodeDelete(pHead->next);
}

🔑 解读：头删，删除第一个有效节点，传入 pHead->next 即可。思路草图如下：

pHead  pos
posPrev(pHead)   pos(pHead->next / 待删目标）   posNext(pHead->next->next)
     ↓________________________________________↑

二、完整代码

💬 DList.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DListNodeDataType;
typedef struct DoubleListNode {
    DListNodeDataType data;  // 用来存放结点的数据
    struct DoubleListNode* next;  // 指向后继节点的指针
    struct DoubleListNode* prev;  // 指向前驱节点的指针
} DLNode;  // 重命名为DLNode
DLNode* DLNodeInit();
void DLNodeDestroy(DLNode* pHead);
void DLNodePrint(DLNode* pHead);
DLNode* DLNodeFind(DLNode* pHead, DListNodeDataType x);
void DLNodeInsert(DLNode* pos, DListNodeDataType x);
void DLNodeDelete(DLNode* pos);
void DLNodePushBack(DLNode* pHead, DListNodeDataType x);
void DLNodePushFront(DLNode* pHead, DListNodeDataType x);
void DLNodePopBack(DLNode* pHead);
void DLNodePopFront(DLNode* pHead);

💬 DList.c

#include "DList.h"
DLNode* DLNodeInit() {
    DLNode* pHead = (DLNode*)malloc(sizeof(DLNode)); // 创建哨兵位头结点
    pHead->next = pHead->prev = pHead; // 让next和prev一开始都默认指向pHead
    return pHead; // 将phead作为结果返回
}
void DLNodeDestroy(DLNode* pHead) {
    assert(pHead); // 防止pHead为空
    DLNode* cursor = pHead->next; // 因为pHead存的不是有效数据，所以要从pHead的下一个结点开始
    while (cursor != pHead) {  // 碰到哨兵位说明遍历完一遍了
        DLNode* next = cursor->next;  // 记录，防止free掉后cursor动不了
        free(cursor);  // 释放 cursor 当前指向的结点
        cursor = next;  // 让cursor继续往后走
    }
    free(pHead); // 干掉掉哨兵
    pHead = NULL; // 置空防野指针
}
void DLNodePrint(DLNode* pHead) {
    assert(pHead);
    DLNode* cursor = pHead->next; // 因为pHead存的不是有效数据，所以要从pHead的下一个结点开始
    while (cursor != pHead) {  // 碰到哨兵位说明遍历完一遍了
        printf("%d", cursor->data); // 打印 cursor 当前指向的节点的数据
        cursor = cursor->next; // 让cursor继续往后走
    }
    printf("\n"); // 换行
}
DLNode* DLNodeFind(DLNode* pHead, DListNodeDataType x) {
    assert(pHead != NULL);
    DLNode* cursor = pHead->next;
    while (cursor != pHead) {
        if (cursor->data == x) {
            return cursor;    
        } else {
            cursor = cursor->next;
        }
    }
    return NULL;
}
DLNode* CreateNewNode(DListNodeDataType x) {
    DLNode* new_node = (DLNode*)malloc(sizeof(DLNode)); // 创建新结点，给一块DLNode大小的空间
    if(new_node == NULL) {  // 检查malloc
        printf("malloc failed!\n");
        exit(-1);
    }
    new_node->data = x;  // 放置数据
    new_node->next = new_node->prev = NULL;  // 默认置为空
    return new_node;
}
void DLNodeInsert(DLNode* pos, DListNodeDataType x) {
    // 思路草图： posPrev <->  new_node(待插目标) <->  pos
    assert(pos);
    DLNode* new_node = CreateNewNode(x); // 创建新节点
    DLNode* posPrev = pos->prev; // 创建pos的前驱指针
    // 把它们相互链接起来
    posPrev->next = new_node;
    new_node->prev = posPrev;
    new_node->next = pos;
    pos->prev = new_node;
}
void DLNodeDelete(DLNode* pos) {
    // 思路草图：  posPrev   pos(待删目标）   posNext
    //               ↓_________________________↑
    assert(pos);
    DLNode* posPrev = pos->prev;
    DLNode* posNext = pos->next;
    // 把他们互相缝合起来
    posPrev->next = posNext; 
    posNext->prev = posPrev;
    // 删除pos位置的结点（释放并置空）
    free(pos);
    pos = NULL;
}
void DLNodePushBack(DLNode* pHead, DListNodeDataType x) {
    // 思路草图：  pHead   ...   end  (x)
    //            posPrev(end) <->  new_node(待插目标) <->  pos(pHead)
    assert(pHead);
    DLNodeInsert(pHead, x);
}
void DLNodePushFront(DLNode* pHead, DListNodeDataType x) {
    // 思路草图：  pHead     pHeadNext
    //            posPrev(pHead) <->  new_node(待插目标) <->  pos(pHeadNext)
    assert(pHead);
    DLNodeInsert(pHead->next, x);
}
void DLNodePopBack(DLNode* pHead) {
    // 思路草图： pHead ... pos
    // 思路草图：  posPrev(endPrev)   pos(end / 待删目标）   posNext(pHead)
    //               ↓__________________________________________↑
    assert(pHead);
    DLNodeDelete(pHead->prev);
}
void DLNodePopFront(DLNode* pHead) {
    // 思路草图： pHead  pos
    // 思路草图：  posPrev(pHead)   pos(pHead->next / 待删目标）   posNext(pHead->next->next)
    //               ↓_______________________________________________↑
    assert(pHead);
    DLNodeDelete(pHead->next);
}

【数据结构】C语言版本的带哨兵位双向循环链表的快速实现方法

前言

一、代码讲解

0x00 定义链表

0x01 初始化（DLNodeInit）

0x02 销毁（DLNodeDestroy）

0x03 打印（DLNodePrint）

0x04 查找（DLNodeFind）

0x05 插入（DLNodeInsert）

0x06 删除（DLNodeDelete）

0x07 尾插头插 / 尾删头删

二、完整代码

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】C语言版本的带哨兵位双向循环链表的快速实现方法

前言

一、 代码讲解

0x00 定义链表

0x01 初始化（DLNodeInit）

0x02 销毁（DLNodeDestroy）

0x03 打印（DLNodePrint）

0x04 查找（DLNodeFind）

0x05 插入（DLNodeInsert）

0x06 删除（DLNodeDelete）

0x07 尾插头插 / 尾删头删

二、完整代码

热门文章

最新文章

相关课程

相关电子书

一、代码讲解