C语言双链表详解：创建、插入、删除及完整代码示例130

双链表是一种常用的数据结构，它允许在任意位置进行高效的插入和删除操作。与单链表相比，双链表每个节点都包含两个指针：一个指向下一个节点（next），另一个指向前一个节点（prev）。这种双向链接使得双链表在数据操作方面具有更大的灵活性。本文将详细讲解C语言中双链表的实现，包括其基本结构、创建、插入、删除等操作，并提供完整的代码示例，帮助读者深入理解和掌握双链表。

1. 双链表节点结构体定义

首先，我们需要定义双链表节点的结构体。每个节点包含数据域和两个指针域，分别指向该节点的下一个节点和前一个节点。一个典型的结构体定义如下：```c
typedef struct Node {
int data; // 数据域，可以根据需要修改数据类型
struct Node *prev; // 指向前一个节点的指针
struct Node *next; // 指向下一个节点的指针
} Node;
```

这里我们使用`int`作为数据域，你可以根据实际需求修改为其他数据类型，例如`char`、`float`、`double`或者自定义结构体。

2. 双链表的创建

创建双链表通常从创建一个头节点开始。头节点不存储实际数据，主要用于简化链表操作，特别是插入和删除操作在链表头部的操作。以下是创建双链表头节点的函数：```c
Node* createList() {
Node* head = (Node*)malloc(sizeof(Node));
if (head == NULL) {
printf("Memory allocation failed!");
exit(1); // 内存分配失败，程序退出
}
head->prev = NULL;
head->next = NULL;
return head;
}
```

这个函数分配一个`Node`类型的内存空间，并将其指针返回。头节点的`prev`和`next`指针都被初始化为`NULL`，表示链表为空。

3. 双链表的插入操作

双链表的插入操作可以分为三种情况：头部插入、尾部插入和指定位置插入。```c
// 头部插入
void insertAtHead(Node* head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = head->next;
newNode->prev = head;
if (head->next != NULL) {
head->next->prev = newNode;
}
head->next = newNode;
}
// 尾部插入
void insertAtTail(Node* head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
Node* current = head;
while (current->next != NULL) {
current = current->next;
}
newNode->prev = current;
current->next = newNode;
}
// 指定位置插入 (在节点p之后插入)
void insertAfter(Node* p, int data) {
if (p == NULL) return; //防止空指针异常
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = p->next;
newNode->prev = p;
if (p->next != NULL) {
p->next->prev = newNode;
}
p->next = newNode;
}
```

4. 双链表的删除操作

类似地，双链表的删除操作也可以分为三种情况：头部删除、尾部删除和指定位置删除。```c
// 头部删除
void deleteAtHead(Node* head) {
if (head->next == NULL) return; // 空链表，不做任何操作
Node* temp = head->next;
head->next = temp->next;
if (temp->next != NULL) {
temp->next->prev = head;
}
free(temp);
}
// 尾部删除
void deleteAtTail(Node* head) {
if (head->next == NULL) return; // 空链表，不做任何操作
Node* current = head;
while (current->next->next != NULL) {
current = current->next;
}
free(current->next);
current->next = NULL;
}
// 指定位置删除
void deleteNode(Node* p) {
if (p == NULL || p->prev == NULL) return; //空指针或删除头节点的情况，直接返回
p->prev->next = p->next;
if (p->next != NULL) {
p->next->prev = p->prev;
}
free(p);
}
```

5. 双链表的遍历输出

遍历双链表并输出其节点数据：```c
void printList(Node* head) {
Node* current = head->next;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("");
}
```

6. 完整的代码示例

将以上所有函数整合到一个完整的程序中：```c
#include
#include
// ... (Node 结构体定义和上述所有函数) ...
int main() {
Node* head = createList();
insertAtHead(head, 10);
insertAtTail(head, 20);
insertAfter(head->next, 15);
printList(head); // 输出: 10 15 20
deleteAtHead(head);
printList(head); // 输出: 15 20
deleteAtTail(head);
printList(head); // 输出: 15
deleteNode(head->next); // 删除15
printList(head); // 输出: (空行)

//释放内存，避免内存泄漏
Node* current = head;
while(current != NULL){
Node* temp = current;
current = current->next;
free(temp);
}
return 0;
}
```