C语言单链表实现原理与操作详解
链表基本概念
链式存储是线性表的一种重要实现方式，与顺序表不同，它通过指针将分散的内存单元串联起来。每个存储单元称为结点，包含两部分：存储实际数据的数据域和记录后继位置的指针域。
单链表的结点结构如下：
typedef int DataType;
// 链表结点定义
typedef struct ListNode {
DataType value; // 数据域
struct ListNode* link; // 指针域，指向下一个结点
} ListNode;核心术语
- 头指针：指向链表首结点的指针变量
- 头结点：附加在表头的空结点，统一操作边界
- 尾结点：最后一个有效结点，其指针域为空
- 空表：头指针指向头结点且头结点的指针域为空
链表初始化
创建带头结点的空链表：
ListNode* createList(void)
{
ListNode* header = (ListNode*)malloc(sizeof(ListNode));
if (header == NULL) {
return NULL; // 内存分配失败
}
header->value = 0; // 头结点数据域可存储长度等元信息
header->link = NULL;
return header;
}遍历输出
从头结点后第一个有效结点开始访问：
void displayList(ListNode* L)
{
ListNode* current = L->link; // 跳过头结点
while (current != NULL) {
printf("%d ", current->value);
current = current->link;
}
printf("\n");
}插入操作
前插法（头插）
新结点插入到首元素之前，时间复杂度 O(1)：
int pushFront(ListNode* L, DataType item)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (newNode == NULL) return 0;
newNode->value = item;
newNode->link = L->link; // 新结点指向原首结点
L->link = newNode; // 头结点指向新结点
return 1;
}前插法会使数据呈现逆序特性，最后插入的元素位于链表最前端。
后插法（尾插）
新结点追加到链表末尾，需先定位尾结点：
// 辅助函数：获取尾结点
ListNode* getLastNode(ListNode* L)
{
ListNode* p = L;
while (p->link != NULL) {
p = p->link;
}
return p;
}
// 尾插实现
int pushBack(ListNode* L, DataType item)
{
ListNode* tail = getLastNode(L);
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (newNode == NULL) return 0;
newNode->value = item;
newNode->link = NULL;
tail->link = newNode; // 原尾结点指向新结点
return 1;
}指定位置插入
在第 pos 个位置（从1开始计数）插入元素：
int insertAt(ListNode* L, int pos, DataType item)
{
ListNode* prev = L; // 定位到第pos-1个结点
for (int i = 1; i < pos; i++) {
prev = prev->link;
if (prev == NULL) return 0; // pos超出范围
}
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->value = item;
newNode->link = prev->link; // ① 新结点连接后继
prev->link = newNode; // ② 前驱结点连接新结点
return 1;
}删除操作
删除第 pos 个位置的结点，需先找到其前驱：
int eraseAt(ListNode* L, int pos)
{
ListNode* prev = L;
// 定位前驱结点
for (int i = 1; i < pos; i++) {
prev = prev->link;
if (prev == NULL) return 0;
}
ListNode* target = prev->link; // 待删除结点
if (target == NULL) {
printf("删除位置无效\n");
return 0;
}
prev->link = target->link; // 绕过待删除结点
free(target); // 释放内存
return 1;
}查找操作
按值查找
ListNode* searchByValue(ListNode* L, DataType key)
{
ListNode* p = L->link;
while (p != NULL) {
if (p->value == key) {
return p; // 返回结点地址
}
p = p->link;
}
return NULL; // 未找到
}求表长
int getLength(ListNode* L)
{
int count = 0;
ListNode* p = L->link; // 从首元结点开始
while (p != NULL) {
count++;
p = p->link;
}
return count;
}销毁链表
释放所有结点内存，防止内存泄漏：
void destroyList(ListNode* L)
{
ListNode* p = L->link;
ListNode* temp;
while (p != NULL) {
temp = p->link; // 保存下一个结点
free(p); // 释放当前结点
p = temp;
}
L->link = NULL; // 头结点指针域置空
}完整测试示例
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
typedef struct ListNode {
DataType value;
struct ListNode* link;
} ListNode;
// 函数声明（上述实现省略）
int main()
{
ListNode* myList = createList();
// 尾插建立有序链表
pushBack(myList, 10);
pushBack(myList, 20);
pushBack(myList, 30);
printf("初始链表：");
displayList(myList);
// 中间插入
insertAt(myList, 2, 15);
printf("插入15后：");
displayList(myList);
// 删除操作
eraseAt(myList, 2);
printf("删除后：");
displayList(myList);
// 查找验证
ListNode* found = searchByValue(myList, 20);
if (found) {
printf("找到元素：%d\n", found->value);
}
printf("当前长度：%d\n", getLength(myList));
destroyList(myList);
return 0;
}存储结构对比
| 特性 | 单链表 | 顺序表 |
|---|---|---|
| 存储空间 | 动态分配，不连续 | 预分配，连续 |
| 访问方式 | 顺序访问 O(n) | 随机访问 O(1) |
| 插入删除 | 修改指针 O(1) | 移动元素 O(n) |
| 内存开销 | 额外指针域 | 可能预留空间浪费 |
| 适用场景 | 频繁增删，数据规模不定 | 频繁查询，数据规模固定 |
链表变体
循环链表
尾结点的指针域指向头结点而非空，形成环状结构。判空条件变为 header->link == header，可从任意位置开始遍历整个链表。
双向链表
结点增加前驱指针，支持双向遍历：
typedef struct DListNode {
DataType value;
struct DListNode* prior;
struct DListNode* next;
} DListNode;双向链表删除结点无需遍历找前驱，直接通过 p->prior->next = p->next 即可完成，但空间开销增加。
