双向链表的C语言实现
双向链表是一种链表数据结构,其中每个节点不仅包含指向下一个节点的指针,还包含指向前一个节点的指针。以下是使用 C 语言实现双向链表的基本结构和操作:
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
} Node;
// 创建新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
// 将节点插入到链表的头部
void insertAtHead(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
newNode->next = *head;
(*head)->prev = newNode;
*head = newNode;
}
}
// 将节点插入到链表的尾部
void insertAtTail(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
Node* current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
}
}
// 从链表中删除节点
void deleteNode(Node** head, int key) {
Node* current = *head;
while (current != NULL && current->data != key) {
current = current->next;
}
if (current == NULL) {
printf("Node with data %d not found.\n", key);
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) {
Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// 释放链表
void freeList(Node* head) {
Node* current = head;
while (current != NULL) {
Node* next = current->next;
free(current);
current = next;
}
}
int main() {
Node* head = NULL;
insertAtTail(&head, 10);
insertAtTail(&head, 20);
insertAtTail(&head, 30);
printList(head); // 输出: 10 20 30
insertAtHead(&head, 5);
printList(head); // 输出: 5 10 20 30
deleteNode(&head, 20);
printList(head); // 输出: 5 10 30
freeList(head);
return 0;
}
说明
createNode
: 创建一个新节点,并将其next
和prev
指针初始化为NULL
。insertAtHead
: 将新节点插入到链表的开头。insertAtTail
: 将新节点插入到链表的末尾。deleteNode
: 从链表中删除包含指定数据的节点(如果存在)。printList
: 打印链表中的所有节点数据。freeList
: 释放链表以避免内存泄漏。
这种基本实现允许你在链表的开头或结尾插入节点,并删除指定节点。