1.双向链表的概念
1.1头节点
1.2带头双向循环链表
注意: 哨兵位创建后,首尾连接自己
1.3双链表的初始化
// 双向链表的初始化
void ListInit(ListNode** pphead)
{
// 给双链表创建一个哨兵位
*pphead = ListBuyNode(-1);
}
2.双向链表的打印
// 双向链表的打印
void ListPrint(ListNode* phead)
{
// 遍历链表
ListNode* pcur = phead->next;
while (pcur != phead)
{
// 打印
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
3.双向链表的尾插
// 双向链表的尾插
void ListPushBack(ListNode* phead, ListDatatype x)
{
// 创建一个存放数据的新节点
ListNode* newnode = ListBuyNode(x);
// 进行尾插
// 新节点连接
newnode->prev = phead->prev;
newnode->next = phead;
// 改变原来链表的连接
phead->prev->next = newnode;
phead->prev = newnode;
}
4.双向链表的头插
void ListPushFront(ListNode* phead, ListDatatype x)
{
// 创建一个存放数据的新节点
ListNode* newnode = ListBuyNode(x);
// 进行头插
// 新节点连接
newnode->prev = phead;
newnode->next = phead->next;
// 改变原来链表的连接
phead->next->prev = newnode;
phead->next = newnode;
}
5.双向链表的尾删
void ListPopBack(ListNode* phead)
{
assert(phead && phead->next != phead);
// 进行尾删除
ListNode* del = phead->prev;
del->prev->next = del->next;
del->next->prev = del->prev;
// 释放空间
free(del);
del = NULL;
}
6.双向链表的头删
void ListPopFront(ListNode* phead)
{
assert(phead && phead->next != phead);
// 进行头删除
ListNode* del = phead->next;
del->next->prev = phead;
phead->next = del->next;
// 释放空间
free(del);
del = NULL;
}
7.双向链表的查找
ListNode* ListFind(ListNode* phead, ListDatatype x)
{
// 遍历双向链表
ListNode* pcur = phead->next;
while (pcur != phead)
{
// 打印
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
// 没有找到
return NULL;
}
8.双向链表在pos位置之后插入
void ListInsret(ListNode* pos, ListDatatype x)
{
assert(pos);
// 创建一个存放数据的新节点
ListNode* newnode = ListBuyNode(x);
// 插入
// 新节点连接
newnode->prev = pos;
newnode->next = pos->next;
// 原链表连接
pos->next->prev = newnode;
pos->next = newnode;
}
9.双向链表删除pos节点
void ListErase(ListNode* pos)
{
//pos理论上来说不能为phead,但是没有参数phead,无法增加校验
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}
10.双向链表的销毁
void ListDesTroy(ListNode* phead)
{
assert(phead);
// 遍历删除
ListNode* pcur = phead->next;
while (pcur != phead)
{
ListNode* next = pcur->next;
free(pcur);
pcur = next;
}
//此时pcur指向phead,而phead还没有被销毁
free(phead);
phead = NULL;
printf("销毁成功!");
}
测试文件:
#include "List.h"
void ListNodetext()
{
ListNode* plist;
ListInit(&plist);
// 测试尾插
ListPushBack(plist, 1);
/*ListPrint(plist);*/
ListPushBack(plist, 2);
/*ListPrint(plist);*/
ListPushBack(plist, 3);
ListPrint(plist); // 1->2->3->
// 测试头插
//ListPushFront(plist, 6);
//ListPrint(plist);
//ListPushFront(plist, 7);
//ListPrint(plist);
//ListPushFront(plist, 8);
//ListPrint(plist);
// 测试尾删
//ListPopBack(plist);
//ListPrint(plist);
//ListPopBack(plist);
//ListPrint(plist);
//ListPopBack(plist);
//ListPrint(plist);
// 测试头删
//ListPopFront(plist);
//ListPrint(plist);
//ListPopFront(plist);
//ListPrint(plist);
//ListPopFront(plist);
//ListPrint(plist);
// 测试查找
//ListNode* find = ListFind(plist, 30);
//if (find == NULL)
//{
// printf("没有找到!");
//}
//else
//{
// printf("找到了!");
//}
// 测试pos位置之后插入
//ListNode* find = ListFind(plist, 2);
//ListInsret(find, 5);
//ListPrint(plist);
// 测试删除pos节点
//ListNode* find = ListFind(plist, 3);
//ListErase(find);
//find = NULL;
//ListPrint(plist);
ListDesTroy(plist);
plist = NULL;
}
int main()
{
ListNodetext();
return 0;
}