C语言双相循环链表增删查改（带头节点）
最后一个节点的 next 指针指向第一个节点，第一个节点的 prev 指针指向最后一个节点
定义链表节点
#include <stdio.h>
#include <stdlib.h> // 内存管理，malloc(size_t size)
// 链表节点结构体
typedef struct Node{
int data;
struct Node* next;
struct Node* prev;
}Node;
定义双向循环链表
typedef struct{
Node* head; // 头节点，虚拟节点
}DouCirLinkedList;
创建新节点
Node* createNewNode(int newData){
Node* newNode = (Node*)malloc(sizeof(Node));
if(newNode == NULL){
printf("Memory allocation failed!\n");
}
newNode->data = newData;
newNode->next = newNode; // 循环链表，初始化指向自己
newNode->prev = newNode;
return newNode;
}
创建带头节点空双向循环链表并初始化
DouCirLinkedList* initList(){
DouCirLinkedList* list = (DouCirLinkedList*)malloc(sizeof(DouCirLinkedList));
list->head = createNewNode(0); // 创建头节点
return list;
}
头插节点
void insertAtHead(DouCirLinkedList* list, int newData){
Node* newNode = createNewNode(newData);
// 新节点的next指针指向原来第一个节点
newNode->next = list->head->next;
// 新节点的prev指针指向头节点
newNode->prev = list->head;
// 更新原来第一个节点的prev指针指向新节点
list->head->next->prev = newNode;
// 更新头节点的next指针指向新节点
list->head->next = newNode;
}
尾插节点
void insertAtTail(DouCirLinkedList* list, int newData){
Node* newNode = createNewNode(newData);
// 找到链表最后一个节点，循环链表很方便
Node* tail = list->head->prev;
// 更新新节点的prev指针指向原来最后一个节点
newNode->prev = tail;
// 跟新新节点的next指针指向头节点
newNode->next = list->head;
// 更新原来最后一个节点的next指针指向新节点
tail->next = newNode;
// 更新头节点的prev指针指向新节点
list->head->prev = newNode;
}
头删节点
void headDelete(DouCirLinkedList* list){
// 循环链表为空
if(list->head->next == list->head){
return;
}
// 头节点后第一个节点
Node* temp = list->head->next;
// 如果链表只有一个节点
if(temp->next == temp){
list->head->next = list->head;
list->head->prev = list->head;
}
else{
// 更新头节点的next指针指向第二个节点
list->head->next = temp->next;
// 更新第二个节点的prev指针指向头节点
temp->next->prev = list->head;
}
}
尾删节点
void tailDelete(DouLinkedList* list){
// 链表为空，只有头节点
if(list->head->next == list->head){
return;
}
// 保存获取链表最后一个节点
Node* tail = list->head->prev;
// 更新倒数第二个节点的next指针
tail->prev->next = list->head;
// 更新第一个节点的prev指针
list->head->prev = tail->prev;
// 释放尾节点
free(tail);
}
查找值为x的节点
Node* searchNode(DouCirLinkedList* list, int x){
// 从头节点的下一个节点开始遍历
Node* cur = list->head->next;
while(cur != list->head){ // 循环直到回到头节点
if(cur->data == x){
return cur; // 返回节点
}
cur = cur->next;
}
return NULL; // 未找到节点，返回NULL
}
修改指定值的节点
int modifyNode(DouCirLinkedList* list, int oldValue, int newValue){
// 从头节点的下一个节点开始遍历
Node* cur = list->head->next;
while(cur != list->head){ // 循环直到回到头节点
if(cur->data = oldValue){
cur->data = newValue; // 修改数据
return 1; // 修改成功返回1
}
cur = cur->next;
}
return 0; // 没有找到返回0
}
在ptr指针前插入新节点
void insertAtPtr(DouCirLinkedList* list, Node* ptr, int newData){
if(ptr == NULL || list == NULL){
return;
}
// 创建新节点
Node* newNode = createNewNode(newData);
// 更新新节点的next指针
newNode->next = ptr;
// 更新新节点的prev指针
newNode->prev = ptr->prev;
// 更新ptr前一个节点的next指针指向新节点
ptr->prev->next = newNode;
// 更新ptr指针的prev指针指向新节点
ptr->prev = newNode;
}
删除ptr指针指向的节点
void deletePtr(DouCirLinkedList* list, Node* ptr){
if(ptr == list->head || ptr == NULL){
return; // 如果ptr为空或是头节点，则直接返回
}
// 更新ptr前一个节点的next指针
ptr->prev->next = ptr->next;
// 更新ptr后一个节点的prev指针
ptr->next->prev = ptr->prev;
free(ptr);
}
打印链表
void printList(DouCirLinkedList* list){
if(list->head->next == list->head){
return;
}
Node* cur = list->head->next;
while(cur != list->head){ // 遍历链表直到回到头节点
printf("%d <-> ", cur->data);
cur = cur->next;
}
printf("\n");
}
销毁链表
void destroyList(DouCirLinkedList* list){
if(list->head->next == list->head){
return;
}
Node* cur = list->head;
Node* temp;
while(cur != list->head){ // 遍历链表直到回到头节点
temp = cur;
cur = cur->next;
free(temp);
}
free(list->head);
free(list);
}