和单链表比较🤔
之前我讲过了单链表，也就是单向不带头不循环链表，看起来和现在的这个简直天差地别，但是——没有关系，我们必须知道一点：
单向不带头不循环链表是最简单的结构，但实现却比较复杂
双向循环带头节点链表是最复杂的结构，但实现却最简单
单链表一般出现在我们熟知的 OJ 题目中，而生活中实际运用却高度依赖于双链表，因为双链表效率高，实现方便，简单易懂，代码清爽，结构严谨，巴拉巴拉……
分类🤔
之前提到过三个分类：
循环就是指链表尾节点不指向 NULL 而是指向 phead，从而使头插头删尾插尾删等基本操作变得十分简单。
当然不止以上6种，两两排列组合可以得到更多的形式。
空间申请👏
老规矩，开辟空间肯定是第一步：
Seqlist* buymalloc(Seqtype x) { 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; }
初始化👏
Seqlist* phead = NULL; phead=ListInit();
这里就开始设置哨兵位头节点：
Seqlist* init() { Seqlist* phead = buymalloc(0); phead->next = phead;//指向下一个节点的指针指向自身 phead->prev = phead;//指向上一个节点的指针指向自身 return phead; }
因为创建的结构体指针 phead 指向NULL，因此我们需要在初始化时创建一个哨兵位头结点，使 phead 指向这个头节点；在后续的使用中，plist始终是指向这个头结点，并不会被修改，因此不需要传入二级指针
存在哨兵位头结点时，改变的是哨兵位（结构体）节点，传入的是结构体的指针（地址），非哨兵位改变的是结构体指针那传入的就是结构体指针的指针（地址）
注意：这里开辟空间参数为 0，这里目的是只要让头结点不为空即可，不用在意值的大小。
尾插👏
以基本功能举两个栗子来实际体会一下和单链表的差距：
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 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; }
pos位插入👏
其实比起头插尾插，pos位插入其实更为简单，注意pos位插入是指 pos 的前一位插入，思路即 pos 前前一个节点与pos前一个节点链接，再和 pos 后一个节点链接就行，中间步骤直接链接即可。
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; }
我们之前说过，头插头删尾插尾删其实是 pos 位插入删除的特殊实现情况，所以我们格局打开：写出 pos 位插入删除即可搞定所有插删操作。
那么头插就可以写成这样：
😎是不是突然就觉得头尾删插是个什么渣渣！😎
没错，这就是结构最复杂操作却最简单的双向带头循环链表。
源码奉上🎉
Slist.h
#pragma once #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
# define _CRT_SECURE_NO_WARNINGS #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
# define _CRT_SECURE_NO_WARNINGS #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; }
