双向链表是一种链式数据结构，每个节点都包含一个数据域和两个指针域：一个指向前一个节点，另一个指向后一个节点。与单向链表相比，双向链表可以在两个方向上进行遍历，因而操作更加灵活。
双向链表的结构
在C语言中，双向链表的节点结构通常定义如下：
#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("内存分配失败\n");exit(1);}newNode->data = data;newNode->prev = NULL;newNode->next = NULL;return newNode;
}
插入节点
以下是一些常见的插入操作，包括在链表头部、尾部插入节点，以及在指定位置插入节点。
1. 头部插入
void insertAtHead(Node** head, int data) {Node* newNode = createNode(data);newNode->next = *head;if (*head != NULL) {(*head)->prev = newNode;}*head = newNode;
}
2. 尾部插入
void insertAtTail(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;return;}Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;newNode->prev = temp;
}
3. 指定位置插入
在指定位置插入节点（例如在第n个节点后面）：
void insertAfter(Node* prevNode, int data) {if (prevNode == NULL) {printf("前置节点不能为空\n");return;}Node* newNode = createNode(data);newNode->next = prevNode->next;prevNode->next = newNode;newNode->prev = prevNode;if (newNode->next != NULL) {newNode->next->prev = newNode;}
}
删除节点
删除双向链表中的节点时，需要更新前后节点的指针。
void deleteNode(Node** head, Node* delNode) {if (*head == NULL || delNode == NULL) return;if (*head == delNode) {*head = delNode->next;}if (delNode->next != NULL) {delNode->next->prev = delNode->prev;}if (delNode->prev != NULL) {delNode->prev->next = delNode->next;}free(delNode);
}
遍历双向链表
从头到尾遍历
void printList(Node* head) {Node* temp = head;printf("正向遍历: ");while (temp != NULL) {printf("%d ", temp->data);temp = temp->next;}printf("\n");
}
从尾到头遍历
void printListReverse(Node* head) {if (head == NULL) return;Node* temp = head;while (temp->next != NULL) {temp = temp->next;}printf("逆向遍历: ");while (temp != NULL) {printf("%d ", temp->data);temp = temp->prev;}printf("\n");
}
示例程序
以下是一个完整的C语言双向链表示例，包含创建、插入、删除和遍历等功能：
int main() {Node* head = NULL;// 插入数据insertAtHead(&head, 10);insertAtHead(&head, 20);insertAtTail(&head, 5);insertAfter(head, 15);// 打印链表printList(head);printListReverse(head);// 删除节点deleteNode(&head, head->next); // 删除第二个节点printList(head);return 0;
}
运行结果
假设输入为上述代码，则输出结果类似于：
正向遍历: 20 10 15 5
逆向遍历: 5 15 10 20
正向遍历: 20 15 5
总结
双向链表在某些场景下比单向链表更灵活，尤其是在需要双向遍历或删除任意节点的情况下。
