今日学习了双链表的相关操作：
一、创建双链表
创建双链表的第一步是定义节点结构体，它包含数据域、指向前驱节点的指针 prev 和指向后继节点的指针 next。
// 双链表节点结构体定义
typedef struct DoubleListNode {
int data;
struct DoubleListNode *prev;
struct DoubleListNode *next;
} DoubleListNode;
初始化时，将表头指针设为 NULL，此时链表为空。当要逐个添加节点构建链表时，以尾插法为例：
DoubleListNode* createDoubleLinkedList() {
DoubleListNode *head = NULL;
DoubleListNode *tail = NULL;
int value;
scanf("%d", &value); // 输入节点数据，以特定值（如 -1）结束输入
while (value!= -1) {
DoubleListNode *newNode = (DoubleListNode *)malloc(sizeof(DoubleListNode));
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
if (head == NULL) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
scanf("%d", &value);
}
return head;
}
上述代码在添加节点过程中，对于非空链表，新节点的前驱指针指向当前尾节点，尾节点的后继指针指向新节点，然后更新尾节点为新节点，确保链表正确构建。
二、插入节点
头插法：
void insertAtHead(DoubleListNode **head, int value) {
DoubleListNode *newNode = (DoubleListNode )malloc(sizeof(DoubleListNode));
newNode->data = value;
newNode->next = head;
newNode->prev = NULL;
if (head!= NULL) {
(head)->prev = newNode;
}
*head = newNode;
}
先创建新节点，让其后继指向原表头，前驱置空，若原表头非空，原表头前驱指向新节点，最后更新表头指针。
中间插入：假设要在值为 target 的节点后插入新节点。
void insertAfter(DoubleListNode *head, int target, int value) {
DoubleListNode *current = head;
while (current!= NULL && current->data!= target) {
current = current->next;
}
if (current == NULL) {
return; // 未找到目标节点，插入失败
}
DoubleListNode *newNode = (DoubleListNode *)malloc(sizeof(DoubleListNode));
newNode->data = value;
newNode->prev = current;
newNode->next = current->next;
if (current->next!= NULL) {
current->next->prev = newNode;
}
current->next = newNode;
}
先定位目标节点，新节点前驱、后继指针相应连接，若目标节点后有节点，其后继节点前驱指针也需更新。
尾插法：类似创建链表尾插过程，找到尾节点插入即可。
三、删除节点
删除表头节点：
void deleteAtHead(DoubleListNode **head) {
if (*head == NULL) {
return; // 空链表，无需删除
}
DoubleListNode temp = head;
head = (head)->next;
if (head!= NULL) {
(head)->prev = NULL;
}
free(temp);
}
保存表头指针，更新表头，若新表头非空，其前驱置空，释放原表头内存。
删除中间节点：要删除值为 key 的节点。
void deleteNode(DoubleListNode **head, int key) {
if (*head == NULL) {
return; // 空链表
}
DoubleListNode *current = *head;
while (current!= NULL && current->data!= key) {
current = current->next;
}
if (current == NULL) {
return; // 未找到要删除的节点
}
if (current->prev!= NULL) {
current->prev->next = current->next;
} else {
*head = current->next;
}
if (current->next!= NULL) {
current->next->prev = current->prev;
}
free(current);
}
先定位节点，若有前驱、后继，分别调整指针跳过该节点，再释放其内存。
四、遍历双链表
正向遍历：
void printForward(DoubleListNode *head) {
DoubleListNode *current = head;
while (current!= NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
从表头顺着后继指针逐个访问节点输出数据。
反向遍历：
void printBackward(DoubleListNode *head) {
DoubleListNode *tail = head;
while (tail->next!= NULL) {
tail = tail->next;
}
while (tail!= NULL) {
printf("%d ", tail->data);
tail = tail->prev;
}
printf("\n");
}
先找到尾节点，再依着前驱指针回溯输出数据。
这些双链表操作相互配合，为解决复杂的数据处理问题提供了有力手段，熟练掌握它们是运用双链表的关键。