介绍
链表是一种常见的数据结构，用于存储一系列线性数据。与数组不同，链表中的元素在内存中不必是连续存放的，而是通过指针将每个元素（节点）链接在一起。链表有很多种类型，例如单向链表、双向链表和循环链表。这里我们主要介绍单向链表。
单向链表
单向链表由一系列节点组成，每个节点包含两个部分：
- 数据部分：存储节点的实际内容。
- 指针部分：存储指向下一个节点的指针。
节点结构
在 C 语言中，我们可以通过定义一个结构体来表示链表的节点：
struct Node {
int data; // 数据部分
struct Node* next; // 指针部分
};
创建节点
可以通过动态内存分配函数 malloc 来创建新节点：
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构
struct Node {
int data;
struct Node* next;
};
// 创建新节点
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
插入节点
我们可以在链表的头部或尾部插入节点。以头部插入为例：
// 头部插入
void insertAtHead(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
删除节点
删除链表中的节点也很常见。假设我们要删除值为 key 的节点：
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head;
struct Node* prev = NULL;
// 如果头节点本身就是要删除的节点
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp); // 释放内存
return;
}
// 搜索要删除的节点
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// 如果没找到要删除的节点
if (temp == NULL) return;
// 断开链接并释放内存
prev->next = temp->next;
free(temp);
}
遍历链表
遍历链表可以通过循环来实现：
void printList(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
尾部插入
尾部插入与头部插入类似，我们需要找到链表的最后一个节点，然后将新节点添加到末尾。
// 尾部插入
void insertAtTail(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
查找节点
查找链表中的某个节点，返回其位置或者指针：
struct Node* searchNode(struct Node* head, int key) {
struct Node* current = head;
while (current != NULL) {
if (current->data == key) {
return current;
}
current = current->next;
}
return NULL; // 未找到
}
链表反转
反转链表是一个经典的问题，可以通过迭代的方式实现：
void reverseList(struct Node** head) {
struct Node* prev = NULL;
struct Node* current = *head;
struct Node* next = NULL;
while (current != NULL) {
next = current->next; // 暂存下一个节点
current->next = prev; // 反转当前节点的指针
prev = current; // 移动 prev 指针
current = next; // 移动 current 指针
}
*head = prev;
}
示例程序
程序1
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void insertAtHead(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head;
struct Node* prev = NULL;
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}
void printList(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
insertAtHead(&head, 1);
insertAtHead(&head, 2);
insertAtHead(&head, 3);
printf("Created Linked List: ");
printList(head);
deleteNode(&head, 2);
printf("Linked List after deletion of 2: ");
printList(head);
return 0;
}
输出结果：
程序2
#include <stdio.h>
#include <stdlib.h>
// 定义节点结构
struct Node {
int data;
struct Node* next;
};
// 创建新节点
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 头部插入
void insertAtHead(struct Node** head, int data) {
struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
// 尾部插入
void insertAtTail(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
// 删除节点
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head;
struct Node* prev = NULL;
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}
// 查找节点
struct Node* searchNode(struct Node* head, int key) {
struct Node* current = head;
while (current != NULL) {
if (current->data == key) {
return current;
}
current = current->next;
}
return NULL;
}
// 反转链表
void reverseList(struct Node** head) {
struct Node* prev = NULL;
struct Node* current = *head;
struct Node* next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head = prev;
}
// 打印链表
void printList(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
insertAtHead(&head, 1);
insertAtHead(&head, 2);
insertAtHead(&head, 3);
printf("初始链表: ");
printList(head);
// 测试尾部插入
insertAtTail(&head, 4);
printf("尾部插入 4 后的链表: ");
printList(head);
// 测试删除节点
deleteNode(&head, 2);
printf("删除节点 2 后的链表: ");
printList(head);
// 测试查找节点
struct Node* foundNode = searchNode(head, 3);
if (foundNode) {
printf("找到节点 3\n");
} else {
printf("未找到节点 3\n");
}
// 测试反转链表
reverseList(&head);
printf("反转后的链表: ");
printList(head);
return 0;
}
输出结果：
