我宁愿靠自己的力量，打开我的前途，而不愿求有力者垂青
文章目录
双线向链表各接口函数名或变量名
双向链表接口实现源码
快速索引【头文件及函数声明】
双向链表接口实现
双向链表的构造分析
双向链表的定义及初始化
双向链表的插入和删除
往期回顾：
数据结构——单链表
数据结构——顺序表
大家好，我是纪宁。
这篇文章向大家介绍一种相对单链表性能更优的链表——双向链表，它能更高效的实现数据的插入、删除和查找等。
文章前半段是双向链表对应名称和源码，文章后半段是对双向链表实现的具体解释。
双线向链表各接口函数名或变量名
| LTDataType | 双向链表数据类型重命名 |
| ListNode | 双向链表结构体 |
| LTNode | 双向链表的重命名 |
| BuyLTNode | 创建一个结点 |
| LTInit | 初始化结点 |
| LTPrint | 打印双向链表 |
| LTPushBack | 尾插 |
| LTPopBack | 尾删 |
| LTPushFront | 头插 |
| LTPopFront | 头删 |
| LTSize | 计算双向链表元素个数 |
| LTFind | 找链表元素 |
| LTInsert | 在pos之前插入结点 |
| LTErase | 删除pos位置的结点 |
双向链表接口实现源码
快速索引【头文件及函数声明】
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;//重命名typedef struct ListNode
{LTDataType Data;struct ListNode* next;struct ListNode* prev;
}LTNode;
LTNode* BuyLTNode(LTDataType x); //创建一个新节点
LTNode* LTInit(); //哨兵位的头结点
void LTPrint(LTNode*phead);//打印双链表
void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾删
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);//头删
LTNode* LTFind(LTNode* phead, LTDataType x);//寻找结点
void LTInsert(LTNode*phead,LTNode* pos, LTDataType x); //在pos之前插入结点双向链表接口实现
LTNode* BuyLTNode(LTDataType x)
{LTNode* nownode =(LTNode*)malloc(sizeof(LTNode));if (nownode == NULL){perror("malloc fail");}nownode->Data = x;nownode->next = NULL;nownode->prev = NULL;return nownode;
}LTNode* LTInit()
{LTNode* phead = BuyLTNode(0);phead->next = phead;phead->prev = phead;return phead;
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->prev;LTNode* nownode = BuyLTNode(x);nownode->next = phead;nownode->prev = tail;tail->next = nownode;phead->prev = nownode;
}void LTPrint(LTNode* phead)
{assert(phead);printf("phead<=>");LTNode* cur = phead;while (cur->next!=phead){printf("%d<=>", cur->next->Data);cur = cur->next;}printf("\n");
}void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);//只有哨兵位的时候不能删LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;tailPrev->next = tail->next;phead->prev = tailPrev;free(tail);
}
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* first = phead->next;LTNode* nownode = BuyLTNode(x);nownode->next = first;nownode->prev = phead;phead->next = nownode;first->prev = nownode;
}void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);//只有哨兵位的时候不能删除LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);
}LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead;while (cur->next != phead){if (cur->next->Data == x)return cur->next;cur = cur->next;}return NULL;
}void LTInsert(LTNode* phead, LTNode* pos, LTDataType x)
{assert(phead);assert(pos);LTNode* cur = phead;while (cur->next != pos){cur = cur->next;}LTNode*nownode = BuyLTNode(x);nownode->next = pos;nownode->prev = cur;cur->next = nownode;pos->prev = nownode;
}void LTErase(LTNode* phead, LTNode* pos)
{assert(pos&&phead);assert(pos->next != pos);assert(phead->next != phead);LTNode* cur = phead;LTNode* posNext = pos->next;while (cur->next != pos){cur = cur->next;}cur->next = posNext;posNext->prev = cur;free(pos);
}双向链表的构造分析
双向链表，相对于单链表不同的是双向链表的节点有两个指针域，一个指向后一个节点，另一个指向前一个节点，默认双向链表都是有带哨兵位的头节点，哨兵位的头节点中储存着第一个有效节点的地址（phead->next）和最后一个有效节点的地址（phead->prev）。
单双链表逻辑图对比
单双链表物理图对比
双向链表的定义及初始化
双向链表中有一个数据域和两个指针域，一个指针指向下一个节点的地址，一个指针指向上一个节点的地址，将这个双链表的结构再重命名。
双向链表在新开辟节点的时候，要先开辟一个节点大小的空间，将它的 next 和 NULL 指向空，然后将它的数据域值赋为 x。
双向链表的插入和删除
双向链表的删除，首先要要明确的一点是不能删除哨兵位这个头节点，因为它是整个双向链表的结构支撑。删除的时候，要找到即将删除节点的上一个节点和下一个节点，将上一个节点的 next 指针指向下一个节点，将下一个节点的 prev 指针指向 上一个节点。最后，将删除的节点空间释放。
双向链表的插入，在插入的时候，理论上在任何位置都是可以插入节点的。因为在初始化的时候，定义新创建节点的指针域都为空。所以在插入的时候，要改变插入节点的两个指针域，将它的next 指针指向下一个节点，将它的 prev 指针指向上一个节点。同样，将上一个节点的 next 指针指向这个新节点，将下一个指针的 prev 指针指向这个新节点。
