数据结构之双向链表
目录
节点的定义
函数接口的实现
1.初始化哨兵位
2. 创造节点
3.尾插
4.头插
5.尾删
6.头删
7.查找
8. 在pos节点之后插入
9.删除pos节点
10.打印链表
11.摧毁链表
介绍
双向链表与单链表大体上差不多,都是不连续的存储结构,顾名思义,双向链表与单链表不同的是,双链表是双向的,而单链表只能向后节点移动,是单向的；需要注意的是：双链表是带头的,也就是在头部有一个哨兵位,双链表的全称就是双向带头循环链表。
节点的定义
typedef struct ListNode
{
DataType data;
struct ListNode* pre;
struct ListNode* next;
}LTnode;相比单链表多了一个前躯节点,用来指向前一个节点， 其他的没有变化；
DataType代表的是数据的类型,通过宏定义；
函数接口的实现
1.初始化哨兵位
这里我采用的方法是,利用函数创造哨兵位,用一个指针来接收；
LTnode* LTinit()//返回初始化的哨兵位
{
LTnode*pphead = (LTnode*)malloc(sizeof(LTnode));
if (pphead == NULL)
{
perror("malloc fail");
exit(1);
}
(pphead)->data = -1;
(pphead)->pre = (pphead);
(pphead)->next = pphead;
return pphead;
}在函数中,利用结构体指针进行开辟空间,这里我们把data的值初始化为-1，因为此时之有一个节点,我把前驱指针和后继指针都指向哨兵位自身，最后返回节点；
2. 创造节点
后续的插入需要创造节点来储存数据，所以使用函数进行包装；
//创造节点
LTnode* creat(DataType x)
{
LTnode* newnode = (LTnode*)malloc(sizeof(LTnode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->data = x;
newnode->next = newnode->pre = NULL;
return newnode;
}与单链表相似,这里不便多言；
3.尾插
由图可知,尾节点前驱指针指向前一个节点;后继指针指向哨兵位；
//尾插
void PushBack(LTnode* pphead, DataType x)
{
assert(pphead);
LTnode* newnode = creat(x);
newnode->pre = pphead->pre;//新节点的前指针指向最后的一个节点
newnode->next = pphead;//然后新节点的后指针指向哨兵位
pphead->pre->next = newnode;//修改原尾节点的指向,指向新节点,
pphead->pre = newnode;//最后是head的前指针指向新尾节点
}创造新节点newnode，然后改变newnode的前后指针指向,newnode的前指针指向前一个节点,而前一个节点我们不需要进行遍历,可以使用哨兵位的前驱节点, 然后依次改变新节点、原尾节点、哨兵位的前后指向即可；
4.头插
//头插
void PushFrint(LTnode* pphead, DataType x)
{
assert(pphead);
LTnode* newnode = creat(x);
newnode->pre = pphead;
newnode->next = pphead->next;
pphead->next->pre = newnode;
pphead->next = newnode;
}需要注意的是,当链表中只剩下哨兵位时,链表就为空；这里头插是在 图中d1的前面,head的后面插入，而d1可以用head->next来表示，先将newnode的前后指针指向head和d1，然后改变d1的前指针，最后改变head的后指针；
5.尾删
//尾删
void PopBack(LTnode* pphead)
{
assert(pphead);
assert(pphead->next != pphead);
LTnode* del = pphead->pre;//最后一个节点
LTnode* prev = del->pre;//倒数第二个节点
prev->next = pphead;
pphead->pre = prev;
free(del);
del == NULL;
}这里将d3表示成del，d2表示成prve，要删除d3就可以直接释放掉，改变d2的后继指针，和head的前指针即可;
6.头删
//头删
void PopFrint(LTnode* pphead)
{
assert(pphead);
assert(pphead->next!=pphead);
LTnode* next = pphead->next->next;//原链表的第3个节点
LTnode* del = pphead->next;//原链表的第2个节点
pphead->next = next;//哨兵位直接指向第二个节点
next->pre = pphead;
free(del);
del = NULL;
}同理,改变3个节点的前后指针指向即可；
7.查找
//查找
LTnode* Find(LTnode* pphead,DataType x)
{
assert(pphead);
LTnode* pcur = pphead->next;
while (pcur != pphead)
{
if (pcur->data != x)
{
pcur = pcur->next;
}
else
return pcur;
}
return NULL;
}查找的时间复杂度是O(N)，直接进行遍历即可，找到就返回节点所在位置的地址,找不到就返回NULL;
8. 在pos节点之后插入
//在pos之后插入
void InsertBack(LTnode* pos, DataType x)
{
LTnode* newnode = creat(x);
LTnode* back = pos->next;
newnode->pre = pos;
newnode->next = back;
pos->next = newnode;
back->pre = newnode;
}pos节点是已知的，在其之后插入新的节点newnode，然后进行前后节点的指向更新即可；
9.删除pos节点
//在pos之后插入
void InsertBack(LTnode* pos, DataType x)
{
LTnode* newnode = creat(x);
LTnode* back = pos->next;
newnode->pre = pos;
newnode->next = back;
pos->next = newnode;
back->pre = newnode;
}10.打印链表
//打印
void Print(LTnode* pphead) {
assert(pphead);
LTnode* pcur = pphead->next;
while (pcur != pphead)
{
printf("%d-> ", pcur->data);
pcur = pcur->next;
}
printf("head\n");
}依次进行遍历打印,直到再次回到哨兵位；
11.摧毁链表
//摧毁链表
void Destory(LTnode* pphead)
{
assert(pphead);
LTnode* pcur = pphead->next;
while (pcur != pphead)
{
LTnode* next = pcur->next;;
free(pcur);
pcur = NULL;
pcur = next;
}
free(pcur);
pcur = NULL;
}摧毁链表：从哨兵位的后一个节点开始进行遍历依次释放,最后循环结束在释放哨兵位；