双向链表的实现（详解）

前言

链表的分类： 带头 不带头 单向 双向 循环 不循环
一共有 (2 * 2 * 2) 种链表

带头指的是：带有哨兵位节点
哨兵位（头结点）：可以放随机数据，哨兵位指向的下一个节点就是我们的第一个有效节点，我们指的头节点是哨兵位

单向：指针只能从前向后遍历
双向：指针既可以从前向后遍历又可以从后向前遍历
循环：可以通过尾节点找到头节点，从而达到循环

主要使用的链表是单链表和双向链表
单链表:不带头单向不循环
双向链表：带头双向循环

初始化

ListNode* TLInit()
{ListNode* phead = ListByNode(-1);//ListByNode后面会介绍//为头节点开辟一个空间，并将头结点指向的值赋值为-1return phead;//将开辟出的头节点返回我们的主函数，主函数中的头节点就知道我们有一个哨兵位了
}

//初始化
void TLInit(ListNode** pphead)
{//给双向链表创建一个哨兵位*pphead = ListByNode(-1);
}

初始化有两种写法，第二种写法也是可行的，但是用第一种，可以使得接口一致，都是一级指针，使用者也会更方便的使用，不用去记忆那个要用一级指针还是二级指针

双向链表的结构

//定义双向链表的结构
typedef int DataType;
typedef struct ListNode//双向链表
{DataType x;//双向链表中的数据struct ListNode* next;//指向后一个节点，后继指针struct ListNode* prev;//指向前一个节点，前驱指针
}ListNode;

为双向链表的节点开辟空间

ListNode* ListByNode(DataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL){perror("malloc");return NULL;}//开辟成功node->next = node->prev = node;//初始化一个哨兵位的下一个节点和前一个节点指向的是自己node->x = x;return node;
}

头插

//头插
//在第一个有效节点之前插入一个节点
void TLPushFront(ListNode* phead,DataType x)
//用一级指针为了不改变原链表的哨兵位
{assert(phead);//断言一下是不是空链表ListNode* newnode = ListByNode(x);ListNode* pcur = phead->next;newnode->next = pcur;newnode->prev = phead;pcur->prev = newnode;phead->next = newnode;}

尾插

//尾插
//在头节点之后或者之前插入
//因为在哨兵位前，哨兵位的prev指向尾结点，尾结点的next指向哨兵位
void TLPushBack(ListNode* phead,DataType x)
{assert(phead);//链表不为空ListNode* newnode = ListByNode(x);//为尾插的节点开辟空间ListNode* pcur = phead->prev; newnode->next = phead;newnode->prev = pcur;pcur->next = newnode;phead->prev = newnode;
}

打印链表

//打印链表
void TLPrint(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->x);pcur = pcur->next;}printf("\n");
}

尾删

//尾删
//注意哨兵位不能被删除，所以理论上至少有一个节点，才能够删除
void TLPopBack(ListNode* phead)
{assert(phead&&phead->next!=phead);ListNode* pcur = phead->prev;ListNode* del = pcur->prev;del->next = phead;phead->prev = del;free(pcur);pcur = NULL;}

头删

//头删
//注意哨兵位不能被删除，所以理论上至少有一个节点，才能够删除
void TLPopFront(ListNode* phead)
{assert(phead&&phead->next!=phead);//phead不能为空ListNode* pcur = phead->next;pcur->next->prev = phead;phead->next = pcur->next;free(pcur);pcur = NULL;}

查找

//查找 x 数据的位置并返回
ListNode* SLFind(DataType x,ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){if (pcur->x == x){return pcur;//找到了}pcur = pcur->next;}return NULL;//找不到了
}

指定位置之后的插入

//指定位置之后的插入
//知道了pos节点，就知道了pos之前的数和之后的数
//指定位置之后的插入和指定位置之前的插入是一样的
void TLInsert(ListNode* pos,DataType x)
{assert(pos);//插入的pos位置不能为空ListNode* newnode = ListByNode(x);//为插入的数据开辟空间ListNode* pcur = pos->next;newnode->next = pcur;newnode->prev = pos;pos->next = newnode;pcur->prev = newnode;}

删除pos节点

//删除pos节点
void Erase(ListNode* pos)
{assert(pos);//理论上pos不能为phead,因为phead不能被删除，它是双向链表pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;}

销毁双向链表

//销毁双向链表
void LTDestroy(ListNode* phead)
{assert(phead);//phead不为空，才销毁，为空，不用销毁//销毁时phead也要释放(销毁)ListNode* pcur = phead->next;ListNode* next = pcur->next;while (pcur != phead){next = pcur->next;free(pcur);pcur = next;}//出来后pcur指向pheadfree(phead);phead = NULL;
}