单链表-代码精简版
单链表核心知识详解单链表是一种动态存储的线性数据结构，其特点是逻辑上一连，物理上非一连，每个节点包含数据域和指向下一个节点的指针域。以下是核心知识点与完备实当代码：
一、单链表的结构界说
单链表节点通过结构体自引用实现：
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)（已知位置时）
[*]缺点：无法随机访问，需遍历查找，空间开销较大（指针占用内存）
[*]应用场景：频仍插入删除、数据量动态变革的场景（如内存管理、任务调理）
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]