《数据结构笔记四》双链表：创建，插入（头插、尾插、中间任意位置插入），删除，遍历，释放内存等核心操作。
双链表结构：数据域、前驱指针、后继指针；
结构体定义为：
typedef struct Node
{
int data;
struct Node *prev;
struct Node *next;
}Node;
步骤分为：
1. 定义节点结构体。
2. 编写创建节点的函数。
3. 编写头插法函数。
4. 编写尾插法函数。
5. 编写在任意位置插入的函数（比如指定位置索引）。
6. 编写删除节点的函数（按位置或按值）。
7. 编写遍历链表的函数。
8. 编写释放链表的函数。
9. 主函数中测试这些操作。
代码实现：
#include <stdio.h>
#include <stdlib.h>// 定义双链表节点结构
typedef struct Node {int data;struct Node* prev;struct Node* next;
} Node;/*----------- 核心操作函数 -----------*/
// 创建新节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (!newNode) {printf("Memory allocation failed!\n");exit(1);}newNode->data = data;newNode->prev = NULL;newNode->next = NULL;return newNode;
}// 头插法
void insertAtHead(Node** head, int data) {Node* newNode = createNode(data);if (*head != NULL) {newNode->next = *head;(*head)->prev = newNode;}*head = newNode;
}// 尾插法
void insertAtTail(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;return;}Node* current = *head;while (current->next != NULL) {current = current->next;}current->next = newNode;newNode->prev = current;
}// 在指定位置插入（从0开始计数）
void insertAtPosition(Node** head, int pos, int data) {if (pos < 0) {printf("Invalid position!\n");return;}// 头插特殊情况处理if (pos == 0) {insertAtHead(head, data);return;}Node* newNode = createNode(data);Node* current = *head;// 定位到插入位置的前一个节点for (int i = 0; i < pos-1 && current != NULL; i++) {current = current->next;}if (current == NULL) {printf("Position exceeds list length!\n");free(newNode);return;}// 调整指针关系newNode->next = current->next;newNode->prev = current;if (current->next != NULL) {current->next->prev = newNode;}current->next = newNode;
}// 删除指定位置的节点
void deleteAtPosition(Node** head, int pos) {if (*head == NULL || pos < 0) {printf("List is empty or invalid position!\n");return;}Node* current = *head;// 定位到要删除的节点for (int i = 0; i < pos && current != NULL; i++) {current = current->next;}if (current == NULL) {printf("Position exceeds list length!\n");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 printList(Node* head) {printf("Forward: ");Node* current = head;while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");// 反向遍历验证if (head == NULL) return;printf("Backward: ");current = head;while (current->next != NULL) {current = current->next;}while (current != NULL) {printf("%d -> ", current->data);current = current->prev;}printf("NULL\n\n");
}// 释放整个链表内存
void freeList(Node** head) {Node* current = *head;while (current != NULL) {Node* temp = current;current = current->next;free(temp);}*head = NULL;
}/*----------- 测试用例 -----------*/
int main() {Node* head = NULL;// 创建并操作链表insertAtTail(&head, 10); // 尾插10insertAtHead(&head, 5); // 头插5insertAtPosition(&head, 1, 7); // 在位置1插入7insertAtPosition(&head, 3, 20); // 在位置3插入20printList(head); // 预期：5 -> 7 -> 10 -> 20deleteAtPosition(&head, 2); // 删除位置2（值10）deleteAtPosition(&head, 0); // 删除头节点（值5）printList(head); // 预期：7 -> 20freeList(&head); // 释放内存return 0;
}代码说明：
完整功能实现：
createNode：动态创建新节点
insertAtHead/insertAtTail：头插/尾插操作
insertAtPosition：支持任意位置插入
deleteAtPosition：支持任意位置删除
printList：双向遍历验证链表结构
freeList：完全释放内存避免泄漏边界处理：
处理空链表插入/删除操作
验证无效位置输入（负数、超长位置）
双向指针调整确保链表完整性
内存管理：
每个动态分配的节点都会被正确释放
删除操作后立即释放对应内存
验证方式：
正向/反向双重遍历验证指针正确性
测试用例覆盖头/尾/中间操作场景
运行该程序时，可以通过双向打印验证链表结构的正确性，同时所有内存操作都经过安全处理，避免常见的内存泄漏问题。