单链表核心知识详解
单链表是一种动态存储的线性数据结构，其特点是逻辑上连续，物理上非连续，每个节点包含数据域和指向下一个节点的指针域。以下是核心知识点与完整实现代码：
一、单链表的结构定义
单链表节点通过结构体自引用实现：
typedef int SLTDataType; // 数据类型可自定义typedef struct SListNode {SLTDataType data; // 数据域struct SListNode* next; // 指针域，指向下一个节点
} SLTNode;关键点：
- 头指针：指向第一个节点的地址（若链表为空则为
NULL）。 - 尾节点：
next指针为NULL，表示链表结束 。
二、单链表的增删改查操作实现
1. 创建新节点
SLTNode* SLTBuyNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;newnode->next = NULL;return newnode;
}作用：动态分配内存创建新节点，初始化数据和指针域。
2. 插入操作
(1) 头插法：在链表头部插入新节点
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}逻辑：新节点的next指向原头节点，头指针更新为新节点。
(2) 尾插法：在链表尾部插入新节点
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL) {*pphead = newnode;} else {SLTNode* tail = *pphead;while (tail->next != NULL) {tail = tail->next;}tail->next = newnode;}
}逻辑：若链表为空直接插入，否则遍历到尾部再插入。
(3) 指定位置后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}逻辑：将新节点插入到pos节点之后，时间复杂度为O(1)。
3. 删除操作
(1) 头删：删除链表头节点
void SLTPopFront(SLTNode** pphead) {assert(pphead && *pphead);SLTNode* tmp = *pphead;*pphead = (*pphead)->next;free(tmp);
}逻辑：保存原头节点地址，头指针后移，释放原头节点。
(2) 尾删：删除链表尾节点
void SLTPopBack(SLTNode** pphead) {assert(pphead && *pphead);if ((*pphead)->next == NULL) { // 只有一个节点free(*pphead);*pphead = NULL;} else {SLTNode* prev = *pphead;while (prev->next->next != NULL) {prev = prev->next;}free(prev->next);prev->next = NULL;}
}逻辑：遍历到倒数第二个节点，释放尾节点并置空指针。
(3) 删除指定节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead && pos && *pphead);if (*pphead == pos) {*pphead = pos->next;free(pos);} else {SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);}
}逻辑：若删除头节点直接处理，否则找到前驱节点调整指针。
4. 查找与修改
(1) 按值查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {SLTNode* cur = phead;while (cur) {if (cur->data == x) return cur;cur = cur->next;}return NULL;
}逻辑：遍历链表直到找到匹配值的节点。
(2) 修改节点值
void ModifyNode(SLTNode* pos, SLTDataType new_val) {if (pos) pos->data = new_val;
}逻辑：直接修改指定节点的数据域。
四、关键总结
- 优点：动态内存分配，插入/删除时间复杂度为
O(1)（已知位置时）
- 缺点：无法随机访问，需遍历查找，空间开销较大（指针占用内存）
- 应用场景：频繁插入删除、数据量动态变化的场景（如内存管理、任务调度）