[数据结构] -- 双向循环链表

简介: [数据结构] -- 双向循环链表

双向循环链表


结构

包含数据域,指针域(前驱节点prev和后继节点next)

介绍

结构最复杂,一般用在单独存储数据。

实际中使用的链表数据结构,都是带头双向循环链表。

另外这个结构虽然结构复杂,

但是使用代码实现以后会发现结构会带来很多优势,但实现简单

图示


双向链表的实现


在List.h中

定义双向链表的结构

typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;
  struct ListNode* prev;
  struct ListNode* next;
}LTNode;

实现双向链表的接口/方法

//初始化
LTNode* LTInit();
//销毁链表
void LTDestroy(LTNode* phead);
//打印链表
void LTPrint(LTNode* phead);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos指定节点
void LTErase(LTNode* pos);
//查找链表的指定元素
LTNode* LTFind(LTNode* phead, LTDataType x);

在List.c中

初始化

//初始化
LTNode* LTInit()
{
  LTNode* phead = LTBuyNode(-1);
  return phead;
}

销毁链表

//销毁
void LTDestroy(LTNode* phead)
{
  assert(phead);
 
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    LTNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
 
  //最后释放头节点的内存并置空
  free(phead);
  phead = NULL;
}

打印链表

//打印双向链表
void LTPrint(LTNode* phead)
{
  assert(phead);
 
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    printf("%d->", pcur->data);
    pcur = pcur->next;
  }
  printf("\n");
}

判断链表是否为空

bool LTEmpty(LTNode* phead)
{
  if (phead->next == phead)
  {
    return true;
  }
 
  else { return false; }
}

尾插

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

后四行的方向和赋值问题

有新开节点newnode

测试

头插

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead);
 
  LTNode* newnode = LTBuyNode(x);
  LTNode* pcur = phead->next;
 
  newnode->next = pcur;
  newnode->prev = phead;
 
  phead->next = newnode;
  pcur->prev = newnode;
}
测试

尾删

//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
 
  LTNode* p1 = phead->prev;
  LTNode* pcur = p1->prev;
 
  pcur->next = phead;
  phead->prev = pcur;
 
  free(p1);
  p1 = NULL;
}
测试

头删

//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
 
  LTNode* pcur = phead->next->next;
  LTNode* p1 = phead->next;
 
  phead->next = pcur;
  pcur->prev = phead;
 
  free(p1);
  p1 = NULL;
}
测试

在pos位置之后插入数据

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
 
   LTNode* newnode = LTBuyNode(x);
 
   newnode->next = pos->next;
   newnode->prev = pos;
 
   //如果pos是最后一个节点
   if (pos->next == NULL)
   {
     newnode->next = NULL;
   }
   else
   {
     pos->next->prev = newnode;
   }
 
   pos->next = newnode;
}
测试

删除pos指定节点

//删除pos节点
void LTErase(LTNode* pos)
{
  assert(pos);
 
  LTNode* p1 = pos->prev;
  LTNode* pcur = pos->next;
 
  p1->next = pcur;
  pcur->prev = p1;
 
  free(pos);
  pos = NULL;
}
测试

查找链表的指定元素

//查找元素
LTNode* LTFind(LTNode* phead, LTDataType x)
{
  assert(phead);
 
  LTNode* pcur = phead->next;
  while (pcur != phead)    //注意循环条件!
  {
    if (pcur->data == x)
    {
      return pcur;
    }
 
    else
    {
      pcur = pcur->next;
    }
  }
  return NULL;
}
目录
相关文章
|
6天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
28 5
|
29天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
55 4
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
2月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
26 7
|
2月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
26 3
|
2月前
|
算法 Java
数据结构与算法学习五:双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现,并通过实例演示了双向链表的优势和应用。
18 0
数据结构与算法学习五:双链表的增、删、改、查
|
29天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
42 0
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现
|
2月前
|
存储 Java
【数据结构】链表
【数据结构】链表
18 1