单链表-代码精简版

单链表核心知识详解

单链表是一种动态存储的线性数据结构，其特点是逻辑上一连，物理上非一连，每个节点包含数据域和指向下一个节点的指针域。以下是核心知识点与完备实当代码：
一、单链表的结构界说

单链表节点通过结构体自引用实现：

1. typedef int SLTDataType;  // 数据类型可自定义
3. typedef struct SListNode {
4.     SLTDataType data;      // 数据域
5.     struct SListNode* next; // 指针域，指向下一个节点
6. } SLTNode;

复制代码

关键点：

• 头指针：指向第一个节点的地点（若链表为空则为NULL）。
  
• 尾节点：next指针为NULL，表现链表竣事 。
  

二、单链表的增删改查操作实现

1. 创建新节点

1. SLTNode* SLTBuyNode(SLTDataType x) {
2.     SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
3.     newnode->data = x;
4.     newnode->next = NULL;
5.     return newnode;
6. }

复制代码

作用：动态分配内存创建新节点，初始化数据和指针域。
2. 插入操作

(1) 头插法：在链表头部插入新节点

1. void SLTPushFront(SLTNode** pphead, SLTDataType x) {
2.     assert(pphead);
3.     SLTNode* newnode = SLTBuyNode(x);
4.     newnode->next = *pphead;
5.     *pphead = newnode;
6. }

复制代码

逻辑：新节点的next指向原头节点，头指针更新为新节点。
(2) 尾插法：在链表尾部插入新节点

1. void SLTPushBack(SLTNode** pphead, SLTDataType x) {
2.     assert(pphead);
3.     SLTNode* newnode = SLTBuyNode(x);
4.     if (*pphead == NULL) {
5.         *pphead = newnode;
6.     } else {
7.         SLTNode* tail = *pphead;
8.         while (tail->next != NULL) {
9.             tail = tail->next;
10.         }
11.         tail->next = newnode;
12.     }
13. }

复制代码

逻辑：若链表为空直接插入，否则遍历到尾部再插入。
(3) 指定位置后插入

1. void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
2.     assert(pos);
3.     SLTNode* newnode = SLTBuyNode(x);
4.     newnode->next = pos->next;
5.     pos->next = newnode;
6. }

复制代码

逻辑：将新节点插入到pos节点之后，时间复杂度为O(1)。
3. 删除操作

(1) 头删：删除链表头节点

1. void SLTPopFront(SLTNode** pphead) {
2.     assert(pphead && *pphead);
3.     SLTNode* tmp = *pphead;
4.     *pphead = (*pphead)->next;
5.     free(tmp);
6. }

复制代码

逻辑：保存原头节点地点，头指针后移，开释原头节点。
(2) 尾删：删除链表尾节点

1. void SLTPopBack(SLTNode** pphead) {
2.     assert(pphead && *pphead);
3.     if ((*pphead)->next == NULL) { // 只有一个节点
4.         free(*pphead);
5.         *pphead = NULL;
6.     } else {
7.         SLTNode* prev = *pphead;
8.         while (prev->next->next != NULL) {
9.             prev = prev->next;
10.         }
11.         free(prev->next);
12.         prev->next = NULL;
13.     }
14. }

复制代码

逻辑：遍历到倒数第二个节点，开释尾节点并置空指针。

(3) 删除指定节点

1. void SLTErase(SLTNode** pphead, SLTNode* pos) {
2.     assert(pphead && pos && *pphead);
3.     if (*pphead == pos) {
4.         *pphead = pos->next;
5.         free(pos);
6.     } else {
7.         SLTNode* prev = *pphead;
8.         while (prev->next != pos) {
9.             prev = prev->next;
10.         }
11.         prev->next = pos->next;
12.         free(pos);
13.     }
14. }

复制代码

逻辑：若删除头节点直接处置惩罚，否则找到前驱节点调解指针。
4. 查找与修改

(1) 按值查找

1. SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
2.     SLTNode* cur = phead;
3.     while (cur) {
4.         if (cur->data == x) return cur;
5.         cur = cur->next;
6.     }
7.     return NULL;
8. }

复制代码

逻辑：遍历链表直到找到匹配值的节点。
(2) 修改节点值

1. void ModifyNode(SLTNode* pos, SLTDataType new_val) {
2.     if (pos) pos->data = new_val;
3. }

复制代码

逻辑：直接修改指定节点的数据域。
四、关键总结

• 优点：动态内存分配，插入/删除时间复杂度为O(1)（已知位置时） 
   
  
• 缺点：无法随机访问，需遍历查找，空间开销较大（指针占用内存） 
   
  
• 应用场景：频仍插入删除、数据量动态变革的场景（如内存管理、任务调理）
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。