与顺序存储结构（如数组）不同，链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻，它通过指针将一组零散的内存块链接起来,形成一个数据序列。
（图片来源网络，侵删）
链表的基本概念
链表由一系列节点组成,每个节点包含两部分：
- 数据域：存储数据元素本身的信息。
- 指针域：存储指向下一个节点的指针。
对于单向链表，最后一个节点的指针域指向 NULL,表示链表的结束。
示意图：
Head Node 1 Node 2 Node 3 ... Node N
+--------+ +--------+ +--------+ +--------+
| Data | -> | Data | -> | Data | ... -> | Data |
+--------+ +--------+ +--------+ +--------+
| Next |----->| Next |----->| Next |---------> | NULL |
+--------+ +--------+ +--------+ +--------+单向链表的C语言实现
下面是一个完整的、带有注释的单向链表C语言实现，包含了创建、插入、删除、查找、遍历和销毁等基本操作。
（图片来源网络，侵删）
1 定义节点结构体
我们需要定义一个结构体来表示链表的节点。
#include <stdio.h>
#include <stdlib.h> // 用于 malloc 和 free
// 定义链表节点结构体
typedef struct Node {
int data; // 数据域，这里以 int 类型为例
struct Node *next; // 指针域，指向下一个节点
} Node;
2 初始化链表
链表的头指针 head 是一个指向第一个节点的指针，如果链表为空，head 就为 NULL。
// 初始化一个空链表
Node* initList() {
return NULL; // 空链表的头指针为 NULL
}
3 创建新节点
这是一个辅助函数,用于动态分配内存并创建一个新节点。
// 创建一个新节点
Node* createNode(int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("内存分配失败！\n");
exit(1); // 内存分配失败，退出程序
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
4 插入节点
插入操作是链表的精髓，有多种插入方式,我们介绍最常用的两种：
a) 在链表头部插入（头插法）
- 时间复杂度: O(1)
- 将新节点作为新的头节点。
// 在链表头部插入节点
Node* insertAtHead(Node *head, int data) {
Node *newNode = createNode(data);
newNode->next = head; // 新节点的next指向原来的头节点
head = newNode; // 更新头节点指针
return head; // 返回新的头节点
}
b) 在链表尾部插入（尾插法）
- 时间复杂度: O(n),因为需要遍历到链表末尾。
- 将新节点添加到链表的最后。
// 在链表尾部插入节点
Node* insertAtTail(Node *head, int data) {
Node *newNode = createNode(data);
// 如果链表为空，新节点就是头节点
if (head == NULL) {
return newNode;
}
// 遍历到链表的最后一个节点
Node *current = head;
while (current->next != NULL) {
current = current->next;
}
// 将最后一个节点的next指向新节点
current->next = newNode;
return head; // 头节点不变
}
5 删除节点
删除节点需要找到待删除节点的前一个节点，然后修改其 next 指针。
// 删除值为 data 的第一个节点
Node* deleteNode(Node *head, int data) {
if (head == NULL) {
printf("链表为空，无法删除，\n");
return NULL;
}
// 如果要删除的是头节点
if (head->data == data) {
Node *temp = head;
head = head->next; // 头指针后移
free(temp); // 释放旧头节点的内存
return head;
}
// 寻找要删除的节点及其前一个节点
Node *current = head;
while (current->next != NULL && current->next->data != data) {
current = current->next;
}
// 如果找到了要删除的节点
if (current->next != NULL) {
Node *temp = current->next; // temp 是要删除的节点
current->next = temp->next; // 前一个节点的next指向要删除节点的下一个
free(temp); // 释放内存
printf("删除了值为 %d 的节点，\n", data);
} else {
printf("未找到值为 %d 的节点，\n", data);
}
return head;
}
6 查找节点
遍历链表,查找是否存在指定值的节点。
// 查找值为 data 的节点，如果找到返回节点指针，否则返回 NULL
Node* findNode(Node *head, int data) {
Node *current = head;
while (current != NULL) {
if (current->data == data) {
return current; // 找到，返回节点指针
}
current = current->next;
}
return NULL; // 未找到
}
7 遍历（打印）链表
从头节点开始,依次访问每个节点并打印其数据。
// 打印链表中的所有节点
void printList(Node *head) {
if (head == NULL) {
printf("链表为空，\n");
return;
}
Node *current = head;
printf("链表内容: ");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
8 销毁链表（释放内存）
为了避免内存泄漏，当不再需要链表时,必须释放所有节点占用的内存。
// 释放整个链表的内存
void destroyList(Node *head) {
Node *current = head;
Node *nextNode;
while (current != NULL) {
nextNode = current->next; // 先保存下一个节点的地址
free(current); // 释放当前节点
current = nextNode; // 移动到下一个节点
}
printf("链表已销毁，\n");
}
完整示例代码
下面是一个 main 函数,演示如何使用上述所有函数。
int main() {
// 1. 初始化一个空链表
Node *head = initList();
printList(head);
// 2. 使用头插法插入数据
head = insertAtHead(head, 10);
head = insertAtHead(head, 20);
head = insertAtHead(head, 30);
printf("头插法插入 30, 20, 10 后:\n");
printList(head);
// 3. 使用尾插法插入数据
head = insertAtTail(head, 40);
head = insertAtTail(head, 50);
printf("尾插法插入 40, 50 后:\n");
printList(head);
// 4. 查找节点
int searchValue = 20;
Node *foundNode = findNode(head, searchValue);
if (foundNode != NULL) {
printf("找到了值为 %d 的节点，\n", searchValue);
} else {
printf("未找到值为 %d 的节点，\n", searchValue);
}
// 5. 删除节点
head = deleteNode(head, 30); // 删除头节点
head = deleteNode(head, 50); // 删除中间节点
head = deleteNode(head, 99); // 删除不存在的节点
printf("删除 30 和 50 后:\n");
printList(head);
// 6. 销毁链表
destroyList(head);
head = NULL; // 防止悬空指针
return 0;
}
程序运行结果：
链表为空。
头插法插入 30, 20, 10 后: 30 -> 20 -> 10 -> NULL
尾插法插入 40, 50 后: 30 -> 20 -> 10 -> 40 -> 50 -> NULL
找到了值为 20 的节点。
删除了值为 30 的节点。
删除了值为 50 的节点。
未找到值为 99 的节点。
删除 30 和 50 后: 20 -> 10 -> 40 -> NULL
链表已销毁。链表的优缺点
优点
- 动态大小：链表的大小可以在运行时动态地增加或缩小,无需预先分配固定大小的内存。
- 高效的插入和删除：在已知节点位置的情况下，插入和删除操作的时间复杂度为 O(1)，相比之下，数组在中间或头部插入/删除需要移动大量元素，时间复杂度为 O(n)。
- 内存利用灵活：链表的节点可以分布在内存的任何位置，不存在内存浪费（数组可能因预留空间而浪费）。
缺点
- 额外的存储空间：每个节点都需要一个额外的指针域来存储下一个节点的地址,这比数组要多占用一些内存。
- 访问效率低：不能像数组那样通过下标直接访问任意位置的元素，访问第
i个节点必须从头节点开始遍历，时间复杂度为 O(n)。 - 实现相对复杂：指针操作容易出错，如内存泄漏、悬空指针等问题,需要仔细管理。
其他类型的链表
除了上述的单向链表,还有其他变种：
- 双向链表：每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点，这使得双向遍历和删除节点更容易（因为不需要找到前一个节点）。
- 循环链表：链表的最后一个节点的
next指针指向头节点，形成一个环,常用于实现队列等数据结构。 - 静态链表：借助数组来描述链表，指针域存储的是数组下标,这在某些没有指针的语言或特定场景下会用到。
链式存储结构是C语言中实现线性表的一种非常重要且灵活的方式，它通过牺牲一些随机访问的效率，换取了动态内存管理和高效插入删除的优势,理解并掌握链表的实现是学习数据结构与算法的基石。
