详解双向循环带头节点链表——十分钟单手吊打链表
source link: https://blog.51cto.com/u_15323899/5145754
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
详解双向循环带头节点链表——十分钟单手吊打链表
推荐 原创传统艺能👏
小编是双非本科大一计科菜鸟（打灰人 ）不赘述，欢迎大佬指点江山
此前博客 点我！点我！请搜索博主 【知晓天空之蓝】
过渡区👏
10天军训终于完了，时间管理大师都没法在这段时间打理学习，中途用所剩无几的理性上传了一篇之前笔记随笔，阅读量却没让我失望，于是我就以最快的速度回来继续奋勇直追！
和单链表比较😎
之前我讲过了单链表，也就是单向不带头不循环链表，看起来和现在的这个简直天差地别，但是——没有关系，我们必须知道一点：
单向不带头不循环链表是最简单的结构，但实现却比较复杂
双向循环带头节点链表是最复杂的结构，但实现却最简单
单链表一般出现在我们熟知的 OJ 题目中，而生活中实际运用却高度依赖于双链表，因为双链表效率高，实现方便，简单易懂，代码清爽，结构严谨，巴拉巴拉……
之前提到过三个分类：
双向就是后一个节点存有指向前一个和后一个的指针，既可以正向访问也可以逆向访问，相比单链表灵活性直接上了一个档次。
所谓带头，指的就是带哨兵位的头，这里的哨兵位相当于一个结构体。
循环就是指链表尾节点不指向 NULL 而是指向 phead，从而使头插头删尾插尾删等基本操作变得十分简单。
当然不止以上6种，两两排列组合可以得到更多的形式。
空间申请😎
老规矩，开辟空间肯定是第一步：
{
Seqlist* newnode = (Seqlist*) malloc (sizeof(Seqlist));
if (newnode == NULL)
{
printf("malloc fail!\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
初始化😎
phead=ListInit();
这里就开始设置哨兵位头节点：
{
Seqlist* phead = buymalloc(0);
phead->next = phead;//指向下一个节点的指针指向自身
phead->prev = phead;//指向上一个节点的指针指向自身
return phead;
}
因为创建的结构体指针 phead 指向NULL，因此我们需要在初始化时创建一个哨兵位头结点，使 phead 指向这个头节点；在后续的使用中，plist始终是指向这个头结点，并不会被修改，因此不需要传入二级指针
存在哨兵位头结点时，改变的是哨兵位（结构体）节点，传入的是结构体的指针（地址），非哨兵位改变的是结构体指针那传入的就是结构体指针的指针（地址）
注意：这里开辟空间参数为 0，这里目的是只要让头结点不为空即可，不用在意值的大小。
以基本功能举两个栗子来实际体会一下和单链表的差距：
{
assert(phead);
Seqlist* newnode = buymalloc(x);
Seqlist* tail = phead->prev;
tail->next = newnode;
tail = newnode->prev;
newnode->next = phead;
phead->prev = newnode;
}
用ppt手残一张图出来配合食用，勿喷捏：
注意各个步骤的顺序，前后的逻辑严格，不可随意调换，稍有差错就可能找不到前一个或者后一个节点的地址。
{
assert(phead);
assert(phead != phead->next);
Seqlist* tail = phead->prev;
Seqlist* tailprev = tail->prev;
free(tail);
tail = NULL;
tailprev->next = phead;
phead->prev = tailprev;
}
pos位插入🤔
其实比起头插尾插，pos位插入其实更为简单，注意pos位插入是指 pos 的前一位插入，思路即 pos 前前一个节点与pos前一个节点链接，再和 pos 后一个节点链接就行，中间步骤直接链接即可。
{
assert(pos);
Seqlist* newnode = buymalloc(x);
Seqlist* posprev = pos->prev;//找到插入节点的正确位置
newnode->next = pos;
posprev->next = newnode;
newnode->prev = posprev;
}
我们之前说过，头插头删尾插尾删其实是 pos 位插入删除的特殊实现情况，所以我们格局打开：写出 pos 位插入删除即可搞定所有插删操作。
那么头插就可以写成这样：
{
assert(phead);
insert(phead->next,x);
}
尾插同理：
{
assert(phead);
insert(phead,x);
}
????是不是突然就觉得头尾删插是个什么渣渣！
没错，这就是结构最复杂操作却最简单的双向带头循环链表。
Slist.h🤔
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int Seqtype;
typedef struct Seqlist
{
Seqtype data;
struct Seqlist* next;
struct Seqlist* prev;
}Seqlist;
Seqlist* buymalloc(Seqtype x);//开辟空间
Seqlist* init();//初始化
void print(Seqlist* phead);//打印
void pushback(Seqlist* phead, Seqtype x);//尾插
void popback(Seqlist* phead);//尾删
void popfront(Seqlist* phead);//头删
void pushfront(Seqlist* phead, Seqtype x);//头插
Seqlist* find(Seqlist* phead, Seqtype x);//查找
void insert(Seqlist* pos, Seqtype x);//pos位插入
void erase(Seqlist* pos);//pos位删除
test.c🤔
#include"Slist.h"
void test()
{
Seqlist* phead = init();
pushback(phead, 2);
pushback(phead, 3);
popback(phead);
print(phead);
}
int main()
{
test();
return 0;
}
Slist.c🤔
#include"Slist.h"
Seqlist* buymalloc(Seqtype x)
{
Seqlist* newnode = (Seqlist*) malloc (sizeof(Seqlist));
if (newnode == NULL)
{
printf("fail!\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
void pushback(Seqlist* phead, Seqtype x)
{
assert(phead);
Seqlist* newnode = buymalloc(x);
Seqlist* tail = phead->prev;
tail->next = newnode;
tail = newnode->prev;
newnode->next = phead;
phead->prev = newnode;
}
//哨兵位头结点，改变的是哨兵位（结构体）节点，
//传的是结构体的指针（地址），非哨兵位改变的是结构体指针那
//传的就是结构体指针的指针（地址）
void print(Seqlist* phead)
{
assert(phead);
Seqlist* newnode = phead->next;
while(newnode != phead)
{
printf("%d ", newnode->data);
newnode = newnode->next;
}
}
Seqlist* init()
{
Seqlist* phead = buymalloc(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
void popback(Seqlist* phead)
{
assert(phead);
assert(phead != phead->next);
Seqlist* tail = phead->prev;
Seqlist* tailprev = tail->prev;
free(tail);
tail = NULL;
tailprev->next = phead;
phead->prev = tailprev;
}
void insert(Seqlist* pos, Seqtype x)
{
assert(pos);
Seqlist* newnode = buymalloc(x);
Seqlist* posprev = pos->prev;
newnode->next = pos;
posprev->next = newnode;
newnode->prev = posprev;
}
void pushfront(Seqlist* phead, Seqtype x)
{
assert(phead);
insert(phead->next, x);
}
Seqlist* find(Seqlist* phead, Seqtype x)
{
assert(phead);
Seqlist* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
今天就到这里吧，摸了家人们。
- 打赏
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
-
35
双向链表的定义 双向链表也叫 双链表 ，是链表的一种，它的每个数据结点中都有两个
-
28
总结 Redis 无环双向链表的实现。 函数指针 Redis 链表结构内置了三个指向操作函数的函数指针，先梳理下函数指针用法。 定义 函数体在编译期间会被存入进程代码段内存的一片连续区域中，而函数...
-
38
本文介绍什么是链表，常见的链表有哪些，然后介绍链表这种数据结构会在哪些地方可以用到，以及 Redis 队列是底层的实现，通过一个小实例来演示 Redis 队列有哪些功能，最后通过 Go 实现一个双向链表。
-
30
一、回顾 单链表 是由 一段 连续或不连续 的物理地址来 存储元素 的。通过存储指针的方式，链表的每个结点中都储存了下一个结点元素的地址。...
-
27
目录 前言 20201010 在阅读 RTOS LiteOS 内核源码时发现该内核使用的链表时 通用链表 ，而 FreeRTOS 内核使用的时 非通用链表 ，所以，有必要发布一下关于链表...
-
10
一、双向带头循环链表的优劣势 结构复杂，但由于结点信息中多包含了一个指向上一个结点的指针，这样操作起来就特别方便，它弥补了单链表的缺点，使得链表更加灵活、实用。
-
2
🍓本文出现如此多草莓的原因是，我昨天晚上吃了好多草莓，并且现在还想吃。 🍓接下来要更新链表这儿的题解咯~ 正文开始@边通书 上文提到，带头双向循环链表 —— 结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构...
-
5
“花自飘零水自流，一种相思,两处闲愁。” “此情无计可消除，才下眉头，却上心头”
-
4
双向带头循环链表的(增删查改)的实现 推荐 原创 萌新的日常 2022-09-22 08:28:19
-
8
LRU缓存 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类： LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK