数据结构之双向链表

链表的结构有很多。

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向带头循环链表。

1.带头双向循环链表的结构

这里的（head）头结点，即“哨兵位”，它不存储任何有效元素，只是站在这里。它在后面的操作中也不会移动。

2.实现双向链表

双向，顾名思义，每个结点需要有两个指针来存储前一个与后一个结点的地址。

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next; //指针保存下⼀个结点的地址struct ListNode* prev; //指针保存前⼀个结点的地址LTDataType data;
}LTNode;

2.1双向链表的初始化

与单链表的初始化相似。但不同的是我们需要将这个结点中的两个指针指向自己，以实现”循环“这个表述。

//初始化
void LTInit(LTNode** pphead) {*pphead = (LTNode*)malloc(sizeof(LTNode));if (*pphead == NULL) {perror("malloc");exit(1);}(*pphead)->data = -1;(*pphead)->next = *pphead;(*pphead)->prev = *pphead;}

但我们会发现这里的操作很像创建一个数据为-1的新结点，那么此时我们可以把创建新结点的代码写出来对照

//创建新节点
LTNode* LTBuyNode(LTDataType x) {LTNode*newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL) {perror("malloc");exit(1);}(newnode)->data = x;(newnode)->next = newnode;(newnode)->prev = newnode;return newnode;
}

所以我们还可以这样初始化。

//初始化
void LTInit(LTNode** pphead) {*pphead = LTBuyNode(-1);
}

极大减少了代码量。

2.2双向链表的尾插

由于每个结点都有指向上一个与后一个结点的指针，所以我们可以直接由头结点找到尾结点进行插入。

//尾插
void LTPushBack(LTNode* phead,LTDataType x) {LTNode* newnode = LTBuyNode(x);LTNode* del = phead->prev;del->next = newnode;newnode->next = phead;newnode->prev = del;phead->prev = newnode;}

2.3双向链表的头插

//头插
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = LTBuyNode(x);LTNode* del = phead->next;del->prev = newnode;newnode->next = del;newnode->prev = phead;phead->next = newnode;
}

先用del指针存储头结点下一个节点，在相连。

2.4双向链表的尾删

//尾删
void LTPopback(LTNode* phead) {assert(!LTEmpty(phead));LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del-> prev;free(del);del = NULL;	
}

2.5双向链表的销毁

//销毁
void LTDestroy(LTNode** pphead) {LTNode* pcur = (*pphead)->next;while (pcur != *pphead) {LTNode* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;
}

与单链表操作相似，设计两个指针，一前一后来销毁结点。
由于尾结点指向头结点，所以我们需要在保留头结点以便退出循环，最后在销毁头结点.
完
如发现错误，欢迎打在评论区。
主页还有更多优质内容OvO