单向链表实现详解：从零构建完整数据结构
本文将详细解析一个完整的单向链表实现，包括创建节点、插入数据、删除数据和遍历等核心操作，帮助读者深入理解链表数据结构的工作原理。
链表概述
单向链表是一种基础但强大的数据结构，由一系列节点组成，每个节点包含：
数据域：存储实际数据
指针域：指向下一个节点的地址
链表优势：
动态内存分配，无需预先指定大小
插入/删除操作高效，时间复杂度O(1)
内存利用率高，按需分配
下面我们将逐部分解析完整的链表实现代码。
完整代码实现
#include
#include
#include
// 定义数据类型
typedef int TypData;
// 链表节点结构体
typedef struct SingleList {
TypData data; // 数据域
struct SingleList *next; // 指向下一个节点的指针
} SList;
// 创建头结点
SList * CreHeadNode() {
SList *Head = (SList *)calloc(1, sizeof(SList));
if (NULL == Head) {
perror("创建头节点失败");
exit(EXIT_FAILURE);
}
Head->next = NULL; // 初始化为空链表
return Head;
}
// 创建新节点
SList * CreaOneNode(TypData data) {
SList *Node = (SList *)calloc(1, sizeof(SList));
if (NULL == Node) {
perror("创建节点失败");
exit(EXIT_FAILURE);
}
Node->data = data;
Node->next = NULL;
return Node;
}
// 判断链表是否为空
bool IsEmpty(SList *List) {
return (List->next == NULL);
}
// 头插法插入节点
bool InstHeadNode(SList *Head, TypData data) {
SList *New = CreaOneNode(data);
if (NULL == New) return false;
New->next = Head->next; // 新节点指向原第一个节点
Head->next = New; // 头节点指向新节点
return true;
}
// 尾插法插入节点
bool InstTailNode(SList *Head, TypData data) {
SList *p = Head;
// 定位到最后一个节点
while (p->next != NULL) {
p = p->next;
}
SList *New = CreaOneNode(data);
if (NULL == New) return false;
p->next = New; // 最后一个节点指向新节点
return true;
}
// 在指定数据后插入节点
bool InstDataNode(SList *Head, TypData NewData, TypData targetData) {
SList *p = Head->next; // 从第一个实际节点开始查找
while (p != NULL) {
if (p->data == targetData) {
SList *New = CreaOneNode(NewData);
if (NULL == New) return false;
New->next = p->next; // 新节点指向原后继节点
p->next = New; // 当前节点指向新节点
return true;
}
p = p->next;
}
printf("未找到数据 %d，插入失败\n", targetData);
return false;
}
// 遍历并打印链表
void ListPrint(SList *Head) {
if (IsEmpty(Head)) {
printf("链表为空\n");
return;
}
SList *p = Head->next;
printf("链表内容: ");
while (p != NULL) {
printf("%d -> ", p->data);
p = p->next;
}
printf("NULL\n");
}
// 删除头节点（首元节点）
bool DelHeadNode(SList *Head) {
if (IsEmpty(Head)) {
printf("链表为空，删除失败\n");
return false;
}
SList *delNode = Head->next; // 要删除的节点
Head->next = delNode->next; // 头节点指向新的第一个节点
free(delNode); // 释放内存
return true;
}
// 删除尾节点
bool DelTailNode(SList *Head) {
if (IsEmpty(Head)) {
printf("链表为空，删除失败\n");
return false;
}
SList *prev = Head; // 前驱节点
SList *curr = Head->next; // 当前节点
// 定位到最后一个节点及其前驱
while (curr->next != NULL) {
prev = curr;
curr = curr->next;
}
prev->next = NULL; // 前驱节点设为新的尾节点
free(curr); // 释放原尾节点
return true;
}
// 删除指定数据的节点
bool DelSpecNode(SList *Head, TypData data) {
if (IsEmpty(Head)) {
printf("链表为空，删除失败\n");
return false;
}
SList *prev = Head; // 前驱节点
SList *curr = Head->next; // 当前节点
while (curr != NULL) {
if (curr->data == data) {
prev->next = curr->next; // 前驱节点指向后继节点
free(curr); // 释放当前节点
return true;
}
prev = curr; // 更新前驱
curr = curr->next; // 移动到下一个节点
}
printf("未找到数据 %d，删除失败\n", data);
return false;
}
// 释放整个链表
void FreeList(SList *Head) {
SList *current = Head;
while (current != NULL) {
SList *temp = current;
current = current->next;
free(temp);
}
}
核心功能详解
1. 节点创建与管理
头节点创建：
SList *Head = (SList *)calloc(1, sizeof(SList));
Head->next = NULL; // 关键：初始化为空链表
头节点不存储实际数据，作为链表入口点，其next指针指向第一个实际节点。
普通节点创建：
Node->data = data;
Node->next = NULL; // 新节点初始为链尾
每个新节点创建时next指针设为NULL，避免野指针问题。
2. 插入操作对比
插入方式
时间复杂度
适用场景
头插法
O(1)
栈结构实现、最近添加项优先访问
尾插法
O(n)
队列结构实现、保持添加顺序
指定位置插入
O(n)
需要特定顺序的插入操作
头插法示意图：
头节点 -> [新节点] -> [原第一个节点]
尾插法示意图：
头节点 -> ... -> [尾节点] -> [新节点]
3. 删除操作精要
头删法：
SList *delNode = Head->next;
Head->next = delNode->next; // 头节点指向新的第一个节点
free(delNode);
尾删法：
while (curr->next != NULL) { // 找到最后一个节点
prev = curr;
curr = curr->next;
}
prev->next = NULL; // 倒数第二个节点设为新尾节点
free(curr);
指定删除：
prev->next = curr->next; // 前驱节点指向后继节点
free(curr); // 绕过当前节点并释放
4. 遍历与打印
void ListPrint(SList *Head) {
SList *p = Head->next; // 跳过头节点
while (p != NULL) {
printf("%d -> ", p->data);
p = p->next;
}
printf("NULL\n"); // 明确链表结束
}
使用箭头符号直观表示节点间关系，最后以NULL结尾，清晰展示链表结构。
内存管理要点
动态分配：
所有节点使用calloc动态创建
初始化为零避免未定义行为
释放策略：
void FreeList(SList *Head) {
SList *current = Head;
while (current != NULL) {
SList *temp = current;
current = current->next;
free(temp);
}
}
从头部开始依次释放所有节点
使用临时指针保存当前节点地址
先获取下一个节点地址再释放当前节点
使用示例
int main() {
// 创建链表
SList *myList = CreHeadNode();
// 插入数据
InstTailNode(myList, 10);
InstTailNode(myList, 20);
InstHeadNode(myList, 5);
InstDataNode(myList, 15, 10); // 在10后插入15
// 打印链表：5 -> 10 -> 15 -> 20 -> NULL
ListPrint(myList);
// 删除操作
DelHeadNode(myList); // 删除5
DelTailNode(myList); // 删除20
DelSpecNode(myList, 10); // 删除10
// 打印链表：15 -> NULL
ListPrint(myList);
// 释放整个链表
FreeList(myList);
return 0;
}
总结与思考
单向链表作为基础数据结构，具有以下特点：
插入/删除高效：时间复杂度O(1)（已知位置）
空间利用率高：动态分配内存，无空间浪费
访问效率低：随机访问需要O(n)时间