单向链表 (Singly Linked List)
每个节点包含数据域与指向后继的指针。头插 O(1)，尾插需遍历或维护尾指针。
结构定义
typedef struct SNode {
int data;
struct SNode *next;
} SNode;函数签名
| 函数 | 复杂度 | 说明 |
|---|---|---|
SNode* slist_create(int val) | O(1) | 创建单节点 |
void slist_push_front(SNode **head, int val) | O(1) | 头插法 |
void slist_pop_front(SNode **head) | O(1) | 删除头节点 |
void slist_insert_after(SNode *node, int val) | O(1) | 在 node 之后插入 |
void slist_remove_after(SNode *node) | O(1) | 删除 node 的后继 |
SNode* slist_find(SNode *head, int val) | O(n) | 按值查找 |
void slist_free(SNode *head) | O(n) | 释放整条链表 |
void slist_reverse(SNode **head) | O(n) | 原地反转 |
使用模式
SNode *head = NULL;
slist_push_front(&head, 30);
slist_push_front(&head, 20);
slist_push_front(&head, 10);
/* 10 -> 20 -> 30 */
slist_pop_front(&head);
/* 20 -> 30 */
slist_free(head);经典操作
反转链表（迭代）：
void slist_reverse(SNode **head) {
SNode *prev = NULL, *curr = *head;
while (curr) {
SNode *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
}对比双向链表
| 特性 | 单向链表 | 双向链表 |
|---|---|---|
| 内存占用 | 1 个指针/节点 | 2 个指针/节点 |
| 前驱查找 | O(n) | O(1) |
| 任意删除 | O(n)（需前驱） | O(1) |
| 使用场景 | 简单队列/栈 | 需要双向遍历 |