🐸一、前言
终于放假啦！🤩🤩停更了两个月，在假期要把欠下的补回来&有规律的学习！🤓
本篇文章来自《数据结构与算法》 专栏，本篇的内容是单链表的学习，也是数据结构的基础，希望烙铁们可以理解消化哦🥰！！！
🐸二、单链表与顺序表的区别
🐵1.存储形式上的区别
顺序表 在物理上和逻辑上都是连续的
单链表 在物理上是不连续的，在逻辑上是连续的
🐵2.空间上的区别
顺序表一般有固定的空间大小，当空间不够时需要进行扩容，扩容时往往不能准确知道需要扩容的空间大小，很容易会造成空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
单链表 用一个空间申请一个空间，相比顺序表不那么浪费空间（并不是完全不浪费）
总结 ：在存储数据时，如果知道具体空间大小，就用顺序表进行存储，不知道具体空间大小，就用单链表
🐵3.时间上的区别
1️⃣随机插入、删除元素的时间复杂度：
顺序表：时间复杂度为 O(n)，因为其空间是连续的，在某个位置插入时，这个位置后面的元素都要往后挪动位置；
单链表：时间复杂度为 O(1)，只需要改变前驱元素及插入删除元素的指向；
2️⃣查找指定元素，修改指定位置元素的时间复杂度：
顺序表：时间复杂度为 O(1)，依靠下标直接可以找到指定元素，对其操作；
单链表：时间复杂度为 O(n)，需要从链表头结点往下遍历；
🐸三、单链表详解
🍎创建单链表
🥰这里先创建三个文件：
1️⃣：SList.h文件，用于函数的声明
2️⃣：SList.c文件，用于函数的定义
3️⃣：Test.c文件，用于测试函数
建立三个文件的目的： 将单链表作为一个项目来进行编写，方便我们的学习与观察。
⭕接口1：定义结构体（SLTNode）
🥰请看代码与注释👇
//自定义类型 typedef int SLTDataType; //创建单链表 typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;
⭕接口2：打印（SLTPrint）
🥰请看代码与注释👇
//打印 void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur != NULL) { printf("%d-> ", cur->data); cur = cur->next; } printf("NULL\n"); }
⭕接口3：释放（SLTDestroy）
🥰请看代码与注释👇
//释放 void SLTDestroy(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
⭕接口4：创建新结点（BuyLTNode）
🥰请看代码与注释👇
//创建新结点 SLTNode* BuyLTNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("mallic fail"); return; } newnode->data = x; newnode->next = NULL; return newnode; }
⭕接口5：头插（SLTPushFront）
🥰请看代码与注释👇
//头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); //链表为空，pphead也不为空，因为他是头指针plist的地址 // *pphead 不能断言，链表为空，也需要能插入 SLTNode* newnode = BuyLTNode(x); newnode->next = *pphead; *pphead = newnode; }
⭕接口6：尾插（SLTPushBack）
🚨主要思想就是 找尾,要注意尾插有两种情况：空链表和非空链表
很多烙铁容易找错，这里要找的是尾结点，而不是空
尾结点（tail）：next为空的
🥰请看代码与注释👇
//尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuyLTNode(x); //1.空链表 //2.非空链表 if (*pphead == NULL) { *pphead = newnode; //改变的结构体的指针plist（用结构体指针的地址） } else { SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; //改变的结构体尾结点 } }
