双向循环链表的原理及应用
双向循环链表的原理及应用
双向循环链表的原理
双向循环链表是一种链式存储结构，每个节点包含两个指针，分别指向前驱节点和后继节点。链表的尾节点指向头节点，头节点指向尾节点，形成闭环。这种结构兼具双向链表和循环链表的特性，支持高效的前后遍历和数据操作。
双向循环链表与双向链表的区别：指的是双向循环链表的首结点中的prev指针成员指向链表的尾结点，并且双向循环链表的尾结点里的next指针成员指向链表的首结点，所以双向循环链表也属于环形结构。
双向循环链表的基本结构
节点结构通常包含三个部分：数据域、前驱指针（prev）和后继指针（next）。前驱指针指向前一个节点，后继指针指向后一个节点。双向循环链表的空链表表现为头节点的前驱和后继均指向自身
双向循环链表相关操作
插入操作分为头插、尾插和中间插入。头插将新节点插入到头节点之后，更新头节点的前驱和后继指针。尾插将新节点插入到尾节点之前，更新尾节点的前驱和后继指针。中间插入需定位插入位置，调整相邻节点的指针。
删除操作分为头删、尾删和中间删除。头删删除头节点的后继节点，更新头节点的后继指针。尾删删除尾节点的前驱节点，更新尾节点的前驱指针。中间删除需定位删除节点，调整相邻节点的指针。
遍历操作支持双向遍历。从头节点出发，沿后继指针遍历至尾节点，再回到头节点。从尾节点出发，沿前驱指针遍历至头节点，再回到尾节点。
由于带头结点更加方便用户进行数据访问，所以本次创建一条带头结点的双向循环的链表
typedef int DataType_t;
//构造双向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleLinkedList
{
DataType_t data; //结点的数据域
struct DoubleLinkedList *prev; //直接前驱的指针域
struct DoubleLinkedList *next; //直接后继的指针域
}DoubleLList_t;(1) 创建一个空链表，由于是使用头结点，所以就需要申请头结点的堆内存并初始化即可
//创建一个空双向循环链表，空链表应该有一个头结点，对链表进行初始化
DoubleLList_t * DoubleCirLList_Create(void)
{
//1.创建一个头结点并对头结点申请内存
DoubleLList_t *Head = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
//2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身即可，体现“循环”
Head->prev = Head;
Head->next = Head;
//3.把头结点的地址返回即可
return Head;
}(2) 创建新结点，为新结点申请堆内存并对新结点的数据域和指针域进行初始化
//创建新的结点，并对新结点进行初始化（数据域 + 指针域）
DoubleLList_t * DoubleCirLList_NewNode(DataType_t data)
{
//1.创建一个新结点并对新结点申请内存
DoubleLList_t *New = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
if (NULL == New)
{
perror("Calloc memory for NewNode is Failed");
return NULL;
}
//2.对新结点的数据域和指针域（2个）进行初始化,指针域指向结点自身，体现“循环”
New->data = data;
New->prev = New;
New->next = New;
return New;
}(3) 根据情况可以从链表中插入新结点，此时可以分为尾部插入、头部插入、指定位置插入
头插
尾插
指定位置插入
(4) 根据情况可以从链表中删除某结点，此时可以分为尾部删除、头部删除、指定结点删除：
头删
尾删
指定位置删除
下面是几道笔试题：
双向循环链表的节点结构应包含哪些成员变量？
A. data，next，prev B. data，next C. data，prev D. data
正确答案：A. data，next，prev
在双向循环链表中，如何在链表尾部插入一个新节点？
A. 将新节点的next指针指向链表头节点，将链表尾节点的next指针指向新节点
B. 将新节点的next指针指向NULL，将链表尾节点的next指针指向新节点
C. 将新节点的prev指针指向链表头节点，将链表尾节点的next指针指向新节点
D. 将新节点的prev指针指向NULL，将链表尾节点的next指针指向新节点
正确答案：B. 将新节点的next指针指向NULL，将链表尾节点的next指针指向新节点
对于一个双向循环链表，如何在指定位置插入一个新节点？
A. 修改前一个节点的next指针和后一个节点的prev指针
B. 修改当前节点的next指针和prev指针
C. 直接修改指定位置节点的指针即可
D. 无法在双向循环链表中指定位置插入新节点
正确答案：A. 修改前一个节点的next指针和后一个节点的prev指针
问题：请编写一个函数，将一个新节点插入到双向循环链表的指定位置之后。
答案：
void insertAfter(Node* currentNode, int newData) {
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->data = newData;
newNode->next = currentNode->next;
newNode->prev = currentNode;
currentNode->next->prev = newNode;
currentNode->next = newNode;
}问题：编写一个函数，实现删除双向循环链表中指定节点的功能。
答案：
void deleteNode(Node* targetNode) {
targetNode->prev->next = targetNode->next;
targetNode->next->prev = targetNode->prev;
free(targetNode);
}问题：请写出一个函数，打印输出整个双向循环链表的所有节点数据。
答案：
void printList(Node* head) {
Node* current = head;
do {
printf("%d ", current->data);
current = current->next;
} while(current != head);
}腾讯云开发者
