---

单链表概念

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表（单链表），单链表是链式存取的结构。

链接存储方法

链接方式存储的线性表简称为链表（Linked List）。 链表的具体存储表示为： ①
用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） ②
链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）
链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。
结点结构：

data域–存放结点值的数据域 next域–存放结点的直接后继的地址（位置）的指针域（链域）
链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，每个结点只有一个链域的链表称为单链表（Single Linked
List）。

头指针head和终端结点

单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。
终端结点无后继，故终端结点的指针域为空，即NULL。

链接过程

从逻辑上：

从物理上：

单链表的优缺点：

1、优点：

插入和删除操作方便，在单链表中，插入和删除节点时，只需修改相邻节点的游标即可，不需要移动大量数据，因此操作效率较高。适合动态存储，单链表可以随时插入和删除节点，因此适合动态存储数据。空间利用率高，单链表不需要连续的存储空间，因此可以更有效地利用内存空间。

2、缺点：

查找效率低，在单链表中，查找某个元素需要从头节点开始遍历整个链表，因此查找效率较低。
需要额外的空间存储游标，单链表需要额外的空间存储游标，这会增加内存空间的消耗。实现复杂度较高，相比数组等数据结构，单链表的实现复杂度较高，需要维护节点的引用关系。

实现

一.思路
1.利用结构体来储存数据和指针（结构体能够存储不同类型数据）
2.每增加一个数据就通过malloc函数来扩展一个空间
3.通过多文件的方式来实现
4.我们实现打印、扩容、尾插、头插、尾删、头删接口函数
二.框架
结构体创建、一些定义：

#include<stdio.h>
#include<stdlib.h>//动态内存函数的头文件
typedef int SLTDataType;//类型定义
struct SListNode
{SLTDataType data;//数据struct SListNode* next;//链接点
};
typedef struct SListNode SLTNode;//类型定义

主函数：

void  Test() {SLTNode* plist = NULL;//头指针初始化  因为开始是没有数据}
int main() {Test();//调用函数return 0;
}

三.接口函数的实现
1.打印函数：
（1）参数：结构体指针类型（接收头指针），由于不需要改变头指针，所以传一个头指针变量过来就行
（2）迭代：将后一个链接的指针变量 next 传给指针phead来找到下一个结点
代码实现：

void SListPrint(SLTNode* phead) {//打印函数//由于不需要改变头指针，所以传一个头指针变量过来就行了while (phead != NULL) {//将phead不是空指针之前的数据打印printf("%d->", phead->data);//打印数据phead = phead->next;//迭代}printf("NULL");//最后打印指向的NUll
}

2.扩容函数：
（1）我们通过malloc函数来实现扩容
（2）参数：插入的数据
（3）返回类型：返回扩建的空间指针变量
（4）过程：在扩容后将插入的数据存储到这个空间里。并把指针变量置空
代码实现：

SLTNode* uuu(SLTDataType x) {//扩容和储存数据SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;//储存数据newnode->next = NULL;//将扩容和的链接点置空return newnode;//放回这个空间的地址
}

3.尾插函数：
有两种情况：
（1）头指针为空，此时将扩建的第一个空间直接当头指针

（2）头指针不为空，此时将我们要通过头指针找到最后一个结点，再用这个结点来链接我们扩建的空间

注意：
1.在实现这个过程可能会改变头指针，所以传参需要使用传址调用
2.第二种情况不要改变头指针

代码实现：

void SListPushBack(SLTNode** pphead, SLTDataType x) {//尾插
//注意：这里需要传参需要进行传址调用SLTNode* newnode = uuu(x);//插入一个数据需要再创建一个新的空间if (*pphead == NULL)//判断是否是第一种情况*pphead = newnode;else{SLTNode* cat = *pphead;//防止头指针被改变while(cat->next!=NULL){//找到最后一个结点cat = cat->next;//迭代}cat->next = newnode;//将扩展的空间连接在最后一个结点的next上}
}

检查：
我们尾插 1、2

SListPushBack(&plist, 1);
SListPushBack(&plist, 2);
SListPrint(plist);

4.头插函数：
（1）我们直接将创建的空间的next与第一个结点连接即可

注意：在实现这个过程会改变头指针，所以传参需要使用传址调用
代码实现：

void SListPushFront(SLTNode** pphead, SLTDataType x) {头插SLTNode* newnode = uuu(x);//扩建空间newnode->next = *pphead;//与第一个结点连接即头指针*pphead = newnode;//将头指针改为头插的空间
}

检查：
我们头插一个 0

void  Test() {SLTNode* plist = NULL;SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushFront(&plist, 0);SListPrint(plist);
}

运行结果：

5，头删函数：
（1）这个我们不用创建新的空间但是要释放空间。释放函数 ferr（）
（2）我们可以创建一个新的指针变量来接收第一个结点的next（第二个结点的地址），然后将第一个结点释放掉，再然后将新的指针变量当作头指针
（3）在实现这个过程会改变头指针，所以传参需要使用传址调用
代码实现：

void SListPopFront(SLTNode** pphead) {//头删SLTNode* next = (*pphead)->next;//创建一个新的指针变量来接收第一个结点的next（第二个结点的地址）free(*pphead);//释放*pphead = next;//重新设置头指针
}

检查：
头删一个数据：

void  Test() {SLTNode* plist = NULL;SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushFront(&plist, 0);SListPopFront(&plist);SListPrint(plist);
}

运行结果：

6.尾删函数：
分三种情况：
（1）没有结点
返回NULL
（2）有一个结点
将其直接释放，并置空
（3）多个结点
我们要创建两个新的变量分别来找倒数第一和第二个结点，释放最后一个结点倒数，第二个结点next置空

代码实现：

void SListPopBack(SLTNode** pphead) {//尾删if (*pphead == NULL)//当为空是直接返回空return;else if ((*pphead)->next == NULL) {//只有一个结点时，直接释放掉pphead并将其置空free(*pphead);*pphead = NULL;}else {//多个结点SLTNode* cat = *pphead;//为了不改变头指针，创建一个新的变量SLTNode* cat1= NULL;//用于找到倒数第二个结点，最后将其next置空while (cat->next != NULL) {//找最后一个结点cat1 = cat;cat = cat->next;}free(cat);//释放最后一个结点cat1->next = NULL;//倒数第二个结点next置空}
}

检查：
尾删一个数据

void  Test() {SLTNode* plist = NULL;SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushFront(&plist, 0);SListPopFront(&plist);SListPopBack(&plist);		SListPrint(plist);
}

运行结果：

代码一览

SList.h：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>//动态内存函数的头文件
typedef int SLTDataType;//类型定义
struct SListNode
{SLTDataType data;//数据struct SListNode* next;//链接点
};
typedef struct SListNode SLTNode;//类型定义// 不会改变链表的头指针，传一级指针
void SListPrint(SLTNode* phead);// 可能会改变链表的头指针，传二级指针
void SListPushBack(SLTNode** pphead, SLTDataType x);//尾插
void SListPushFront(SLTNode** pphead, SLTDataType x);//头插
void SListPopFront(SLTNode** pphead);头删
void SListPopBack(SLTNode** pphead);//尾删

SList.c：

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"void SListPrint(SLTNode* phead) {//打印函数//由于不需要改变头指针，所以传一个头指针变量过来就行了while (phead != NULL) {//将phead不是空指针之前的数据打印printf("%d->", phead->data);//打印数据phead = phead->next;//迭代}printf("NULL");//最后打印指向的NUll
}SLTNode* uuu(SLTDataType x) {//扩容和储存数据SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;//储存数据newnode->next = NULL;//将扩容和的链接点置空return newnode;//放回这个空间的地址
}void SListPushBack(SLTNode** pphead, SLTDataType x) {//尾插SLTNode* newnode = uuu(x);if (*pphead == NULL)*pphead = newnode;else{SLTNode* cat = *pphead;while(cat->next!=NULL){cat = cat->next;}cat->next = newnode;}
}
void SListPushFront(SLTNode** pphead, SLTDataType x) {头插SLTNode* newnode = uuu(x);newnode->next = *pphead;*pphead = newnode;
}
void SListPopFront(SLTNode** pphead) {//头删SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}void SListPopBack(SLTNode** pphead) {//尾删if (*pphead == NULL)return;else if ((*pphead)->next == NULL) {free(*pphead);*pphead = NULL;}else {SLTNode* cat = *pphead;SLTNode* cat1= NULL;while (cat->next != NULL) {cat1 = cat;cat = cat->next;}free(cat);cat1->next = NULL;}
}

Test:

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"void  Test() {SLTNode* plist = NULL;SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushFront(&plist, 0);SListPopFront(&plist);SListPopBack(&plist);SListPrint(plist);
}
int main() {Test();return 0;
}

还有查改等没写，有兴趣的可以去试试哦
以上就是我的分享了，如果有什么错误，欢迎在评论区留言。
最后，谢谢大家的观看！