【数据结构】单向链表实现 超详细

目录

一. 单链表的实现

1.准备工作及其注意事项

1.1 先创建三个文件

1.2 注意事项：帮助高效记忆和理解

2.链表的基本功能接口

2.0 创建一个 链表

2.1 链表的打印

 3.链表的创建新节点接口

4.链表的节点插入功能接口

4.1 尾插接口

4.2 头插接口  

  4.3 指定位置 pos 之前 插入接口

 4.4 指定位置pos 之后 插入接口（推荐）

5.链表表的删除功能接口

5.1 尾删接口

5.2头删接口

5.3 删除 指定位置 pos 节点 接口

5.4 删除  指定位置 pos ==之后== 的一个 节点 接口

6.链表的  查找  接口

7.链表的  销毁  接口

二、总代码

SList.h

SList.c

test.c

---

前言：（受篇幅限制，为了划清知识模块，进行分章节讲解）

若想了解清楚 链表的概念和分类 ：

可以点击跳转 这一章节----> :【数据结构】链表的概念 及 分类 （使用比喻解释概念）

---

一. 单链表的实现

1.准备工作及其注意事项

1.1 先创建三个文件

 解释这三个文件的作用
 1、头文件SList.h  是来声明接口函数，定义链表，将几个公共用到的库函数集合起来
 2、源文件SList.c  是用来具体实现接口
 3、源文件test.c  用于接口的测试工作 ，即具体的使用场景

1.2 注意事项：帮助高效记忆和理解

1. 但凡是删除，必须 断言 链表不能为 空，避免传过来的是NULL指针 assert(*pphead);
2. 传递二级指针，要断言 不能为 NULL ，指针不能为空：assert(pphead);
3. 指定位置 pos 时，要确保pos存在：assert(pos);
4. (pphead)->next;  解引用前一定要加 括号，* 号 优先级 < 箭头操作符
5. 链表的所有插入接口：链表为空： 没有节点 就直接插入
6.要找 前一个节点 prev 或 后一个节点 next 时， 一定要确保 其本身存在！！！！
7.当指定位置 pos 刚好是 头节点时 就没有 prev 了

2.链表的基本功能接口

2.0 创建一个 链表

// 创建链表节点结构体
// 和顺序表创建原理相同，可以看我的 【顺序表】章节
typedef  int  SLDataType;
typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SLTNode;

2.1 链表的打印

// 打印函数
//注意这里的 phead 仅表示单向链表传递过来的 第一个节点地址，不是 双向链表的带头节点 
void SLTPrint(SLTNode* phead)
{SLTNode* ptemp = phead;while (ptemp) // ptemp != NULL 说明为是有效的节点，则循环打印{printf("%d -> ", ptemp->data);ptemp = ptemp->next; // 更新 ptemp ：保存下个节点的地址：遍历节点的关键}printf("NULL\n");
}

 3.链表的创建新节点接口

// 创建新节点函数：所有的插入接口，都需要 创建新节点
SLTNode* STLCreatNode(SLDataType x)
{// 先创建 一个 新节点SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));newNode->data = x;newNode->next = NULL;return newNode;
}

4.链表的节点插入功能接口

4.1 尾插接口

链表的尾插法
几种情况
1、链表非空：先找到尾节点，然后直接将尾节点 的 next 指向 新节点，(形成链接), 新节点 则 指向 NULL 变成 新的尾节点
2、链表为空：将头指针phead更新 成 新插入节点的地址，然后新节点 next 指向 NULL

// 注意：plist 头指针是 时刻更新为了指向头节点，当创建新的头节点后，要更新 plist ，而若要真正改变 plist 的值，需要传地址
// 传递过来的 头指针 &plist 是 一级指针 plist 的地址，要用 二级指针 pphead 来接收 ； 而 *pphead == plist 
// void SLTPushBack(SLTNode* phead, SLDataType x) // 错误写法：传值void SLTPushBack(SLTNode** pphead, SLDataType x)
{assert(pphead); // 传递过来的 一级指针的地址 二级指针 不能为 NULL// 先创建 一个 新节点SLTNode* newNode = STLCreatNode(x);// 1、链表为空if (*pphead == NULL){*pphead = newNode;return;}// 2、链表非空SLTNode* ptail = *pphead; // 因为要找 尾节点：干脆命名为 tail//本质是：找到尾节点的地址，而不是 尾节点的 nextwhile (ptail->next) {ptail = ptail->next;}ptail->next = newNode;
}

4.2 头插接口  

void SLTPushFront(SLTNode** pphead, SLDataType x)
{assert(pphead); // 传递过来的 一级指针的地址 二级指针 不能为 NULL// 先创建 一个 新节点SLTNode* newNode = STLCreatNode(x);newNode->next = *pphead; // 先将原本的 头指针放在 新节点的next*pphead = newNode; // 更新 头指针
}

  4.3 指定位置 pos 之前 插入接口

// 在指定位置节点pos 之前插入数据 
// 思路：找三个节点 ：prev     newNode      next 
//                  前      本身新节点     后         为了找到 地址 才能将三者链接起来
// 注意：要找 前一个节点 prev 时， 一定要确保 其本身存在！！！ 
// 当 pos 刚好是 头节点时 就没有 prev 了，特殊情况, 否则会因为找不到prev而 程序奔溃
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead); // 指针不能为空assert(pos); // pos 不能为空assert(*pphead); // 链表不能为空: pos 是链表中 的一个有效节点，pos 不为空，链表也不能为 空// 创建新节点SLTNode* newNode = STLCreatNode(x);if (*pphead == pos){// 当 pos 刚好是 头节点时 就用 头插法：调用之前写的函数接口SLTPushFront(pphead, x);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}// 三者关联起来:  prev -> newNode -> posnewNode->next = pos;prev->next = newNode;
}

 4.4 指定位置pos 之后 插入接口（推荐）

// 在指定位置节点pos 之后插入数据: 注意一下错误写法： 和正确写法刚好相反
// 特点：有了 pos 就不需要 头节点了！！
void SLTInsertAfter(SLTNode*pos, SLDataType x)
{assert(pos); // pos 不能为空// 创建新节点SLTNode* newNode = STLCreatNode(x);newNode->next = pos->next;pos->next = newNode;
}

5.链表表的删除功能接口

5.1 尾删接口

// 链表的尾删法
// 思路：删除尾节点 以及  前一个节点 pre 的next 要置为 NULL
// 要注意 只有一个节点时，没有前置节点 pre！！！！
void SLTPopBack(SLTNode** pphead)
{assert(pphead); // 一级指针为plist 指向头节点，传递过来的 一级指针的地址二级指针不能为 NULLassert(*pphead); // 一级指针为plist 指向头节点, *pphead == plist 这个指针也不能为 NULL 不能为空链表// 链表非空// 链表只有一个节点时if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}// 链表有多个节点SLTNode* ptail = *pphead;SLTNode* prev = NULL; // 时刻更新保存 while(ptail->next){ prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;
}

5.2头删接口

// 链表的头删法
void SLTPopFront(SLTNode** pphead)
{assert(pphead); // 指针不能为空assert(*pphead); // 链表不能为空// 让第二个节点成为新的头节点// 将 旧的节点释放掉: 注意 要先将 第二个节点的地址  (*pphead) -> next  临时储存起来！！SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

5.3 删除 指定位置 pos 节点 接口

// 删除pos 节点
// 删除 pos 节点后，还要 将 prev 和 next （pos的前后两个节点） 链接上！！： 比较麻烦
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead); // 指针不能为空assert(pos); // pos 不能为空assert(*pphead); // 链表不能为空: pos 是链表中 的一个有效节点，pos 不为空，链表也不能为 空//先 让 prev 链接上 next，后 free 释放掉 pos// 遇到 需要找 prev 的，一定要 检查是否存在 previf (*pphead == pos)//检查是否存在 prev{free(pos);*pphead = NULL;return;}SLTNode* prev = *pphead;while (prev->next != pos) // 找 前面节点 prev{prev = prev->next;}prev->next = pos->next; // 先赋值后 再free释放free(pos);pos = NULL;
}

 5.4 删除  指定位置 pos ==之后== 的一个 节点 接口

// 删除pos 之后的节点
// 直接 删除 pos 之后的 节点 pos->next  
// 先让 pos 和 pos -> next -> next 链接起来，后 删除 节点 pos -> next 
// 注意：像这类找 上一个节点 prev 或 找下一个节点 next ：都需要 检查 是否存在 该节点
void SLTEraseBeind(SLTNode* pos)
{assert(pos); // pos 不能为空assert(pos->next); // 这个节点必须存在，否则该函数无意义！ 链表至少要有两个节点// 三者的关联关系：pos    pos->next    pos->next->next// 注意：下面 先 pos->next = pos->next->next， 后 free(pos->next) 是不对的  // pos->next 已经更新，不是你所认为的原来的那个 中间节点了，因此要先 临时保存起来！！！SLTNode* temp = pos->next;pos->next = pos->next->next;free(temp);temp = NULL;
}

 6.链表的  查找  接口

// 链表的查找
SLTNode* SLTFind(SLTNode** pphead, SLDataType x)
{// 遍历链表assert(pphead); // 指针不能为空SLTNode* ptemp = *pphead;while (ptemp){if (ptemp->data == x) return ptemp; // 找到了就返回节点ptemp = ptemp->next;}// 没找到return NULL;
}

7.链表的  销毁  接口

// 销毁链表
// 一旦涉及到 动态内存申请，不要忘记销毁
void SListDestory(SLTNode** pphead)
{assert(pphead); // 指针不能为空assert(*pphead); // 链表不能为空，空的没必要销毁了// 顺序表是一段连续的空间，可以执行一次free全部销毁，而链表节点是独立的，需要遍历节点一个一个销毁// 不能直接 一个一个 free 下去，需要 保存 next 节点，才能找到下个节点！！！！SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}// 当所有节点销毁后，需要 将头指针 销毁*pphead = NULL;
}

二、总代码

SList.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>// 零、创建链表节点
typedef int SLDataType;
typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SLTNode;// 一、打印函数: 这里用传址
void SLTPrint(SLTNode* ps);// 二、尾插法
void SLTPushBack(SLTNode** pphead, SLDataType x);// 三、头插法
void SLTPushFront(SLTNode** pphead, SLDataType x);// 四、尾删法
void SLTPopBack(SLTNode** pphead);// 五、头删法
void SLTPopFront(SLTNode** pphead);// 六、链表的查找
SLTNode* SLTFind(SLTNode** pphead, SLDataType x);// 七、指定位置 pos 之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);// 八、指定位置 pos 之后 插入
void SLTInsertAfter(SLTNode* pos, SLDataType x);// 九、删除 指定 pos 节点
void SLTErase(SLTNode** pphead, SLTNode* pos);// 十、删除指定 pos 之后 的节点
void SLTEraseAfter(SLTNode* pos);// 十一、销毁链表
void SLTDestory(SLTNode** pphead);

SList.c

#include"SList.h"// 一、打印函数: 这里用传址
void SLTPrint(SLTNode* phead)
{SLTNode* ptemp = phead;while (ptemp) //  ptemp != NULL 表示为有效节点 {printf("%d -> ", ptemp->data);ptemp = ptemp->next;}printf("NULL\n");
}// 创建节点函数
SLTNode* SLTCreatNode(SLDataType x)
{SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));newNode->data = x;newNode->next = NULL;return newNode;
}
// 二、尾插法
void SLTPushBack(SLTNode** pphead, SLDataType x)
{assert(pphead);// 创建新节点SLTNode* newNode = SLTCreatNode(x);// 链表为空： 没有节点 就直接插入if (*pphead == NULL){*pphead = newNode;return;}// 链表非空：找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newNode;
}// 三、头插法
void SLTPushFront(SLTNode** pphead, SLDataType x)
{assert(pphead);// 创建新节点SLTNode* newNode = SLTCreatNode(x);// 先 链接 第一个节点，  没有第一个节点就是 NULL，也可以直接给 newNode->next，后更新 *ppheadnewNode->next = *pphead;*pphead = newNode;
}// 四、尾删法
void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);// 先找尾节点 和 前置节点 prev，后删除+链接// 当只有一个 节点时if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}// 当有 两个 节点 及以上SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;
}// 五、头删法
void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);// 让 *pphead 指向第二个节点，free 掉第一个SLTNode* next = (*pphead)->next; // 一定要加 括号，* 号 优先级 < 箭头操作符 free(*pphead);*pphead = next;
}// 六、链表的查找
SLTNode* SLTFind(SLTNode** pphead, SLDataType x)
{assert(pphead);// 遍历SLTNode* ptemp = *pphead;while (ptemp){if (ptemp->data == x) return ptemp;ptemp = ptemp->next;}return NULL;
}// 七、指定位置 pos 之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead);assert(pos);assert(*pphead);// 涉及到三个节点： prev    newNode   pos// 创建新节点SLTNode* newNode = SLTCreatNode(x);if (*pphead == pos)// 无 prev 的情况{SLTPushFront(pphead, x);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newNode->next = pos;prev->next = newNode;
}// 八、指定位置 pos 之后 插入（推荐！）
void SLTInsertAfter(SLTNode* pos, SLDataType x)
{assert(pos);// 创建新节点SLTNode* newNode = SLTCreatNode(x);newNode->next = pos->next;pos->next = newNode;
}// 九、删除 指定 pos 节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);assert(*pphead);// 关系三个节点：prev    pos    next// 先找 prevSLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}// 十、删除指定 pos 之后 的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next); // 注意  pos->next 这个必须存在// 关系三个节点： pos      pos->next     pos->next->next// 另一种可能：     pos      pos->next     NULLif (pos->next->next == NULL){free(pos->next);pos->next = NULL;return;}// 直接销毁  pos->next  会找不到 pos->next->next，先保存SLTNode* ptemp = pos->next->next;free(pos->next);pos->next = NULL;pos->next = ptemp;
}// 十一、销毁链表
void SLTDestory(SLTNode** pphead)
{assert(pphead);// 遍历销毁if (*pphead == NULL)return;SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}// 别忘了将 头指针销毁！！！*pphead = NULL;
}

test.c

#include"SList.h"void SLTest1()
{// 零、创建 链表SLTNode* plist = NULL;// 二、尾插法SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4); // 1 -> 2 -> 3 -> 4 -> NULLprintf("测试尾插：");SLTPrint(plist);// 三、头插法SLTPushFront(&plist, 5);SLTPushFront(&plist, 6); // 6 -> 5 -> 1 -> 2 -> 3 -> 4 -> NULLprintf("测试头插：");SLTPrint(plist);// 四、尾删法SLTPopBack(&plist);SLTPopBack(&plist); // 6 -> 5 -> 1 -> 2 -> NULLprintf("测试尾删：");SLTPrint(plist);// 五、头删法SLTPopFront(&plist);SLTPopFront(&plist); // 1 -> 2 -> NULLprintf("测试头删：");SLTPrint(plist);// 六、链表的查找SLTNode* FindRet = SLTFind(&plist, 2);printf("测试查找：");if (FindRet) printf("找到了\n");else printf("没找到\n");// 七、指定位置 pos 之前插入SLTNode* FindRet1 = SLTFind(&plist, 2);SLTNode* FindRet2 = SLTFind(&plist, 1);SLTInsert(&plist, FindRet1, 200);SLTInsert(&plist, FindRet2, 100);// 100 -> 1 -> 200 -> 2 -> NULLprintf("测试指定位置之前插入：");SLTPrint(plist);// 八、指定位置 pos 之后 插入（推荐！）SLTNode* FindRet3 = SLTFind(&plist, 2);SLTInsertAfter(FindRet3, 200); // 100 -> 1 -> 200 -> 2 -> 200 -> NULLprintf("测试指定位置之后插入：");SLTPrint(plist);// 九、删除 指定 pos 节点SLTNode* FindRet4 = SLTFind(&plist, 1);SLTErase(&plist, FindRet4);// 100 -> 200 -> 2 -> 200 -> NULLprintf("测试删除指定节点：");  SLTPrint(plist);// 十、删除指定 pos 之后 的节点SLTNode* FindRet5 = SLTFind(&plist, 200); // 注意如果 通过 Find 函数 找 节点，节点中有重复数据，返回 第一个遇到的SLTEraseAfter(FindRet5);// 100 -> 200 -> 200 -> NULLprintf("测试删除指定节点："); SLTPrint(plist);//
}
int main()
{SLTest1();return 0;
}

完。

若上述文章有什么错误，欢迎各位大佬及时指出，我们共同进步！