DS：带头双向循环链表的实现-阿里云开发者社区

创作不易，友友们给个三连吧！！！

博主的上篇文章介绍了链表，以及单链表的实现。

单链表的实现（超详细！！）

其实单链表的全称叫做不带头单向不循环链表，本文会重点介绍链表的分类以及双链表的实现！

一、链表的分类

链表的结构⾮常多样，组合起来就有8种（2 x 2 x 2）链表结构：

1.1 单向或者双向

双向链表，即上一个结点保存着下一个结点的地址，且下一个结点保存着上一个结点的地址，即我们可以从头结点开始遍历，也可以从尾结点开始遍历

1.2 带头或者不带头

单链表中我们提到的“头结点”的“头”和“带头”链表的头是两个概念！单链表中提到的“头结点”指的是第一个有效的结点，“带头”链表里的“头”指的是无效的结点（即不保存任何有效的数据！）

1.3 循环或者不循环

不循环的链表最后一个结点的next指针指向NULL，而循环的链表，最后一个结点的next指针指向第一个结点！！

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表（不带头单向不循环链表）和双向链表（带头双向循环链表）

1. 无头单向非循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。

2. 带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实现反⽽简单了，后⾯我们代码实现了就知道了。

二、带头双向循环链表的结构

带头链表⾥的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨的”

“哨兵位”存在的意义：遍历循环链表避免死循环。

三、双向链表结点结构体的创建

与单链表结点结构体不同的是，双向链表的结点结构体多了一个前驱结点！！

typedef int LTDataType;//对类型进行重命名，后面可以通过修改存储其他数据类型
typedef struct ListNode
{
  LTDataType data;//保存的数据
  struct ListNode* prev;//指针保存前一个结点的地址
  struct ListNode* next;//指针保存后一个结点的地址
}LTNode;

四、带头双向循环链表的实现

4.1 新结点的申请

涉及到需要插入数据，都需要申请新节点，所以优先封装一个申请新结点的函数！利用返回值返回该结点

LTNode* LTBuyNode(LTDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(1);//申请失败需要强制退出程序
  }
  //申请成功，则新节点的前驱结点和后驱结点都指向自己
  newnode->data = x;
  newnode->prev = newnode->next = newnode;
    return newnode;
}

4.2 初始化（哨兵位结点）

对于双向链表来说，需要优先创建一个哨兵结点，和其他结点不同的是，该哨兵结点可以不存储数据，这里我们默认给他一个-1。并利用返回值返回该结点。

LTNode* LTInit()
{
  LTNode* phead = LTBuyNode(-1);//哨兵结点可以不存储数据，我们默认给个-1
  return phead;//返回哨兵结点
}

4.3 尾插

如图，因为这个一个循环链表，相当于我们要把新节点插在最后一个结点和哨兵结点之间，并且最后一一个结点可以用哨兵结点的前驱结点（phead->prev）就可以找到，然后建立phead phead->prev newnode的联系！

void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);//申请新节点
  //建立phead phead->prev newnode的联系
  newnode->prev = phead->prev;
  newnode->next = phead;
  phead->prev->next = newnode;//尾结点的后继指针指向新节点
  phead->prev = newnode;//哨兵结点的前驱指针指向新结点
}

单链表中我们的参数选择二级指针，为什么这里选择一级指针？？？

对于单链表来收，单链表的头节点是会改变的，所以我们需要用二级指针，但是双链表的头节点相当于哨兵位，哨兵位是不需要被改变的，他是固定死的，所以我们选择了一级指针。（单链表改了完全头节点，但是双链表只会改变头结点的成员——prev和next）

注：phead->prev->next = newnode和phead->prev = newnode不能替换顺序，因为尾结点是通过头节点找到的，所以要优先让他与newnode建立联系，双链表虽然不需要像单链表一样找最后一个结点需要遍历链表，但是要十分注意修改指针指向的先后顺序！！

4.4 头插

如图可知，相当于将新节点插入在头节点和头节点下一个结点之间，头节点下一个结点可以通过phead->next找到，然后建立phead、phead->next、newnode的联系！！

void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);//申请新节点
  //建立phead phead->next newnode的联系
  newnode->prev = phead;
  newnode->next = phead->next;
  phead->next->prev = newnode;//头节点的下一个结点的前驱指针指向新结点
  phead->next = newnode;//头节点的后继指针指向新节点
}

4.5 打印

因为是循环链表，所以为了避免死循环打印，我们要设置一个指针接收头节点的下一个结点，然后往后遍历，直到遍历到头节点结束。

void LTPrint(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("\n");
}

4.6 尾删

由图可知，要建立phead和phead->prev->prev的联系，同时由于还要释放最后一个结点（phead->prev），所以在建立联系之前要现保存这个被释放的空间，等建立联系完再释放！！同时要注意一条规则，就是当链表中只有哨兵结点的时候，我们称该链表为空链表！因此如果链表只存在哨兵结点，那么删除是没有意义的，所以必须断言！

void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);//链表只有哨兵结点时删除没意义
  LTNode* del = phead->prev;//del记录最后一个结点
  del->prev->next = phead;//倒数第二个结点的后驱指针指向头结点
  phead->prev = del->prev;//头节点的前驱结点指向倒数第二个结点
  free(del);//释放最后一个结点
  del = NULL;
}

4.7 头删

由图可知，要建立phead和phead->next->next的联系，同时由于还要释放第二个结点（phead->next），所以在建立联系之前要现保存这个被释放的空间，等建立联系完再释放！！

void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);//链表只有哨兵结点时删除没意义
  LTNode* del = phead->next;//del记录第二个结点
  del->next->prev = phead;//第二个结点的前驱指针指向头结点
  phead->next = del->next;//头节点的后驱指针指向第三个结点
  free(del);//释放第二个结点
  del = NULL;
}

4.8 查找

涉及到对指定位置进行操作的时候，需要设置一个查找函数，根据我们需要的数据返回他的结点地址

LTNode* LTFind(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)//遍历链表
  {
    if (pcur->data == x)
      return pcur;//找到的话返回该结点
    pcur = pcur->next;
  }
  //循环结束还是没找到
  return NULL;
}

4.9 指定位置之后插入

由图可知，指定位置插入相当于将新结点插入到指定位置（pos）和指定位置下一个结点的位置（pos->next）,然后建立pos pos->next newnode的联系，而且这里用不到头节点！

void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);//保证pos为有效结点
  LTNode* newnode = LTBuyNode(x);//申请新节点
  //建立pos pos->next newnode的联系
  newnode->prev = pos;
  newnode->next = pos->next;
  pos->next->prev = newnode;//pos的后一个结点的前驱结点指向新节点
  pos->next = newnode;//pos结点的后继结点指向新结点
}

4.10 指定位置删除

右图可知建立指定位置的前一个结点（pos->prev）和指定位置的后一个结点（pos->next）的联系，并释放pos。

void LTErase(LTNode* pos)
{
  assert(pos);//保证pos为有效结点
  pos->prev->next = pos->next;//pos的前一个结点的后继指针指向pos后一个结点
  pos->next->prev = pos->prev;//pos的后一个结点的前驱指针指向pos的前一个结点
  free(pos);//释放pos
  pos = NULL;
}

4.11 销毁链表

void LTDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  LTNode*next = NULL;
  while (pcur != phead)
  {
    next = pcur->next;
    free(pcur);
    pcur = next;
  }
  //除了头结点都释放完毕
  free(phead);
  //phead = NULL;//没有用！
}

为什么phead=NULL没有用？？

因为我们使用的是一级指针，这里相当于是值传递，值传递形参改变不了实参，所以将phead置空是没有意义的，其实如果这里使用二级指针，然后传地址就可以了，但是为了保持接口一致性，我们还是依照这种方法，但是phead=NULL必须在主函数中去使用，所以我们在调用销毁链表的函数的时候，别忘记了phead=NULL！！

五、带头双向循环链表实现的全部代码

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;//对类型进行重命名，后面可以通过修改存储其他数据类型
typedef struct ListNode
{
  LTDataType data;//保存的数据
  struct ListNode* prev;//指针保存前一个结点的地址
  struct ListNode* next;//指针保存后一个结点的地址
}LTNode;
LTNode* LTBuyNode(LTDataType x);//申请新的链表结点
LTNode* LTInit();//初始化（申请一个哨兵结点）
void LTPushBack(LTNode* phead, LTDataType x);//尾插 （最后一个结点后插入或哨兵结点前插入）
void LTPushFront(LTNode* phead, LTDataType x);//头插 （哨兵结点后的插入）
void LTPrint(LTNode* phead);//打印
void LTPopBack(LTNode* phead);//尾删
void LTPopFront(LTNode* phead);//头删
LTNode* LTFind(LTNode* phead, LTDataType x);//查找
void LTInsert(LTNode* pos, LTDataType x);//指定位置之后插入
void LTErase(LTNode* pos);//指定位置删除
void LTDestroy(LTNode* phead);//销毁链表

List.c

#include"List.h"
LTNode* LTBuyNode(LTDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(1);//申请失败需要强制退出程序
  }
  //申请成功，则新节点的前驱结点和后驱结点都指向自己
  newnode->data = x;
  newnode->prev = newnode->next = newnode;
  return newnode;
}
LTNode* LTInit()
{
  LTNode* phead = LTBuyNode(-1);//哨兵结点可以不存储数据，我们默认给个-1
  return phead;//返回哨兵结点
}
void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);//申请新节点
  //建立phead phead->prev newnode的联系
  newnode->prev = phead->prev;
  newnode->next = phead;
  phead->prev->next = newnode;//尾结点的后继结点指向新节点
  phead->prev = newnode;//哨兵结点的前驱指针指向新结点
}
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* newnode = LTBuyNode(x);//申请新节点
  //建立phead phead->next newnode的联系
  newnode->prev = phead;
  newnode->next = phead->next;
  phead->next->prev = newnode;//头节点的下一个结点的前驱指针指向新结点
  phead->next = newnode;//头节点的后继指针指向新节点
}
void LTPrint(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("\n");
}
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);//链表只有哨兵结点时删除没意义
  LTNode* del = phead->prev;//del记录最后一个结点
  del->prev->next = phead;//倒数第二个结点的后驱指针指向头结点
  phead->prev = del->prev;//头节点的前驱结点指向倒数第二个结点
  free(del);//释放最后一个结点
  del = NULL;
}
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);//链表只有哨兵结点时删除没意义
  LTNode* del = phead->next;//del记录第二个结点
  del->next->prev = phead;//第二个结点的前驱指针指向头结点
  phead->next = del->next;//头节点的后驱指针指向第三个结点
  free(del);//释放第二个结点
  del = NULL;
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)//遍历链表
  {
    if (pcur->data == x)
      return pcur;//找到的话返回该结点
    pcur = pcur->next;
  }
  //循环结束还是没找到
  return NULL;
}
void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);//保证pos为有效结点
  LTNode* newnode = LTBuyNode(x);//申请新节点
  //建立pos pos->next newnode的联系
  newnode->prev = pos;
  newnode->next = pos->next;
  pos->next->prev = newnode;//pos的后一个结点的前驱结点指向新节点
  pos->next = newnode;//pos结点的后继结点指向新结点
}
void LTErase(LTNode* pos)
{
  assert(pos);//保证pos为有效结点
  pos->prev->next = pos->next;//pos的前一个结点的后继指针指向pos后一个结点
  pos->next->prev = pos->prev;//pos的后一个结点的前驱指针指向pos的前一个结点
  free(pos);//释放pos
  pos = NULL;
}
void LTDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  LTNode*next = NULL;
  while (pcur != phead)
  {
    next = pcur->next;
    free(pcur);
    pcur = next;
  }
  //除了头结点都释放完毕
  free(phead);
  //phead = NULL;//没有用！
}

六、顺序表和链表的优缺点分析

1、存储空间

顺序表物理上连续

链表逻辑上连续，但是物理上不连续

2、随机访问

顺序表可以通过下标去访问

链表不可以直接通过下标去访问

3、任意位置插入或者删除元素

顺序表需要挪移元素，效率低

链表只需修改指针指向

4、插入

动态顺序表空间不够时需要扩容

链表没有容量的概念

5、应用场景

顺序表应用于元素高效存储+频繁访问的场景

链表应用于任意位置插入和删除频繁的场景

总之：没有绝对的优劣，都要各自适合的应用场景！！

DS：带头双向循环链表的实现

一、链表的分类

1.1 单向或者双向

1.2 带头或者不带头

1.3 循环或者不循环

二、带头双向循环链表的结构

三、双向链表结点结构体的创建

四、带头双向循环链表的实现

4.1 新结点的申请

4.2 初始化（哨兵位结点）

4.3 尾插

4.4 头插

4.5 打印

4.6 尾删

4.7 头删

4.8 查找

4.9 指定位置之后插入

4.10 指定位置删除

4.11 销毁链表

五、带头双向循环链表实现的全部代码

六、顺序表和链表的优缺点分析

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

DS：带头双向循环链表的实现

一、链表的分类

1.1 单向或者双向

1.2 带头或者不带头

1.3 循环或者不循环

二、带头双向循环链表的结构

三、双向链表结点结构体的创建

四、带头双向循环链表的实现

4.1 新结点的申请

4.2 初始化（哨兵位结点）

4.3 尾插

4.4 头插

4.5 打印

4.6 尾删

4.7 头删

4.8 查找

4.9 指定位置之后插入

4.10 指定位置删除

4.11 销毁链表

五、带头双向循环链表实现的全部代码

六、顺序表和链表的优缺点分析

热门文章

最新文章

相关电子书