C语言：链表

链表是一种常见的线性数据结构，其中每个元素（称为节点）包含两部分：数据和指向下一个节点的指针。链表的主要优点是插入和删除操作的时间复杂度较低，但随机访问的效率不如数组。

1. 链表的基本概念

节点（Node）：链表的基本单元，包含数据和指向下一个节点的指针。
头节点（Head）：链表的第一个节点。
尾节点（Tail）：链表的最后一个节点，其指针通常为 NULL。
空链表：没有节点的链表，头节点指针为 NULL。

链表是一种常见的数据结构，它由一系列节点组成。每个节点包含两部分：数据部分和指针部分。数据部分用于存储数据，指针部分用于指向下一个节点，从而将各个节点连接起来。链表可以动态地分配内存，方便地进行插入和删除操作。

2. 链表的操作

常见的链表操作包括：

插入：在链表的某个位置插入一个新节点。
删除：从链表中删除一个节点。
查找：在链表中查找一个节点。
遍历：遍历链表中的所有节点。

3. 实例

下面是一个用C语言实现单向链表的示例：

#include <stdio.h>
#include <stdlib.h>// 定义节点结构
typedef struct Node {int data;struct Node* next;
} Node;// 创建新节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("Memory allocation failed\n");exit(1);}newNode->data = data;newNode->next = NULL;return newNode;
}// 在链表头部插入节点
void insertAtHead(Node** head, int data) {Node* newNode = createNode(data);newNode->next = *head;*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;}
}// 删除链表中的节点
void deleteNode(Node** head, int data) {if (*head == NULL) {printf("List is empty\n");return;}if ((*head)->data == data) {Node* temp = *head;*head = (*head)->next;free(temp);return;}Node* current = *head;while (current->next != NULL && current->next->data != data) {current = current->next;}if (current->next == NULL) {printf("Node with value %d not found\n", data);return;}Node* temp = current->next;current->next = current->next->next;free(temp);
}// 查找链表中的节点
Node* search(Node* head, int data) {Node* current = head;while (current != NULL) {if (current->data == data) {return current;}current = current->next;}return NULL;
}// 遍历链表并打印所有节点
void printList(Node* head) {Node* current = head;while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");
}// 清空链表
void clearList(Node** head) {Node* current = *head;while (current != NULL) {Node* temp = current;current = current->next;free(temp);}*head = NULL;
}int main() {Node* head = NULL;insertAtHead(&head, 10);insertAtHead(&head, 20);insertAtTail(&head, 30);printList(head);  // 输出: 20 -> 10 -> 30 -> NULLdeleteNode(&head, 10);printList(head);  // 输出: 20 -> 30 -> NULLNode* foundNode = search(head, 30);if (foundNode != NULL) {printf("Found node with value: %d\n", foundNode->data);} else {printf("Node not found\n");}clearList(&head);printList(head);  // 输出: NULLreturn 0;
}

代码解释
- 节点结构 Node：包含一个整数 data 和一个指向下一个节点的指针 next。
- 创建新节点 createNode：分配内存并初始化节点的数据和指针。
- 在链表头部插入节点 insertAtHead：创建新节点并将其插入到链表的头部。
- 在链表尾部插入节点 insertAtTail：创建新节点并将其插入到链表的尾部。
- 删除链表中的节点 deleteNode：从链表中删除指定值的节点。
- 查找链表中的节点 search：在链表中查找指定值的节点。
- 遍历链表并打印所有节点 printList：遍历链表并打印所有节点的数据。
- 清空链表 clearList：释放链表中所有节点的内存并设置头节点为 NULL。
- 主函数 main:
  - 创建一个空的链表 head。
  - 插入一些节点并打印链表。
  - 删除一个节点并打印链表。
  - 查找一个节点并输出结果。
  - 清空链表并打印链表。
运行结果：