双向链表和双向循环链表的学习总结和C语言代码实现（数据结构学习4）

双向链表

定义

我们一开始学习的链表中各节点中都只包含一个指针（游标），且都统一指向直接后继节点，通常称这类链表为单向链表。

虽然使用单向链表能 100% 解决逻辑关系为 "一对一" 数据的存储问题，但在解决某些特殊问题时，单链表并不是效率最优的存储结构。比如说，如果算法中需要大量地找某指定节点的前驱节点，使用单链表无疑是灾难性的，因为单链表更适合 "从前往后" 找，而 "从后往前" 找并不是它的强项。

为了能够高效率解决类似的问题，就发明了双向链表。从名字上理解双向链表，即链表是 "双向" 的，如下图所示：

非空双向链表.png

从上图中可以看到，双向链表中各节点包含以下 3 部分信息（如下图所示）：

指针域 prior：用于指向当前节点的直接前驱节点；
数据域 data：用于存储数据元素。
指针域 next：用于指向当前节点的直接后继节点；

结点结构.png

因此，双链表的节点结构用 C 语言实现为：

typedef struct Node {
    struct Node *prior;//指向直接前驱节点
    ElemType data;//数据域
    struct Node *next;//指向直接后继节点
} Node;

注意：因为带头节点会更好操作，所以我的代码都有头节点。

1、双向链表的创建

同单链表相比，双链表仅是各节点多了一个用于指向直接前驱的指针域。因此，我们可以在单链表的基础轻松实现对双链表的创建。

//1、初始化双向链表（带头节点）
Status initLinkList(LinkList *list){
    
    //创建头节点
    *list = malloc(sizeof(Node));
    if (*list == NULL) {
        return ERROR;
    }
    (*list)->prior = NULL;
    (*list)->data = -1;
    (*list)->next = NULL;
    printf("已初始化链表~\n");
    return OK;
}

2、遍历双向链表

和单向链表遍历方式一模模一样样，这里就不多讲。我多加了一层使用prior指针逆序输出，相信有点基础的同学应该能一眼看明白。

//2、遍历双向链表
void printfLinkLisk(LinkList list){
    
    printf("遍历链表：\n");
    if (list == NULL || list->next == NULL) {
        printf("这是一个空链表\n");
        return;
    }
    LinkList p = list;
    //判断next是否全部正确
    printf("根据next从前往后遍历：");
    while (p->next) {
        printf("%d ",p->next->data);
        p = p->next;
    }
    printf("\n");
    
    //判断prior是否全部正确
    printf("根据prior从后往前遍历：");
    while (p != list) {
        printf("%d ",p->data);
        p = p->prior;
    }
    printf("\n");
}

3、根据索引位置添加节点

因为我的双向链表有头节点，所以只有两种添加情况：

添加至表的中间位置

同单链表添加数据类似，双向链表中间位置添加数据需要经过以下 4 个步骤(步骤中的顺序中 3 必须放到 1 和 2 后面，其它顺序可变)，如下图所示：

将priorNode->next节点的prior指向新节点；
将新节点->next指向原来的priorNode->next；
将priorNode->next指向新节点；
新节点的prior指向priorNode。

插入结点.png

添加至表尾

与添加到表中间的步骤只需要少掉步骤 1。因为priorNode->next是Null，不能用它执行操作，否则会崩溃。

//3、根据索引位置插入数据至链表中
Status insertLinkList(LinkList *list, int index, ElemType data){
    
    if (list == NULL || index < 0) {
        return ERROR;
    }
    int i = 0;
    LinkList priorNode = *list;
    //判断插入的位置，这里开始位置是0，index超过链表长度则插入末尾
    while (i < index && priorNode->next != NULL) {
        priorNode = priorNode->next;
        I++;
    }
    LinkList newNode = malloc(sizeof(Node));
    if (newNode == NULL) {
        return ERROR;
    }
    newNode->data = data;
    //插入操作共四步，看好了，别眨眼
    //1.将priorNode->next节点的前驱指向新节点
    if (priorNode->next) {
        priorNode->next->prior = newNode;
    }
    //2.将新节点->next指向原来的priorNode->next
    newNode->next = priorNode->next;
    //3.将priorNode->next指向新节点
    priorNode->next = newNode;
    //4.新节点的前驱指向priorNode
    newNode->prior = priorNode;
    return OK;
}

4、根据索引位置删除节点

根据索引删除节点时，只需遍历链表找到要删除的结点，更改前驱节点的next和后继节点的prior即可。

删除结点.png

//4、根据索引位置删除节点
Status deleteLinkListByIndex(LinkList *list, int index, ElemType *data){
    
    if (*list == NULL || index < 0) {
        return ERROR;
    }
    LinkList locaNode = *list;
    int i = 0;
    while (i <= index) {
        locaNode = locaNode->next;
        if (locaNode == NULL) {
            printf("没有这个你想要删除的节点\n");
            return ERROR;
        }
        I++;
    }
    
    //开始删除，只需要做两步
    //1、更改前驱节点的next
    locaNode->prior->next = locaNode->next;
    //2、更改后继节点的prior。
    if (locaNode->next) {
        locaNode->next->prior = locaNode->prior;
    }
    *data = locaNode->data;
    free(locaNode);
    return OK;
}

5、根据存储的值删除节点

根据值删除节点时，只需遍历链表找到要删除的结点，更改前驱节点的next和后继节点的prior即可。

//5、根据存储的值删除节点
Status deleteLinkListByData(LinkList *list, ElemType data){
    
    if (*list == NULL) {
        return ERROR;
    }
    LinkList locaNode = (*list)->next;
    while (locaNode) {
        if (locaNode->data == data) {
            break;
        }
        locaNode = locaNode->next;
    }
    if (locaNode == NULL) {
        printf("没有这个你想要删除的节点\n");
        return ERROR;
    }
    //开始删除，只需要做两步
    locaNode->prior->next = locaNode->next;
    if (locaNode->next) {
        locaNode->next->prior = locaNode->prior;
    }
    free(locaNode);
    return OK;
}

6、根据值查找节点

方法同单向链表

//6、查找元素
Status selectNode(LinkList list, ElemType data, LinkList *locaNode){
    
    if (list == NULL) {
        return ERROR;
    }
    LinkList p = list->next;
    while (p) {
        if (p->data == data) {
            *locaNode = p;
            break;
        }
        p = p->next;
    }
    if (*locaNode == NULL) {
        printf("没有这个你想要的节点\n");
        return ERROR;
    }
    else {
        return OK;
    }
}

其它辅助代码

#include "stdlib.h"

#define OK    1
#define ERROR 0

//元素类型
typedef int ElemType;
//状态类型
typedef int Status;
//定义节点结构体
typedef struct Node {
    struct Node *prior;
    ElemType data;
    struct Node *next;
} Node;

typedef Node *LinkList;

int main(int argc, const char * argv[]) {
    
    LinkList list;
    initLinkList(&list);
    
    for (int i = 0; i < 10; i ++) {
        insertLinkList(&list, i, i);
    }
    printfLinkLisk(list);
    
    int index, data;
    printf("输入你想插入的位置（从0开始）和存储的值:");
    scanf("%d %d",&index,&data);
    insertLinkList(&list, index, data);
    printfLinkLisk(list);
    
    printf("输入你想删除的位置（从0开始）:");
    scanf("%d",&index);
    deleteLinkListByIndex(&list, index, &data);
    printfLinkLisk(list);
    
    printf("输入你想删除的节点的值（只删最前的那个）:");
    scanf("%d",&data);
    deleteLinkListByData(&list, data);
    printfLinkLisk(list);
    
    printf("\n");
    return 0;
}

输出结果：

输入结果.png

双向循环链表

定义

双向循环链表和它名字的表意一样，就是把双向链表的两头连接，使其成为了一个环状链表。只需要将表中最后一个节点的next指针指向头节点，头节点的prior指针指向尾节点，链表就能成环儿，如图所示：

双向循环链表.png

需要注意的是，虽然双向循环链表成环状，但本质上还是双向链表，因此在双向循环链表中，依然能够找到头指针和头节点等。双向循环链表和双向链表相比，唯一的不同就是双向循环链表首尾相连，其他都完全一样。

注意：因为我上面已经讲了双向链表，所以这里只注重讲他们的实现差异。另因为带头节点会更好操作，所以我的代码都有头节点。

1、双向循环链表的创建

初始化时需要将头节点的next和prior都指向自己。

头节点.png

//1、初始化双向循环链表（带头节点）
Status initLinkList(LinkList *list){
    
    //创建头节点
    *list = malloc(sizeof(Node));
    if (*list == NULL) {
        return ERROR;
    }
    //前驱和后继都指向自己
    (*list)->prior = *list;
    (*list)->data = -1;
    (*list)->next = *list;
    printf("已初始化链表~\n");
    return OK;
}

2、遍历双向循环链表

注意它的尾节点的next不再是Null，而是头节点

//2、遍历双向循环链表
void printfLinkLisk(LinkList list){
    
    printf("遍历链表：\n");
    if (list == NULL || list->next == list) {
        printf("这是一个空链表\n");
        return;
    }
    LinkList p = list;
    //判断next是否全部正确
    printf("根据next从前往后遍历：");
    while (p->next != list) {
        printf("%d ",p->next->data);
        p = p->next;
    }
    printf("\n");
    
    //判断prior是否全部正确
    printf("根据prior从后往前遍历：");
    while (p != list) {
        printf("%d ",p->data);
        p = p->prior;
    }
    printf("\n");
}

3、根据索引位置添加节点

这里不需要判断尾节点的next是否为Null，因为它会指向头节点。

//3、根据索引位置插入数据至链表中
Status insertLinkList(LinkList *list, int index, ElemType data){
    
    if (list == NULL || index < 0) {
        return ERROR;
    }
    int i = 0;
    LinkList priorNode = *list;
    //判断插入的位置，这里开始位置是0，index超过链表长度则插入末尾
    while (i < index && priorNode->next != *list) {
        priorNode = priorNode->next;
        I++;
    }
    LinkList newNode = malloc(sizeof(Node));
    if (newNode == NULL) {
        return ERROR;
    }
    newNode->data = data;
    //插入操作共四步，看好了，别眨眼
    //1.将priorNode->next节点的前驱指向新节点
    priorNode->next->prior = newNode;
    //2.将新节点->next指向原来的priorNode->next
    newNode->next = priorNode->next;
    //3.将priorNode->next指向新节点
    priorNode->next = newNode;
    //4.新节点的前驱指向priorNode
    newNode->prior = priorNode;
    
    return OK;
}

4、根据索引位置删除节点

这里不需要判断尾节点的next是否为Null，因为它会指向头节点。

//4、根据索引位置删除节点
Status deleteLinkListByIndex(LinkList *list, int index, ElemType *data){
    
    if (*list == NULL || index < 0) {
        return ERROR;
    }
    LinkList locaNode = *list;
    int i = 0;
    //注意别删了头节点
    while (i <= index) {
        locaNode = locaNode->next;
        if (locaNode == *list) {
            printf("没有这个你想要删除的节点\n");
            return ERROR;
        }
        I++;
    }
    
    //开始删除，只需要做两步
    locaNode->prior->next = locaNode->next;
    locaNode->next->prior = locaNode->prior;
    *data = locaNode->data;
    free(locaNode);
    return OK;
}

5、根据存储的值删除节点

这里不需要判断尾节点的next是否为Null，因为它会指向头节点。

//5、根据存储的值删除节点
Status deleteLinkListByData(LinkList *list, ElemType data){
    
    if (*list == NULL) {
        return ERROR;
    }
    LinkList locaNode = (*list)->next;
    while (locaNode != *list) {
        if (locaNode->data == data) {
            break;
        }
        locaNode = locaNode->next;
    }
    if (locaNode == *list) {
        printf("没有这个你想要删除的节点\n");
        return ERROR;
    }
    //开始删除，只需要做两步
    locaNode->prior->next = locaNode->next;
    locaNode->next->prior = locaNode->prior;
    free(locaNode);
    return OK;
}

6、根据值查找节点

尾节点的next可是头节点哦，找到它就是最后一个了。

//6、查找元素
Status selectNode(LinkList list, ElemType data, LinkList *locaNode){
    
    if (list == NULL) {
        return ERROR;
    }
    LinkList p = list->next;
    while (p != list) {
        if (p->data == data) {
            *locaNode = p;
            break;
        }
        p = p->next;
    }
    if (*locaNode == NULL) {
        printf("没有这个你想要的节点\n");
        return ERROR;
    }
    else {
        return OK;
    }
}

其它辅助代码

#include "stdlib.h"

#define OK    1
#define ERROR 0

//元素类型
typedef int ElemType;
//状态类型
typedef int Status;
//定义节点结构体
typedef struct Node {
    
    struct Node *prior;
    ElemType data;
    struct Node *next;
} Node;

typedef Node *LinkList;

int main(int argc, const char * argv[]) {
    
    LinkList list;
    initLinkList(&list);
    
    for (int i = 0; i < 10; i ++) {
        insertLinkList(&list, i, i);
    }
    printfLinkLisk(list);
    
    int index, data;
    printf("输入你想插入的位置（从0开始）和存储的值:");
    scanf("%d %d",&index,&data);
    insertLinkList(&list, index, data);
    printfLinkLisk(list);

    printf("输入你想删除的位置（从0开始）:");
    scanf("%d",&index);
    deleteLinkListByIndex(&list, index, &data);
    printfLinkLisk(list);

    printf("输入你想删除的节点的值（只删最前的那个）:");
    scanf("%d",&data);
    deleteLinkListByData(&list, data);
    printfLinkLisk(list);
    
    printf("\n");
    return 0;
}

输出结果

输出结果.png

如有不对的地方，请指正，谢谢您的阅读～

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 194,491评论 5赞 459
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 81,856评论 2赞 371
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 141,745评论 0赞 319
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,196评论 1赞 263
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,073评论 4赞 355
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,112评论 1赞 272
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,531评论 3赞 381
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,215评论 0赞 253
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,485评论 1赞 290
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,578评论 2赞 309
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,356评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,215评论 3赞 312
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,583评论 3赞 299
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 28,898评论 0赞 17
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,174评论 1赞 250
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,497评论 2赞 341
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,697评论 2赞 335

双向链表和双向循环链表的学习总结和C语言代码实现（数据结构学习4）

双向链表

定义

1、双向链表的创建

2、遍历双向链表

3、根据索引位置添加节点

4、根据索引位置删除节点

5、根据存储的值删除节点

6、根据值查找节点

其它辅助代码

输出结果：

双向循环链表

定义

1、双向循环链表的创建

2、遍历双向循环链表

3、根据索引位置添加节点

4、根据索引位置删除节点

5、根据存储的值删除节点

6、根据值查找节点

其它辅助代码

输出结果

推荐阅读更多精彩内容