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

本文涉及的产品
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 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); //释放头指针
}


总结



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

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


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

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


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

目录
相关文章
|
2天前
|
存储 消息中间件 NoSQL
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
|
1天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
21天前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
23 7
|
21天前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
20 3
|
20天前
|
算法 Java
数据结构与算法学习五:双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现,并通过实例演示了双向链表的优势和应用。
14 0
数据结构与算法学习五:双链表的增、删、改、查
|
1天前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
14天前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
16 0
|
19天前
|
存储
探索数据结构:便捷的双向链表
探索数据结构:便捷的双向链表
|
19天前
|
存储
探索数据结构:单链表的实践和应用
探索数据结构:单链表的实践和应用

推荐镜像

更多