【数据结构】从头到尾全解析双向链表

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: 【数据结构】从头到尾全解析双向链表

在之前我们已经讲过< 单链表 >了,单链表查找上一个结点的时间复杂度为O(n),尾插时也要遍历一次链表也是O(n),因为我们每次都要从头开始遍历找,为了克服这单向性的缺点,我们就有了双向链表.

如果要提高链表的查找,尾插等效率,那双向链表(双链表)无疑是首选。


双向链表的概念及结构



双向链表是一种常用的数据结构,它允许我们在O(1)时间内对链表的头尾进行元素的添加和删除操作,同时也支持双向遍历。


双向链表是在单链表的每个结点中,再设置一个指向其前驱结点的指针域,所以在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱。


958d2da67aa34a48a3b436f6cc948884.png

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


双向链表的结构:双向链表的每个节点包含了三个基本元素,分别是元素值、指向前一个节点的指针和指向下一个节点的指针。


  • 双向链表存储结构


struct SListNode
{
  int data;  //节点存储数据
  struct SListNode* next; //指向前驱节点
  struct SListNode* prev; //指向后驱节点
};


  • 注意:

双向链表头指针是一个虚拟头节点,不存储任何有效数据,他的前驱节点与后驱节点都是指向自己的,头指针节点相当于是一个削兵。用来站岗的。方便链接前后指针.


双向链表接口的实现



申请节点空间


  • 链表添加一个节点数据时候,每次都要写一段代码,这样做是不是太繁琐了,我们可以封

装一个函数来解决问题,每次添加一个节点时,将结点存放的数据置为需要存放的值,在将结构体存放节点的地址置为NULL, 需要增加节点时调用一下改函数即可。


//申请节点空间
LTNode* BuyList(LTDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)  //判断是否申请成功
  {
    perror("malloc fail");
  }
  else   //申请成功
  {
    newnode->data = x;  //将结点存放的数据置为需要存放的值
    newnode->next = NULL;  //节点的地址置为NULL
    newnode->prev = NULL;  //节点的地址置为NULL
    return newnode;
  }
}


双向链表的初始化


  • 其实在双向链表操作中,我们只需要一级指针接收就能修改链表的指向了,但在初始化时

候我们要修改头节点指针,需要二级指针来接收修改头节点,为了后面统一用一级指针,所以我们在初始化时候不传参,直接申请一个节点,然后返回,该指点的前驱指针与后驱指针都是指向自己。节点数据不存储有效数据


LTNode* LTInit() 
{
  LTNode* phead = BuyLTNode(-11111);//节点数据不存储有效数据
  //前驱指针与后驱指针都是指向自己
  phead->next = phead;  
  phead->prev = phead;
  return phead; //返回该节点
}


双向链表打印数据


  • 双向链表是通过结构体存储的头指针下一个指针开始遍历链表的,当遍历的指针指向头指

针则遍历完毕。


void LTPrint(LTNode* phead)
{
  assert(phead); //断言:判断是否为空
  printf("guard<==>");
  LTNode* cur = phead->next; //从头指针的next开始遍历
  while (cur != phead)
  {
    printf("%d<==>", cur->data); // 打印数据
    cur = cur->next; //迭代指向下一个
  }
  printf("\n");
}


双向链表是否为空


  • 如果phead->next为自己,则链表为空,返回真,反之返回假.


bool LTEmpty(LTNode* phead)
{
  assert(phead); //断言 判断是否为空指针
  return phead->next == phead; 
}


双向链表尾插


  • 双向链表尾插步骤
  1. 创建一个新节点 ,将新节点的数据填充为要插入的数据。
  2. 使用phead->prev找到当前双向链表的尾节点tail。
  3. 将tail节点的next指针指向新的待插入节点newnode
  4. 将待插入节点newnode的prev指针指向原尾节点tail
  5. 将待插入节点newnode的next指针指向链表的头节点phead。
  6. 将链表头节点phead的prev指针指向插入的新节点newnode。


// 双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
  assert(phead); //断言:判断是否为空
  LTNode* tail = phead->prev;  //使用phead->prev找到当前双向链表的尾节点tail。
  LTNode* newnode = BuyLTNode(x); //创建一个新节点 
  tail->next = newnode;  //将tail节点的next指针指向新的待插入节点newnode
  newnode->prev = tail;  //将待插入节点newnode的prev指针指向原尾节点tail
  newnode->next = phead; //将待插入节点newnode的next指针指向链表的头节点phead。
  phead->prev = newnode; //将链表头节点phead的prev指针指向插入的新节点newnode。
}


双向链表头插


  • 双向链表头插步骤
  1. 创建一个新节点 ,将新节点的数据填充为要插入的数据。
  2. 使用phead->next找到当前双向链表的头节点,用first保存.
  3. 将链表头节点phead的next指针指向新插入的节点newnode
  4. 将待插入节点newnode的prev指针指向链表的头节点phead。
  5. 将待插入节点newnode的next指针指向原头节点first。
  6. 将原头节点first的prev指针指向插入的新节点newnode。


void LTPushFront(LTNode* phead, LTDataType x)
{
  assert(phead); //断言 判断是否为空
  LTNode* newnode = BuyLTNode(x); //创建一个新节点 ,将新节点的数据填充为要插入的数据
  LTNode* first = phead->next; //使用phead->next找到当前双向链表的头节点
  phead->next = newnode;  //将链表头节点phead的next指针指向新插入的节点newnode
  newnode->prev = phead;  //将待插入节点newnode的prev指针指向链表的头节点phead。
  newnode->next = first;  //将待插入节点newnode的next指针指向原头节点first。
  first->prev = newnode;  //将原头节点first的prev指针指向插入的新节点newnode。
}


双向链表尾删


  • 双向链表尾删步骤
  1. 判断链表是否为空,如果为空,则无法进行删除操作
  2. 使用phead->prev找到当前双向链表的尾节点.(用一个临时变量tail来记录)
  3. 使用tail->prev找到当前尾节点的前一个节点。(用一个临时变量tailPrev来记录)
  4. 释放尾节点tail的内存空间
  5. 将tailPrev的next指针指向链表头节点phead。
  6. 将链表头节点phead的prev指向tailPrev


void LTPopBack(LTNode* phead)
{
  assert(phead);  //判断头指针是否为空
  assert(!LTEmpty(phead)); //断言:判断链表是否为空,如果为空,则无法进行删除操作
  LTNode* tail = phead->prev;    //使用phead->prev找到当前双向链表的尾节点.
  LTNode* tailPrev = tail->prev; //使用tail->prev找到当前尾节点的前一个节点
  free(tail); //释放尾节点tail的内存空间
  tailPrev->next = phead; //将tailPrev的next指针指向链表头节点phead
  phead->prev = tailPrev; //将链表头节点phead的prev指向tailPrev
}


双向链表头删


  • 双向链表头删步骤
  1. 判断链表是否为空,如果为空,则无法进行删除操作
  2. 使用phead->next找到当前双向链表的头节点下一个。(用一个临时变量first来记录)
  3. 使用first->next找到当前头节点的下一个节点(用一个临时变量second来记录)
  4. 将链表头节点phead的next指针指向second节点。
  5. 将second节点的prev指针指向链表头节点phead。
  6. 释放头节点first的内存空间,进行头删.


void LTPopFront(LTNode* phead)
{
  assert(phead); 判断头指针是否为空
  assert(!LTEmpty(phead)); 断言:判断链表是否为空,如果为空,则无法进行删除操作
  LTNode* first = phead->next;  //使用phead->next找到当前双向链表的头节点的下一个
  LTNode* second = first->next; //使用first->next找到当前头节点的下一个节点
  phead->next = second;  //将链表头节点phead的next指针指向second节点
  second->prev = phead;  //将second节点的prev指针指向链表头节点phead
  free(first); //进行头删
}


双向链表的查找


  • 获得链表某个节点的数据思路也较简单
  1. 从头节点的下一个节点开始,依次遍历链表中的每个节点。
  2. 在每个节点的数据域中查找节点的值是否为x,如果是则返回该节点的指针
  3. 如果遍历完整个链表都没有找到节点的值为x,则返回NULL。
LTNode* LTFind(LTNode* phead, LTDataType x)
{
  assert(phead); ///判断头指针是否为空
  LTNode* cur = phead->next; //从头节点的下一个节点开始,依次遍历链表中的每个节点。
  while (cur != phead)
  {
    if (cur->data == x) //在每个节点的数据域中查找节点的值是否为x,如果是则返回该节点的指针
    {
      return cur;
    }
    cur = cur->next; //迭代 指向下一个
  }
  return NULL; //如果遍历完整个链表都没有找到节点的值为x,则返回NULL。
}


双向链表在指定位置前插入数据


双向链表插入数据不用像单链表一样从头查找,双向链表只需原地动数据就可。具体步骤如下:

  1. 获取pos节点的前一个节点(使用一个临时变量tmp来保存)
  2. 创建一个新的待插入节点newnode
  3. 将tmp节点的next指向待插入节点newnode
  4. 将待插入节点newnode的prev指针指向tmp节点
  5. 将待插入节点newnode的next指针指向pos节点
  6. 将pos节点的prev指针指向待插入节点newnode


// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);//节点pos不为空
  LTNode* tmp = pos->prev; //获取pos节点的前一个节点
  LTNode* newnode = BuyLTNode(x); //创建一个新的待插入节点newnode
  tmp->next = newnode; //将tmp节点的next指向待插入节点newnode
  newnode->prev = tmp; //将待插入节点newnode的prev指针指向tmp节点
  newnode->next = pos;  //将待插入节点newnode的next指针指向pos节点
  pos->prev = newnode;  //将pos节点的prev指针指向待插入节点newnode
}


双向链表删除指定位置的值


  • 删除指定位置的具体逻辑步骤

1.获取pos节点的前一个节点和后一个节点。(用posprev和posnext临时变量来记录)

2.将posPrev节点的next指向posNext节点

3.将posNext节点的prev指向posPrev节点

4..释放要删除的节点pos的内存空间。


void LTErase(LTNode* pos)
{
  assert(pos); //节点pos不为空
    //获取pos节点的前一个节点和后一个节点
  LTNode* posPrev = pos->prev;
  LTNode* posNext = pos->next;
  posPrev->next = posNext;  //将posPrev节点的next指向posNext节点
  posNext->prev = posPrev;  //将posNext节点的prev指向posPrev节点
  free(pos);  //释放要删除的节点pos的内存空间。
}


双向链表的销毁


  • 当我们不打算使用这个单链表时,我们需要把它销毁,其实也就是在内存中将它释放掉,

以便于留出空间给其他程序或软件使用。释放内存具体步骤如下:

1.使用一个指针变量遍历整个链表在循环中,对于当前遍历到的节点,将其保留下一个节点的指针,以便于在释放当前指针后,指向的节点时能够顺利找到下一个节点.

2.先从头指针的下一个节点开始释放,最后在释放头指针.


void LTDestroy(LTNode* phead)
{
  assert(phead); //断言:头指针不能为空
  LTNode* cur = phead->next;//先指向有效位置头指针的下一个节点
  while (cur != phead)
  {
    LTNode* next = cur->next; //保存下一个指针
    free(cur); //释放cur节点占用的内存空间,
    cur = next; //迭代
  }
  free(phead); //释放头指针
}


总结



  • 双向链表相对于单向链表的优点在于它可以支持双向遍历,即从链表头或尾部开始遍历,

因此它可以在某些情况下更加高效。同时,双向链表也支持在任意位置进行链表节点的插入和删除操作,这是单向链表不支持的。因此,双向链表更加灵活,可以满足更多场景下的需求。


  • 相对于单链表,双向链表的节点需要额外存储一个指针,即指向前面节点的指针,因此相

对于单链表会占用更多的内存空间。


总之,双向链表是一种值得掌握的重要数据结构,掌握了它的基本操作和应用场景,可以大大提高算法和数据结构等领域的编程水平。

目录
相关文章
|
3月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
80 4
|
11天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
75 29
|
11天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
63 29
|
11天前
|
存储 机器学习/深度学习 人工智能
C 408—《数据结构》易错考点200题(含解析)
408考研——《数据结构》精选易错考点200题(含解析)。
84 27
|
11天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
70 25
|
1月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
38 5
|
2月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
2月前
|
存储 算法 C语言
【C语言】深入浅出:C语言链表的全面解析
链表是一种重要的基础数据结构,适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现,以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。
751 6
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
97 5
|
3月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
161 4

推荐镜像

更多