C语言实现双向链表：详解及代码示例318

双向链表是一种常用的数据结构，它允许在链表中的任何位置进行高效的插入和删除操作。与单向链表相比，双向链表增加了指向前驱节点的指针，使得遍历更加灵活。本文将详细介绍如何在C语言中实现双向链表，并提供完整的代码示例，涵盖创建、插入、删除、查找、打印等核心功能。

1. 数据结构定义

首先，我们需要定义双向链表节点的数据结构。每个节点包含数据域和两个指针域：一个指向下一个节点（next），一个指向前一个节点（prev）。```c
#include
#include
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
```

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

2. 创建双向链表

创建一个双向链表需要创建一个头节点（head），它不存储实际数据，主要用于链表操作的方便性。初始状态下，头节点的 `next` 和 `prev` 指针都指向 `NULL`。```c
Node* createList() {
Node* head = (Node*)malloc(sizeof(Node));
if (head == NULL) {
perror("Memory allocation failed");
exit(1);
}
head->next = NULL;
head->prev = NULL;
return head;
}
```

函数 `createList` 分配内存空间给头节点，并初始化其指针。如果内存分配失败，则打印错误信息并退出。

3. 在链表尾部插入节点

在链表尾部插入节点是最简单的插入操作。我们需要遍历链表找到最后一个节点，然后将新节点插入到最后一个节点之后。```c
void insertAtEnd(Node* head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
perror("Memory allocation failed");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
Node* current = head;
while (current->next != NULL) {
current = current->next;
}
newNode->prev = current;
current->next = newNode;
}
```

函数 `insertAtEnd` 创建一个新节点，将数据赋值给新节点，然后遍历链表找到尾节点，并将新节点插入到尾节点之后。 注意要正确设置新节点的前驱和后继指针。

4. 在链表头部插入节点

在链表头部插入节点比尾部插入更为高效，因为它不需要遍历链表。```c
void insertAtBeginning(Node* head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
perror("Memory allocation failed");
exit(1);
}
newNode->data = data;
newNode->next = head->next;
newNode->prev = head;
if (head->next != NULL) {
head->next->prev = newNode;
}
head->next = newNode;
}
```

函数 `insertAtBeginning` 创建一个新节点，并将新节点插入到头节点之后。

5. 删除节点

删除节点需要找到要删除的节点，然后调整其前驱和后继节点的指针。```c
void deleteNode(Node* head, int data) {
Node* current = head->next;
while (current != NULL) {
if (current->data == data) {
if (current->prev != NULL) {
current->prev->next = current->next;
} else {
head->next = current->next;
}
if (current->next != NULL) {
current->next->prev = current->prev;
}
free(current);
return;
}
current = current->next;
}
printf("Node with data %d not found.", data);
}
```

函数 `deleteNode` 遍历链表，找到要删除的节点，然后更新指针，释放内存。

6. 打印链表

打印链表方便我们查看链表中的数据。```c
void printList(Node* head) {
Node* current = head->next;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("");
}
```

函数 `printList` 遍历链表并打印每个节点的数据。

7. 完整示例代码```c
// ... (previous code) ...
int main() {
Node* head = createList();
insertAtEnd(head, 10);
insertAtEnd(head, 20);
insertAtBeginning(head, 5);
printList(head); // Output: 5 10 20
deleteNode(head, 10);
printList(head); // Output: 5 20
return 0;
}
```

这段代码演示了如何创建、插入、删除和打印双向链表。

8. 内存管理

在使用双向链表时，务必注意内存管理。 在创建和插入节点时要使用 `malloc` 分配内存，并在删除节点时使用 `free` 释放内存，以避免内存泄漏。 良好的内存管理对于程序的稳定性至关重要。

9. 错误处理

在代码中加入错误处理，例如检查 `malloc` 是否成功分配内存，可以提高程序的健壮性。 如果内存分配失败，程序应该优雅地处理错误，而不是崩溃。

本篇文章详细介绍了 C 语言双向链表的实现，并提供了完整的代码示例。 理解双向链表的原理和实现方法对于掌握数据结构和算法至关重要。 希望这篇文章能够帮助你更好地理解和应用双向链表。

2025-04-24

上一篇：C语言换行排序输出详解：算法选择与代码实现

下一篇：C语言实现满屏代码输出的多种方法及性能分析