数据结构——双向链表

🌷0. 前言

• 前面我们已经介绍了单向链表的相关知识（具体参考这篇文章：数据结构——单链表）
• 单链表头插头删效率十分的高，但是要在中间或者尾部进行插入删除操作时，需要找到前驱节点，而且单链表难以逆序，这导致单链表具有一定的局限性。
• 为了克服这单向性的缺点，我们的前辈们设计出了双向链表。本文讲解的是带头双向循环链表。

🌻1. 带头双向循环链表概念

🪂1.1 双向循环

双向循环链表是在单链表的每个节点中，再设置一个指向其全区节点的指针域，在链表的尾部指向头部，形成一个环状结构。

双向链表具有两个指针域：

1. next指向直接后继
2. prev指向直接前驱

🪂1.2 带头节点

链表的头部放置一个哨兵位，不存储数据，用于指向链表的第一个实际存储数据的节点。

带头结点的好处：
没有带头的情况下，在对链表进行插入删除等操作时，需要对头节点进行判断。而带头结点的情况下，可以将所以链表操作都一视同仁对待。

🌹2. 接口声明

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;//初始化
LTNode* LTInit();//销毁
void LTDestroy(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);//pos位置之前插入
void LTInsert(LTNode* pos,LTDataType x);//pos位置删除
void LTErase(LTNode* pos);//打印
void LTPrint(LTNode* phead);//判空
bool LTEmpty(LTNode* phead);

🌼3. 接口实现

💫3.1 节点申请

//"买"节点
LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail");exit(-1);}node->data = x;node->next = NULL;node->prev = NULL;return node;
}

💫3.2 初始化与销毁

//初始化
LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}//销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

tips：

• 我们之前写过单向链表，没有写初始化函数，因为结构较简单，所以我们手动将头节点置为NULL，不需要显式地进行初始化，只需要创建第一个节点并将其指针设置为NULL即可。
• 对于双向带头循环链表，需先创建头节点，并将前驱指针和后继指针都指向自身，确保链表的循环性，所以我们写一个初始化函数，显式初始化。

💫3.3 链表判空

在进行删除操作的时候，空链表是不能删除的，所以我们写一个函数来对链表是否为空来进行判断：

//判空
bool LTEmpty(LTNode* phead)
{return phead->next == phead;
}

💫3.4 尾插与尾删

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;tailPrev->next = phead;phead->prev = tailPrev;free(tail);tail = NULL；
}

💫3.5 头插与头删

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* first = phead->next;newnode->next = first;first->prev = newnode;phead->next = newnode;newnode->prev = phead;//这里未保存头节点，需按顺序操作/*newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;*/
}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* first = phead->next;phead->next = first->next;first->next->prev = first->prev;free(first);first = NULL;
}

💫3.6 查找

查找也代表这修改，如果能找到某个节点的位置，那么就可以将其节点内容修改。

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}

💫3.7 指定位置插入与删除

//pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = BuyListNode(x);newnode->next = pos;pos->prev = newnode;newnode->prev = posPrev;posPrev->next = newnode;
}//pos位置删除
void LTErase(LTNode* pos)
{assert(pos);LTNode* del = pos;LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;posPrev->next = pos->next;posNext->prev = pos->prev;free(del);del = NULL;
}

其实有了指定位置的插入和删除，那么我们的头插尾插、头删尾删里面的内容都能复用该功能：

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTInsert(phead, x);
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->prev);
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTInsert(phead->next, x);
}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->next);
}

🌾4. 接口测试

#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:6031)
#include"List.h"void TestList1()
{//初始化LTNode* plist = LTInit();//尾插测试LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPushBack(plist, 5);LTPrint(plist);//尾删测试//LTPopBack(plist);//LTPopBack(plist);//LTPopBack(plist);//LTPopBack(plist);//LTPopBack(plist);//LTPrint(plist);//头插测试//LTPushFront(plist, 1);//LTPushFront(plist, 2);//LTPushFront(plist, 3);//LTPushFront(plist, 4);//LTPushFront(plist, 5);//LTPushFront(plist, 6);//LTPushFront(plist, 7);//LTPrint(plist);//头删测试//LTPopFront(plist);//LTPopFront(plist);//LTPopFront(plist);//LTPrint(plist);//查找测试LTNode* pos = LTFind(plist, 3);printf("%d\\n", pos->data);//pos位置之前插入测试LTInsert(pos, 9);LTPrint(plist);//pos位置删除测试LTErase(pos);pos = NULL;LTPrint(plist);//销毁测试LTDestroy(plist);plist = NULL;
}int main()
{TestList1();return 0;
}

剑虹评论网