网站导航
> 文档中心 > ＜ 数据结构 ＞ 双向带头循环链表

＜ 数据结构 ＞ 双向带头循环链表

网友: 文档中心 2022-04-02 14:36:55

目录

一、概念

二、必备工作

       2.1、创建双向链表结构

       2.2、初始化链表

       2.3、动态申请节点

       2.4、打印链表

       2.5、销毁链表

三、主要功能

       3.1、在pos节点前插入数据

                尾插

                头插

        3.2、删除pos处节点数据

                尾删

                头删

        3.3、查找数据

四、总代码

        List.h 文件

        List.c 文件

        Test.c 文件

五、拓展：对比顺序表与链表

一、概念

前文我们已经学习了单向链表，并通过oj题目深入了解了带头节点的链表以及带环链表，来画张图总体回顾下：

在我们学习的链表中，其实总共有8种，都是单双向和带不带头以及带不带环的任意组合

今儿要学习的是双向 - 带头 - 循环链表，听名字就觉着结构很复杂，要比曾经学的单向 - 不带头 - 不循环 链表的结构复杂的多 ，确实也是。先来画张图整体感受下：

  • 解释：
  1. 双向：就要确保每个数据存两个指针next和prev。next指向下一个节点，prev指向上一个节点
  2. 带头：带一个哨兵位的头节点在数据的最前头。
  3. 循环：尾节点的next指向哨兵位头节点，而哨兵位的上一个节点prev指向尾节点，构成循环。

正文开始：

二、必备工作

2.1、创建双向链表结构

因为是双向链表，所以在结构体里头必然有两个指针，一个next指向下一个节点，一个prev指向上一个节点。

  • List.h 文件：
//创建双向链表结构typedef int LTDataType;   //方便后续更改数据类型，本文以int整型为主typedef struct ListNode{LTDataType data; //存储数据struct ListNode* next; //指向下一个struct ListNode* prev; //指向上一个}LTNode; //方便后续使用，不需要重复些struct

2.2、初始化链表

  • 思路：

在初始化的时候要传地址，因为形参的改变不会影响实参，pphead的改变不会影响pList，要传pList的地址，用**pphead来接收，此时就要assert断言了，因为二级指针地址不可能位空。因为是双向循环链表，所以要将创建好的哨兵位节点的next和prev均指向自己。

  • List.h 文件：（1）
//初始化链表（二级指针版）void ListInit(LTNode* pphead);
  • List.c 文件：（1）
//初始化链表（二级指针版）void ListInit(LTNode** pphead){//传二级指针，那么当然要断言assert(pphead);*pphead = BuyLTNode(0);//因为是带哨兵位的头节点，所以一开始就要给一个节点//为了循环，要让哨兵位的next和prev均指向自己(*pphead)->next = *pphead; //注意优先级，*pphead要加括号(*pphead)->prev = *pphead;}
  • 注意：

上一种方法我们传的是二级指针，那么可以传一级指针吗，其实也是可以的，只需写个函数返回指针即可

  • List.h 文件：（2）
//初始化链表（一级指针版本）LTNode* ListInit();
  • List.c 文件：（2）
//初始化链表（一级指针版）LTNode* ListInit(){LTNode* phead = BuyLTNode(0);phead->next = phead;phead->prev = phead;return phead;}

2.3、动态申请节点

  • List.c 文件：
//创建新节点LTNode* BuyLTNode(LTDataType x){LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode; //返回新创建的节点}

2.4、打印链表

  • 思路：

既然是打印，首先要搞明白一点，哨兵位不用来存放有效数据，那么就不需要打印，定义一个cur指针来迭代，那么应该从phead的next开始打印，当cur走完一遍，重又回到phead的时候停止

  • List.h 文件：
//打印链表void ListPrint(LTNode* phead);
  • List.c 文件：
//打印链表void ListPrint(LTNode* phead){assert(phead);//断言LTNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");}

2.5、销毁链表

  • 思路：

既然是销毁链表了，那么自然是要把链表的所有元素包括哨兵位都给销毁掉，但毕竟刚开始传phead的时候是不能为空的，所以要断言，在把所有有效数据销毁后最后再销毁哨兵位即可。

法一：遍历

定义一个指针cur，从phead的next第一个有效数据开始free，保存下一个，再free，依次遍历下去

法二：附用ListErase函数

此法也可以，不过每次Erase完，都会把前后两个节点再链接起来，虽说最后都会销毁，但duck不必多此一举，所有直接采用法一比较好

  • List.h 文件：
//销毁链表void ListDestory(LTNode* phead);
  • List.c 文件：
//销毁链表void ListDestory(LTNode* phead){assert(phead);LTNode* cur = phead->next;//销毁从第一个节点到尾部的数据while (cur != phead){LTNode* next = cur->next;//ListErase(cur);free(cur);cur = next;}//置空哨兵位节点pheadfree(phead);phead = NULL;}
  • Test.c 文件：
void TestList7(){LTNode* pList = ListInit();for (int i = 1; i <= 7; i++){ListPushBack(pList, i); //尾插7个数字}ListPrint(pList);//打印//销毁链表ListDestory(pList);pList = NULL;}

三、主要功能

3.1、在pos节点前插入数据

  • 思路：

假设我们已经进行了尾插4个数字，现在想在数字3的前面插入30，那么首先就要查找有无数字3，若有，则插入。注意：这里需要用到后文才讲到的查找函数，这里直接引用了，详解看后文即可，问题不大！

首先，将30放到新创建的节点newnode里头，为了实现双向，要先把3的前一个数据2的next指向新节点newnode，把newnode的prev指向2，newnode的next指向3，3的prev指向newnode。

  •  List.h 文件：
//在pos前插入数据void ListInsert(LTNode* pos, LTDataType x);
  • List.c 文件：
//在pos前插入数据void ListInsert(LTNode* pos, LTDataType x){assert(pos);//创建插入数据的新节点LTNode* newnode = BuyLTNode(x);//链接左侧pos->prev->next = newnode;newnode->prev = pos->prev;//链接右侧newnode->next = pos;pos->prev = newnode;}
  • Test.c 文件：
void TestList3(){LTNode* pList = ListInit();for (int i = 1; i <= 7; i++){ListPushBack(pList, i); //尾插7个数据}ListPrint(pList);//打印尾插的7个//寻找数字LTNode* pos = ListFind(pList, 3);if (pos){ListInsert(pos, 30); //找到数字3就插入}ListPrint(pList);//打印}
  • 效果如下：

尾插

  • 思路：

首先，因为此链表是带哨兵位的头节点，所以头节点必然不为空，刚开始就要assert断言。其次，单链表尾插需要找尾，双向链表虽然也需要，不过非常简单，不需要再遍历链表了，因为哨兵位头节点的phead的上一个节点指向的就是尾，这就充分体现了双向循环的好处，找到了尾节点就需要再创建一个节点存储插入数据，方便尾插。

  • List.h 文件：
//尾插void ListPushBack(LTNode* phead, LTDataType x);

  • List.c 文件：1.0
//尾插1.0void ListPushBack(LTNode* phead, LTDataType x){assert(phead); //断言，防止头节点为空LTNode* tail = phead->prev; //找到尾节点，便于后续插入数据LTNode* newnode = BuyLTNode(x);//创建新节点//将此新插入的尾节点与上一个节点链接起来tail->next = newnode;newnode->prev = tail;//将尾节点与哨兵位phead链接起来构成循环newnode->next = phead;phead->prev = newnode;}
  • Test.c 文件：
void TestList1(){//初始化（法一）/*LTNode* pList = NULL;ListInit(&pList);*///初始化（法二）LTNode* pList = ListInit();for (int i = 1; i <= 7; i++){ListPushBack(pList, i); //尾插7个数据}ListPrint(pList);//打印尾插的7个}
  • 效果如下：

  • 注意：

在上文中，我们学习了在pos前插入数据，那么设想一下，当pos就等于phead的时候，它（phead）的前不就是链表的尾部吗，那么理所应当，尾插也可以这样完成：

  • List.c 文件：2.0
//尾插2.0void ListPushBack(LTNode* phead, LTDataType x){assert(phead); ListInsert(phead, x);}

头插

  • 思路：

前面我们已经学习了在pos前插入数据，那么头插的实现就尤为简单了，当pos为原第一个数据phead->next时，此时就是在其之前插入数据，那么实现的不久是头插吗，如下：

  • List.h 文件：
//头插void ListPushFront(LTNode* phead, LTDataType x);
  • List.c 文件：
//头插void ListPushFront(LTNode* phead, LTDataType x){assert(phead);ListInsert(phead->next, x);}
  • Test.c 文件：
void TestList4(){LTNode* pList = ListInit();for (int i = 1; i <= 7; i++){ListPushBack(pList, i); //尾插7个数字}ListPrint(pList);//打印for (int i = -2; i <= 0; i++){ListPushFront(pList, i); //头插3个数字}ListPrint(pList);//打印}
  • 效果如下：

3.2、删除pos处节点数据

  • 思路：

删除pos处数据其实也很简单，有点类似于把pos处直接忽略的思想，或者说是绕过去。首先，需要找到pos的上一个节点prev和下一个节点next，将prev和next互相链接即可，直接跳过了pos，这样就实现了删除pos处节点的数据，记得把pos处给free释放掉。这里我们以pos为2示例：

  •  List.h 文件：
//删除pos处数据void ListErase(LTNode* pos);
  • List.c 文件：
//删除pos处数据void ListErase(LTNode* pos){assert(pos);//定义两个指针保存pos两边的节点LTNode* prev = pos->prev;LTNode* next = pos->next;//将prev和next链接起来prev->next = next;next->prev = prev;//free释放free(pos);pos = NULL;}
  • Test.c 文件：
void TestList5(){LTNode* pList = ListInit();for (int i = 1; i <= 7; i++){ListPushBack(pList, i); //尾插7个数据}ListPrint(pList);//打印尾插的7个//寻找数字LTNode* pos = ListFind(pList, 3);if (pos){ListErase(pos); //删除pos处数据pos = NULL; //形参的改变不会影响实参，最好在这置空pos}ListPrint(pList);//打印}
  • 效果如下：

尾删

  • 思路：

双向循环链表的特点将再次得以体现，根据其特性，我们知道phead的prev指向尾节点，用tail指针保存，再定义一个指针tailPrev指向tail的prev，现仅需将tailPrev的next指向哨兵位节点phead，再把哨兵位phead的prev重新置成tailPrev即可，但是别忘记把删掉的尾节点给释放掉，得free(tail)。记得要断言链表不能为空，因为不能删除哨兵位节点。

  • List.H 文件：
//尾删void ListPopBack(LTNode* phead);
  • List.c 文件：1.0
//尾删void ListPopBack(LTNode* phead){assert(phead);//本身就有哨兵位，不能为空，要断言assert(phead->next != phead); //防止链表为空，导致删除哨兵位节点LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;//释放尾节点free(tail);tail = NULL;//将链表循环起来tailPrev->next = phead;phead->prev = tailPrev;}
  • Test.c 文件：
void TestList2(){LTNode* pList = ListInit();for (int i = 1; i <= 7; i++){ListPushBack(pList, i); //尾插7个数据}ListPrint(pList);//打印尾插的7个//尾删两次ListPopBack(pList);ListPopBack(pList);ListPrint(pList);//再次打印}
  • 效果如下：

  •  注意：

前文我们已经学了删除pos处节点的数据，那么当pos为phead->prev时，删除的是不是就是尾节点，所以，尾删理所应当可以这样写：

  • List.c 文件：2.0
//尾删void ListPopBack(LTNode* phead){assert(phead);//本身就有哨兵位，不能为空，要断言assert(phead->next != phead); //防止链表为空，导致删除哨兵位节点ListErase(phead->prev);}

头删

  • 思路：

有了上文之鉴，我们可以直接利用前面写的删除pos处数据的函数来完成，当pos为phead->prev时，pos的位置就是尾，此时删除的就是尾。当然还得注意一点，需要额外assert断言防止删除的数据为哨兵位的节点。

  • List.h 文件：
//头删void ListPopFront(LTNode* phead);
  • List.c 文件：
//头删void ListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead); //防止删除哨兵位节点ListErase(phead->next);}
  • Test.c 文件：
void TestList6(){LTNode* pList = ListInit();for (int i = 1; i <= 7; i++){ListPushBack(pList, i); //尾插7个数字}ListPrint(pList);//打印//头插3个数字ListPushFront(pList, 0);ListPushFront(pList, -1);ListPushFront(pList, -2);ListPrint(pList);//打印//尾删3个数字ListPopBack(pList);ListPopBack(pList);ListPopBack(pList);ListPrint(pList);//打印//头删3个数字ListPopFront(pList);ListPopFront(pList);ListPopFront(pList);ListPrint(pList);//打印}
  • 效果如下：

3.3、查找数据

  • 思路：

查找数据其实也比较简单，首先，定义一个指针cur指向哨兵位phead的next，依次遍历cur看cur->data是否为查找的数据x，如果是，则返回cur，否则继续（cur=cur->next），若找不到则返回NULL。

  • List.h 文件：
//链表查找LTNode* ListFind(LTNode* phead, LTDataType x);
  • List.c 文件：
//链表查找LTNode* ListFind(LTNode* phead, LTDataType x){assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur; //找到就返回cur}cur = cur->next;}return NULL; //找不到就返回空}

四、总代码

List.h 文件

#pragma once#include#include#include//创建双向链表结构typedef int LTDataType;   //方便后续更改数据类型，本文以int整型为主typedef struct ListNode{LTDataType data; //存储数据struct ListNode* next; //指向下一个struct ListNode* prev; //指向上一个}LTNode; //方便后续使用，不需要重复些struct//初始化链表（二级指针版本）/*void ListInit(LTNode** pphead);*///初始化链表（一级指针版本）LTNode* ListInit();//打印链表void ListPrint(LTNode* phead);//链表查找LTNode* ListFind(LTNode* phead, LTDataType x);//销毁链表void ListDestory(LTNode* phead);//尾插void ListPushBack(LTNode* phead, LTDataType x);//尾删void ListPopBack(LTNode* phead);//头插void ListPushFront(LTNode* phead, LTDataType x);//头删void ListPopFront(LTNode* phead);//在pos前插入数据void ListInsert(LTNode* pos, LTDataType x);//删除pos处数据void ListErase(LTNode* pos);

List.c 文件

#define _CRT_SECURE_NO_WARNINGS 1#include"List.h"//创建新节点LTNode* BuyLTNode(LTDataType x){LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode; //返回新创建的节点}//初始化链表（二级指针版）/*void ListInit(LTNode** pphead){//传二级指针，那么当然要断言assert(pphead);*pphead = BuyLTNode(0);//因为是带哨兵位的头节点，所以一开始就要给一个节点//为了循环，要让哨兵位的next和prev均指向自己(*pphead)->next = *pphead; //注意优先级，*pphead要加括号(*pphead)->prev = *pphead;}*///初始化链表（一级指针版）LTNode* ListInit(){LTNode* phead = BuyLTNode(0);phead->next = phead;phead->prev = phead;return phead;}//打印链表void ListPrint(LTNode* phead){assert(phead);//断言LTNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");}//链表查找LTNode* ListFind(LTNode* phead, LTDataType x){assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur; //找到就返回cur}cur = cur->next;}return NULL; //找不到就返回空}//销毁链表void ListDestory(LTNode* phead){assert(phead);LTNode* cur = phead->next;//销毁从第一个节点到尾部的数据while (cur != phead){LTNode* next = cur->next;//ListErase(cur);free(cur);cur = next;}//置空哨兵位节点pheadfree(phead);phead = NULL;}//尾插void ListPushBack(LTNode* phead, LTDataType x){assert(phead); //断言，防止头节点为空/*法一：LTNode* tail = phead->prev; //找到尾节点，便于后续插入数据LTNode* newnode = BuyLTNode(x);//创建新节点//将此新插入的尾节点与上一个节点链接起来tail->next = newnode;newnode->prev = tail;//将尾节点与哨兵位phead链接起来构成循环newnode->next = phead;phead->prev = newnode;*///法二：ListInsert(phead, x);}//尾删void ListPopBack(LTNode* phead){assert(phead);//本身就有哨兵位，不能为空，要断言assert(phead->next != phead); //防止链表为空，导致删除哨兵位节点/*法一：LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;//释放尾节点free(tail);tail = NULL;//将链表循环起来tailPrev->next = phead;phead->prev = tailPrev;*///法二：ListErase(phead->prev);}//头插void ListPushFront(LTNode* phead, LTDataType x){assert(phead);ListInsert(phead->next, x);}//头删void ListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead); //防止删除哨兵位节点ListErase(phead->next);}//在pos前插入数据void ListInsert(LTNode* pos, LTDataType x){assert(pos);//创建插入数据的新节点LTNode* newnode = BuyLTNode(x);//链接左侧pos->prev->next = newnode;newnode->prev = pos->prev;//链接右侧newnode->next = pos;pos->prev = newnode;}//删除pos处数据void ListErase(LTNode* pos){assert(pos);//定义两个指针保存pos两边的节点LTNode* prev = pos->prev;LTNode* next = pos->next;//将prev和next链接起来prev->next = next;next->prev = prev;//free释放free(pos);pos = NULL;}

Test.c 文件

#define _CRT_SECURE_NO_WARNINGS 1#include"List.h"void TestList1(){//初始化（法一）/*LTNode* pList = NULL;ListInit(&pList);*///初始化（法二）LTNode* pList = ListInit();for (int i = 1; i <= 7; i++){ListPushBack(pList, i); //尾插7个数据}ListPrint(pList);//打印尾插的7个}void TestList2(){LTNode* pList = ListInit();for (int i = 1; i <= 7; i++){ListPushBack(pList, i); //尾插7个数据}ListPrint(pList);//打印尾插的7个//尾删两次ListPopBack(pList);ListPopBack(pList);ListPrint(pList);//再次打印}void TestList3(){LTNode* pList = ListInit();for (int i = 1; i <= 7; i++){ListPushBack(pList, i); //尾插7个数据}ListPrint(pList);//打印尾插的7个//寻找数字LTNode* pos = ListFind(pList, 3);if (pos){ListInsert(pos, 30); //找到数字3就插入}ListPrint(pList);//打印}void TestList4(){LTNode* pList = ListInit();for (int i = 1; i <= 7; i++){ListPushBack(pList, i); //尾插7个数字}ListPrint(pList);//打印for (int i = -2; i <= 0; i++){ListPushFront(pList, i); //头插3个数字}ListPrint(pList);//打印}void TestList5(){LTNode* pList = ListInit();for (int i = 1; i <= 7; i++){ListPushBack(pList, i); //尾插7个数据}ListPrint(pList);//打印尾插的7个//寻找数字LTNode* pos = ListFind(pList, 3);if (pos){ListErase(pos); //删除pos处数据pos = NULL; //形参的改变不会影响实参，最好在这置空pos}ListPrint(pList);//打印}void TestList6(){LTNode* pList = ListInit();for (int i = 1; i <= 7; i++){ListPushBack(pList, i); //尾插7个数字}ListPrint(pList);//打印//头插3个数字ListPushFront(pList, 0);ListPushFront(pList, -1);ListPushFront(pList, -2);ListPrint(pList);//打印//尾删3个数字ListPopBack(pList);ListPopBack(pList);ListPopBack(pList);ListPrint(pList);//打印//头删3个数字ListPopFront(pList);ListPopFront(pList);ListPopFront(pList);ListPrint(pList);//打印//销毁链表ListDestory(pList);pList = NULL;}void TestList7(){LTNode* pList = ListInit();for (int i = 1; i <= 7; i++){ListPushBack(pList, i); //尾插7个数字}ListPrint(pList);//打印//销毁链表ListDestory(pList);pList = NULL;}int main(){//TestList1();//TestList2();//TestList3();//TestList4();//TestList5();//TestList6();TestList7();return 0;}

五、拓展：对比顺序表和链表

不同点 顺序表 链表
存储空间上 物理上一定连续 逻辑上连续，但物理上不一定连续
随机访问 支持O(1) 不支持O(N)
任意位置插入或者删除元素 可能需要搬移元素，效率低O(N) 只需修改指针指向
插入 动态顺序表，空间不够时需要扩容 没有容量的概念
应用场景 元素高效存储+频繁访问 任意位置插入和删除数据
缓存利用率 高 低
  • 优缺点对比：
顺序表 链表
优点

1、物理空间是连续的，方便用下标随机访问。

2、CPU高速缓存命中率会更高。（补充）

1、按需申请释放空间。

2、任意位置可以O(1)插入删除数据。
缺点

1、正因为物理空间连续，空间不够需要扩容，扩容本身又一定消耗，其次扩容机制还存在一定的空间浪费。

2、头部或者中部插入删除，挪动数据，效率低，O(N)。

1、不支持下标的随机访问。

2、有些算法不适合在它上面进行，如：二分查找、排序等。
网络标签：

相关问题