欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 社会 > 【落羽的落羽 数据结构篇】双向链表

【落羽的落羽 数据结构篇】双向链表

2025/2/25 16:31:02 来源:https://blog.csdn.net/2402_86681376/article/details/145611293  浏览:    关键词:【落羽的落羽 数据结构篇】双向链表

在这里插入图片描述

文章目录

  • 一、链表的分类
  • 二、双向链表
    • 1. 结构
    • 2. 申请一个新节点
    • 3. 尾部插入数据
    • 4. 头部插入数据
    • 5. 尾部删除数据
    • 6. 头部删除数据
    • 7. 在指定位置之后插入数据
    • 8. 删除指定位置节点
    • 9. 销毁链表

一、链表的分类

链表的分类实际上要从这三个方向分析:是否带头、单向还是双向、是否循环。

“带头”指链表是否有“头节点”,并不指链表的第一个节点,而是一个不存储有效数据的“哨兵位”,作用仅仅是表明链表的起始点。上次讲的单链表中我们说的“首节点”,只是链表的第一个存储数据的节点,并不是头节点,这个单链表是没有头结点的

单链表是单向链表,也存在双向链表,也就是这种链表的节点有两个指针成员,一个指向下一个节点、一个指向上一个节点。

循环就很好理解了,节点的指针成员循环指向。

所以,理论上我们能把链表分为2×2×2=8种:带头单向不循环链表、不带头双向不循环链表、带头双向循环链表……
上次我们学习的“单链表”,全称应该就是“不带头单向不循环链表”。而我们这次要学习的“双向链表”,全称是“带头双向循环链表”。这两种链表也是最常用的两种。

在这里插入图片描述

二、双向链表

1. 结构

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

这是双向链表的每一个节点的结构。next指针指向下一个节点,prev指针指向上一个节点
值得注意的是,单链表为空时,链表一个节点都没有;双向链表为空时,它仍有一个哨兵位,如果连哨兵位都没有的话,这不是双向链表而是单链表。同时,这个哨兵位的next指针和prev指针都是指向自己的。
在这里插入图片描述
在这里插入图片描述

2. 申请一个新节点

LTNode* BuyNode(LTDataType x)
{  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));assert(newnode);newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}

测试:
在这里插入图片描述

3. 尾部插入数据

这里的“尾部”,是头结点的prev指针指向的位置

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);newnode->next = phead; //新尾结点的next指向头结点newnode->prev = phead->prev; //新尾结点的prev指向原尾结点phead->prev->next = newnode; //原尾结点的next指向新尾结点phead->prev = newnode; //头结点的prev指向新尾结点
}

测试:
在这里插入图片描述
在这里插入图片描述

4. 头部插入数据

“头部”是头结点的next指向的位置

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

测试:
在这里插入图片描述
在这里插入图片描述

5. 尾部删除数据

void LTPopBack(LTNode* phead)
{assert(phead != phead->next); //保证原链表不为空,否则无数据可删LTNode* del = phead->prev; //要删除的节点设置成deldel->prev->next = phead; //del的前一个节点的next指向头结点phead->prev = del->prev; //头结点的prev指向del的前一个节点free(del);del = NULL;
}

测试:
在这里插入图片描述

6. 头部删除数据

void LTPopFront(LTNode* phead)
{assert(phead != phead->next);LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

测试:在这里插入图片描述

7. 在指定位置之后插入数据

void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyNode(x);newnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}

测试:
在这里插入图片描述

8. 删除指定位置节点

void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

测试:
在这里插入图片描述

9. 销毁链表

void LTDestory(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

测试:
在这里插入图片描述

本篇完,感谢阅读

在这里插入图片描述

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词