【双向链表】带头双向循环（1）-阿里云开发者社区

今天实现一个带头双向循环链表。

🙂判断为NULL的情况
🙂判断二级指针&一级指针（想要改变实参不仅可以用指针，而且可以用return
🙂判断先实现哪一步
❌野指针的出现
❌修改指针用二级指针
❌修改结构体用一级指针
❌内存泄露的问题，需要释放
❌释放完空间，指针需要置NULL
🆗无头单项不循环链表适用OJ链表比较多
🆗带头双向不循环适用生活工作场景比较多
🆗C++是兼容C
❌【单链表】一般都不带头//需要二级指针处理//除了！链表分割
❌【双向链表】需要带头
🙂【单链表】Singly linked list（SLT）
🙂【双链表】Double linked list（LT）
🙂【顺序表】Sequention table list（SL)

链表的分类

前面我们学习了单链表。但是链表并不仅限只有【单链表】。【链表】是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

单向或者双向

带头或者不带头

循环或者非循环

这些特征组合起来可以构成：8种形态的链表。

虽然有这么多的链表的结构，但是我们实际中最常用的还是有两种结构。

【无头单项非循环链表】&【带头双向循环链表】

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。实际生活中使用很多。

在前面我们已经学过无头单项不循环链表，这里我们来实现带头双向循环链表

Test.c主函数

int main()
{
  LTNode* phead = LTInit();//初始化
  test1(phead);//头插
  test2(phead);//头删
  test3(phead);//尾插
  test4(phead);//尾删
    test5(phead);//查询某个数字
  test6(phead);//插入pos位置的前一个/后一个元素
  test7(phead);//删除pos位置的元素
  LTDestroy(phead);//空间释放/防止内存泄露
  return 0;
}

test1头插

#include"DList.h"
void test1(LTNode* phead)//头插
{
  LTPushFront(phead, 7);
  LTPushFront(phead, 3);
  LTPushFront(phead, 4);
  LTPushFront(phead, 7);
  LTPushFront(phead, 8);
  LTPushFront(phead, 9);
  LTPrint(phead);
}

test2头删

void test2(LTNode* phead)//头删
{
  LTPopFront(phead);
  LTPopFront(phead);
  LTPopFront(phead);
  LTPrint(phead);
}

test3尾插

void test3(LTNode* phead)//尾插
{
  LTPushBack(phead, 77);
  LTPushBack(phead, 99);
  LTPrint(phead);
}

test4尾删

void test4(LTNode* phead)//尾删
{
  LTPopBack(phead);
  LTPopBack(phead);
  LTPopBack(phead);
  LTPopBack(phead);
  LTPrint(phead);
}

test5查询

void test5(LTNode* phead)//查询
{
  LTNode* node = LTFind(phead, 4);
  if (node == NULL)
  {
    printf("没找到");
  }
  else
  {
    printf("%d", node->val);
  }
}

test6插入pos位置后一个

void test6(LTNode* phead)//插入pos位置的前一个/后一个元素
{
  LTNode* pos = LTFind(phead, 4);
  LTInsertAfter(phead, pos, 77);
  LTInsertAfter(phead, pos, 66);
  LTInsertAfter(phead, pos, 99);
  LTPrint(phead);
}

test7删除pos

//删除pos位置的元素
void test7(LTNode* phead)
{
  LTNode* pos = LTFind(phead, 4);
    if(pos)//查询成功才进入
    {
    LTErase(phead, pos);
      pos=NULL;
    }
  LTPrint(phead);
}

Test.c总代码

#include"DList.h"
void test1(LTNode* phead)//头插
{
  LTPushFront(phead, 7);
  LTPushFront(phead, 3);
  LTPushFront(phead, 4);
  LTPushFront(phead, 7);
  LTPushFront(phead, 8);
  LTPushFront(phead, 9);
  LTPrint(phead);
}
void test2(LTNode* phead)//头删
{
  LTPopFront(phead);
  LTPopFront(phead);
  LTPopFront(phead);
  LTPrint(phead);
}
void test3(LTNode* phead)//尾插
{
  LTPushBack(phead, 77);
  LTPushBack(phead, 99);
  LTPrint(phead);
}
void test4(LTNode* phead)//尾删
{
  LTPopBack(phead);
  LTPopBack(phead);
  LTPopBack(phead);
  LTPopBack(phead);
  LTPrint(phead);
}
void test5(LTNode* phead)//查询
{
  LTNode* node = LTFind(phead, 4);
  if (node == NULL)
  {
    printf("没找到");
  }
  else
  {
    printf("%d", node->val);
  }
}
void test6(LTNode* phead)//插入pos位置的前一个/后一个元素
{
  LTNode* pos = LTFind(phead, 4);
  LTInsertAfter(phead, pos, 77);
  LTInsertAfter(phead, pos, 66);
  LTInsertAfter(phead, pos, 99);
  LTPrint(phead);
}
//删除pos位置的元素
void test7(LTNode* phead)
{
  LTNode* pos = LTFind(phead, 4);
    if(pos)//查询成功才进入
    {
    LTErase(phead, pos);
      pos=NULL;
    }
  LTPrint(phead);
}
int main()
{
  LTNode* phead = LTInit();//已经被初始化了
  test1(phead);//头插
  test2(phead);//头删
  test3(phead);//尾插
  test4(phead);//尾删
    test5(phead);//查询某个数字
  test6(phead);//插入pos位置的前一个/后一个元素
  test7(phead);//删除pos位置的元素
  LTDestroy(phead);//空间释放/防止内存泄露
    phead=NULL;
  return 0;
}

DList.h头文件&函数声明

头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
assert(//)//括号里是可以出现的情况为真 若括号里的表达式为假那就❌

函数声明

声明节点

typedef int LTDateType;
//声明节点
typedef struct DListNode
{
  LTDateType val;
  struct DListNode* prev;
  struct DListNode* next;
}LTNode;

初始化（可以用指针修改实参/也可以用返回值改变实参）

LTNode* LTInit();

头插

void LTPushFront(LTNode*phead, LTDateType x);

头删

void LTPopFront(LTNode* phead);

尾插

void LTPushBack(LTNode* phead,LTDateType x);

尾删

void LTPopBack(LTNode* phead);

打印

void LTPrint(LTNode* phead);

查询

LTNode* LTFind(LTNode* phead);

在pos的后面插入一个元素

void LTInsertAfter(LTNode* phead, LTNode* pos, LTDateType x);

删除pos位置的元素

void LTErase(LTNode* phead, LTNode* pos);

销毁释放

void LTDestroy(LTNode* phead);

DList.h总代码

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDateType;
//定义节点
typedef struct DListNode
{
  LTDateType val;
  struct DListNode* prev;
  struct DListNode* next;
}LTNode;
//初始化
LTNode* LTInit();//不用二级指针/用返回值改变实参
void LTPushFront(LTNode*phead, LTDateType x);//头插
void LTPopFront(LTNode* phead);//头删
void LTPushBack(LTNode* phead,LTDateType x);//尾插
void LTPopBack(LTNode* phead);//尾删
void LTPrint(LTNode* phead);//打印
LTNode* LTFind(LTNode* phead);//查询
void LTInsertAfter(LTNode* phead, LTNode* pos, LTDateType x);//在pos的后面插入一个元素
void LTErase(LTNode* phead, LTNode* pos);//删除pos位置的元素
void LTDestroy(LTNode* phead);//销毁释放

DList.c函数实现

//初始化
LTNode* LTInit()
{
  LTNode* phead = Createnode(-1);
  phead->prev = phead;
  phead->next = phead;
  return phead;
}

Createnode创建节点

#include"DList.h"
//创造节点
LTNode* Createnode(LTDateType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("malloc");
    exit(-1);//程序停止
  }
  newnode->val = x;
  newnode->prev = NULL;
  newnode->next = NULL;
  return newnode;
}

LTInit初始化

通过形参改变实参可以使用【指正】
通过形参改变实参可以使用【return】

//初始化
LTNode* LTInit()
{
  LTNode* phead = Createnode(-1);
  phead->prev = phead;
  phead->next = phead;
  return phead;
}

LTPrint打印

//打印
void LTPrint(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead;
  printf("<=>");
    printf("%d<=>", cur->val);
  cur = cur->next;
  while (cur != phead)
  {
    printf("%d<=>", cur->val);
    cur = cur->next;
  }
  printf("\n");
}

LTPushFront头插

//头插
void LTPushFront(LTNode* phead,LTDateType x)
{
  assert(phead);
  LTNode* newnode = Createnode(x);
  newnode->next = phead->next;
  phead->next->prev = newnode;
  phead->next = newnode;
  newnode->prev = phead;
}

LTPopFron头删

一定不能把头节点哨兵位给删除了会出现野指针的问题❌

//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  LTNode* next = cur->next;
  assert(cur != phead); //考虑如果链表为NULL
  phead->next = next;
  next->prev = phead;
  free(cur);
  cur = NULL;
}

LTPushBack尾插

//尾插
void LTPushBack(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* newnode = Createnode(x);
  newnode->prev = phead->prev;
  phead->prev->next = newnode;
  newnode->next = phead;
  phead->prev = newnode;
}

LTPopBack尾删

一定不能把头节点哨兵位给删除了会出现野指针的问题❌

//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->prev;
  LTNode* next = cur->prev;
  assert(cur != phead);
  phead->prev = next;
  next->next = phead;
  free(cur);
  cur = NULL;
}

LTFind查询

查询到某个数据的位置意味着可以修改这个位置前后的数据

//查询
//查询某个数，存在返回节点地址，不存在返回NULL
LTNode* LTFind(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->val == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

LTInsertAfter在pos后面插入

//在pos的后面插入一个元素
void LTInsertAfter(LTNode* phead, LTNode*pos, LTDateType x)
{
  assert(phead);
  LTNode* newnode = Createnode(x);
  newnode->next = pos->next;
  pos->next->prev = newnode;
  pos->next = newnode;
  newno

LTErase删除pos数据

//删除pos位置的元素//
void LTErase(LTNode* phead, LTNode* pos)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* cur = pos->prev;
  LTNode* next = pos->next;
  cur->next = next;
  next->prev = cur;
  free(pos);
  pos = NULL;
}

LTDestroy销毁释放

//销毁
void LTDestroy(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* tmp = cur->next;
    free(cur);
    cur = tmp;
  }
}

DList.c总代码

#include"DList.h"
//创造节点
LTNode* Createnode(LTDateType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("malloc");
    exit(-1);//程序停止
  }
  newnode->val = x;
  newnode->prev = NULL;
  newnode->next = NULL;
  return newnode;
}
//初始化
LTNode* LTInit()
{
  LTNode* phead = Createnode(-1);
  phead->prev = phead;
  phead->next = phead;
  return phead;
}
//打印
void LTPrint(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead;
  printf("<=>");
    printf("%d<=>", cur->val);
  cur = cur->next;
  while (cur != phead)
  {
    printf("%d<=>", cur->val);
    cur = cur->next;
  }
  printf("\n");
}
//头插
void LTPushFront(LTNode* phead,LTDateType x)
{
  assert(phead);
  LTNode* newnode = Createnode(x);
  newnode->next = phead->next;
  phead->next->prev = newnode;
  phead->next = newnode;
  newnode->prev = phead;
}
//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->next;
  LTNode* next = cur->next;
  assert(cur != phead); //考虑如果链表为NULL
  phead->next = next;
  next->prev = phead;
  free(cur);
  cur = NULL;
}
//尾插
void LTPushBack(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* newnode = Createnode(x);
  newnode->prev = phead->prev;
  phead->prev->next = newnode;
  newnode->next = phead;
  phead->prev = newnode;
}
//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  LTNode* cur = phead->prev;
  LTNode* next = cur->prev;
  assert(cur != phead);
  phead->prev = next;
  next->next = phead;
  free(cur);
  cur = NULL;
}
//查询
//查询某个数，存在返回节点地址，不存在返回NULL
LTNode* LTFind(LTNode* phead, LTDateType x)
{
  assert(phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    if (cur->val == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//在pos的后面插入一个元素
void LTInsertAfter(LTNode* phead, LTNode*pos, LTDateType x)
{
  assert(phead);
  LTNode* newnode = Createnode(x);
  newnode->next = pos->next;
  pos->next->prev = newnode;
  pos->next = newnode;
  newnode->prev = pos;
}
//删除pos位置的元素//
void LTErase(LTNode* phead, LTNode* pos)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* cur = pos->prev;
  LTNode* next = pos->next;
  cur->next = next;
  next->prev = cur;
  free(pos);
  pos = NULL;
}
//销毁
void LTDestroy(LTNode* phead)
{
  assert(phead);
  assert(phead->next != phead);
  LTNode* cur = phead->next;
  while (cur != phead)
  {
    LTNode* tmp = cur->next;
    free(cur);
    cur = tmp;
  }
    cur=NULL;
}
//形式参数这里就可以置NULL 
//实际参数到主函数里面置NULL

✔✔✔✔✔最后感谢大家的阅读，若有错误和不足，欢迎指正!乖乖敲代码哦！

代码---------→【唐棣棣 (TSQXG) - Gitee.com】

联系---------→【邮箱：2784139418@qq.com】

【双向链表】带头双向循环（1）