C语言双向链表：详解创建、插入、删除及正反向遍历74

链表是一种常用的数据结构，它通过指针将一系列数据节点连接起来。与数组不同，链表的内存空间可以动态分配，因此更灵活地处理动态数据。双向链表是链表的一种改进，每个节点不仅包含指向下一个节点的指针，还包含指向前一个节点的指针，这使得双向链表可以进行正向和反向遍历，从而提高了数据访问的效率。

本文将详细讲解C语言中双向链表的实现，包括创建、插入、删除以及正反向遍历等核心操作。我们将通过清晰的代码示例和详细的注释，帮助读者深入理解双向链表的工作原理和使用方法。

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

首先，我们需要定义双向链表节点的结构体。每个节点包含三个成员：数据域data，前驱指针prev和后继指针next。```c
typedef struct Node {
int data; // 数据域
struct Node *prev; // 指向前一个节点的指针
struct Node *next; // 指向下一个节点的指针
} Node;
```

2. 双向链表的创建

创建一个双向链表，需要先创建一个头节点（head），作为链表的起始节点。头节点通常不存储实际数据，主要用于简化链表的操作。```c
Node* createList() {
Node* head = (Node*)malloc(sizeof(Node));
if (head == NULL) {
printf("内存分配失败!");
return NULL;
}
head->prev = head->next = head; // 头节点的前驱和后继都指向自身
return head;
}
```

3. 在双向链表中插入节点

插入节点操作包括在链表头部插入、在链表尾部插入和在指定节点之后插入。```c
// 在头部插入节点
void insertHead(Node* head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = head->next;
newNode->prev = head;
head->next->prev = newNode;
head->next = newNode;
}
// 在尾部插入节点
void insertTail(Node* head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = head;
newNode->prev = head->prev;
head->prev->next = newNode;
head->prev = newNode;
}
// 在指定节点之后插入节点
void insertAfter(Node* node, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = node->next;
newNode->prev = node;
node->next->prev = newNode;
node->next = newNode;
}
```

4. 从双向链表中删除节点

删除节点操作包括删除头部节点、删除尾部节点和删除指定节点。```c
// 删除头部节点
void deleteHead(Node* head) {
if (head->next == head) return; // 链表为空
Node* temp = head->next;
head->next = temp->next;
temp->next->prev = head;
free(temp);
}
// 删除尾部节点
void deleteTail(Node* head) {
if (head->next == head) return; // 链表为空
Node* temp = head->prev;
head->prev = temp->prev;
temp->prev->next = head;
free(temp);
}
// 删除指定节点
void deleteNode(Node* node) {
if (node == NULL || node->next == node) return; // 节点不存在或链表为空
node->prev->next = node->next;
node->next->prev = node->prev;
free(node);
}
```

5. 双向链表的正向和反向遍历

双向链表的优势在于可以正向和反向遍历。```c
// 正向遍历
void traverseForward(Node* head) {
Node* p = head->next;
while (p != head) {
printf("%d ", p->data);
p = p->next;
}
printf("");
}
// 反向遍历
void traverseBackward(Node* head) {
Node* p = head->prev;
while (p != head) {
printf("%d ", p->data);
p = p->prev;
}
printf("");
}
```

6. 完整示例

以下是一个完整的示例，展示了双向链表的创建、插入、删除和遍历操作：```c
#include
#include
// ... (Node结构体定义和函数实现，如上所示) ...
int main() {
Node* head = createList();
insertHead(head, 10);
insertTail(head, 20);
insertAfter(head->next, 15);
printf("正向遍历: ");
traverseForward(head);
printf("反向遍历: ");
traverseBackward(head);
deleteHead(head);
deleteTail(head);
printf("删除头尾节点后，正向遍历: ");
traverseForward(head);
// ... (添加更多测试代码) ...
return 0;
}
```