还在被双链表绕晕？这篇保姆级教程带你彻底吃透（含完整C实现）
月华透云上枝头，稚雏也学雀南飞。
此朝花间挑芙蓉，莺莺燕燕娇欲滴。
岂敢良景乏乏眼，正是华灯初上时。
可将此生留其中，往是你去也是你。
1. 链表的分类
1.1单双向
单向链表（以单链表为例子）双向链表（以双链表为例）
1.2带头或不带头
不带头：头节点直接存储有效数据
带头：头节点不存储有效数据，而是存储第一个有效节点的地址（可视为占位子或者哨兵位）
1.3循环和不循环
不循环（存在尾结点，也可以说某个节点的next指针指向NULL）
循环（所有结点中的next指针没有指向NULL）
综上所述可以列举出八种不同的链表类型，日常主要是应用两种链表：
Ⅰ：无头单向非循环链表（即单链表）
结构简单，一般不会用于单独存储数据，实际应用于作为其他数据结构的子结构，如哈希桶，图的邻接表等
Ⅱ：带头双向循环链表
结构复杂，一般用于单独存储数据，一个节点由三个部分组成：前驱指针+后驱指针+保存数据
2.双链表的接头实现（C语言）
2.1对双链表类型的成员定义（包含的重命名）
typedef int LTDataType; typedef struct ListNode { LTDataType data;//要存储的有效数据 struct ListNode* next;//保存下一个节点地址的指针 struct ListNode* prev;//保存上一个节点地址的指针 }LTNode;2.2双链表初始化
以下代码存在一些问题，pphead可能不为空指针，但*pphead可能为空指针，因为情况一：此时链表中不存在节点，此处初始化的节点是第一个节点运行程序时可能会出现问题
void LTInit(LTNode** pphead) { assert(pphead);//判断是否为NULL，防止对空指针解引用 (*pphead)->data = -1;//将存储的有效数据初始化为-1 (*pphead)->prev = (*pphead)->next = *pphead;//前驱指针和后驱指针全部指向自身 }2.0初始化版本
void LTInit(LTNode** pphead) { assert(pphead); LTBuyNode(-1);//后面的函数调用，作用是申请一个节点的空间，并将有效数据保存其中 }2.3双链表创建节点空间
LTNode* LTBuyNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); //申请一个节点的空间，并且保存这个空间的地址给newnode if (newnode == NULL) { perror("malloc fail!"); exit(1); }//判断是否申请空间成功 newnode->data = x;//将数据保存到新申请的节点中 newnode->prev = newnode->next = newnode;//将前驱指针和后驱指针全部指向自身 return newnode;//返回新节点的地址 }2.4双链表的打印
void LTPrint(LTNode* phead) { LTNode* pcur = phead->next; while (pcur != phead) { printf("%d->", pcur->data); pcur = pcur->next; } printf("\n"); }2.5双链表的尾插（头节点不需要改变则传一级指针，否则传二级指针）
观察上方两幅图示可知仅需改变：
原链表：d3的next指向newnode
head的prev指向newnode
新节点：prev指向d3
next指向head
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTBuyNode(x); //优先改变对原链表无影响的部分，即新插入的节点 newnode->prev = phead->prev; newnode->next = phead; //再修改原链表 phead->prev->next = newnode;//尾节点修改 phead->prev = newnode;//头节点修改 }2.6判断链表是否为空（仅有一个头节点的情况下双链表为空）
bool LTEmpty(LTNode* phead) { assert(phead); return phead->next == phead; }2.7双链表的尾删（注意：链表不可为空）
主要修改对象是：头节点和倒数第二个节点
修改对象：倒数第二个节点的next指向头节点
head->prev指向倒数第二个节点
void LTPopBack(LTNode* phead) { assert(!LTEmpty(phead)); LTNode* del = phead->prev; del->prev->next = phead; phead->prev = del->prev; free(del); del = NULL; }2.8双链表的头插（在第一个有效节点前插入）
注意：不能先使head->next指向new->prev，这样会使原链表的第一个节点地址丢失
故先使d1->prev指向newnode，再使head->next指向newnode
void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTBuyNode(x); newnode->next = phead->next;//新节点的next指向原链表的第一个节点 newnode->prev = phead;//新节点的prev指向头节点 phead->next->prev = newnode;//原链表的第一个节点的prev指向新节点 phead->next = newnode;//头节点的next指向新节点 }2.9双链表的头删
修改对象：d2的prev指向head
head的next指向d2
void LTPopFront(LTNode* phead) { assert(!LTEmpty(phead)); LTNode* del = phead->next;//del指向第一个有效节点 del->next->prev = phead;//原链表的第二个节点的prev指向头节点 phead->next = del->next;//头节点的next指向原链表的第二个节点 free(del); del = NULL; }2.10双链表的查找
LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* pcur = phead->next;//pcur初始化指向第一个有效节点 while (pcur != phead) { if (pcur->data == x) { return pcur; } pcur = pcur->next;//pcur指针不断向后移动，直到指向头节点退出 } return NULL; }2.11删除双链表中指定位置pos的节点
void LTErase(LTNode* pos) { assert(pos); pos->next->prev = pos->prev;//pos的下一个节点的prev指向pos的前一个节点 pos->prev->next = pos->next;//pos的前一个节点的next指向pos的下一个节点 free(pos); pos = NULL; }2.12在指定位置pos之后插入数据
处理对象：Ⅰ：先对原链表无影响的newnode进行处理
newnode的next指向pos的next
newnode的prev指向pos
Ⅱ：不可以通过原链表进行改动，读者大可一试，小编try过几次，还是觉得通过新节点间接改动原链表更有效且正确
void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTBuyNode(x); newnode->next = pos->next; newnode->prev = pos; pos->next->prev = newnode; pos->next = newnode; }2.13销毁链表
void LTDestroy(LTNode** pphead) { LTNode* pcur = (*pphead)->next; while (pcur != *pphead) { LTNode* next = pcur->next; free(pcur); pcur = next; } free(*pphead); *pphead = NULL; }双链表的销毁需要一个一个节点单独销毁，小编给出的销毁实现函数是传入二级指针，有违背接口的一致性，各位读者也可以改为一级指针，之后在调用完函数之后手动置空