一、链表概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
1️⃣从上图可以看出逻辑上是连续的，而物理上就并不一定是连续的了
2️⃣现实中结点都是从堆上申请的，（有的书上结点也可能为节点意思是相同的，在这里也顺便介绍一下什么是前驱结点，后驱结点。例如：1、2、3、n、n+1中n+1是n的后驱结点，而n是n+1的前驱结点）
3️⃣因为是在堆上申请的空间，所以可能会出现二次申请空间可能，所以也就导致在物理上不是连续的。
二、链表的分类
链表一共分为三种结构，
带不带头，单向双向，循不循环。
由这三种结构可以组合八种，所以链表的分类为八种。
🐬：在下面就不全部介绍了，拿出两个经典也是最常用的来介绍一下无头单向非循环链表带头双向循环链表，在下面的图看上去带头双向循环链表可能看起来比较复杂，但是在我们实现的过程中会发现便不难，对比无头单向非循环，还是前者写起来比较舒服。
1️⃣ 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2️⃣ 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了
三、单链表的实现（无头单向不循环）
这里把单链表分为三个大部分分别是
1️⃣test.c：头文件用来测试单链表的功能。
2️⃣SLT.c：主要是用来单链表功能的实现
3️⃣SLT.h：用来放一些头文件，函数声明，结构体的创建。
1.SLT.c
1.1创建新的结点
创建新的节点，使用动态开辟空间，并对结点内的值进行初始化。
SLTNode* BuySLTNode(SLTDataType x)
{//创建新结点
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)//判断是否空间开辟成功
{
perror("malloc");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;//进行初始化
return newnode;
}
1.2插入n个连续的数
该函数的目的是插入n个连续的数，并不需要一个一个的插入，提供了便捷。在这里每插入一个数就开辟一个空间，这样并不会造成空间浪费，在这里并不能直接尾插，因为这并不是带头的链表，所以需要判断一下。
SLTNode* CreateSList(int n)//插入n个连续的数
{
SLTNode* phead = NULL;
SLTNode* ptail = NULL;
for (int i = 0; i < n; i++)
{
SLTNode* newnode = BuySLTNode(i);
if (phead == NULL)
{
//SLTNode* newnode = BuySLTNode(i);
phead = ptail = newnode;
}
else
{
ptail->next = newnode;
ptail = newnode;
}
}
return phead;
}
说一个我自己犯得错误，在创建新的结点的时候，因为上面是在循环当中创建的，我就认为BuySLTNode(i)中主要是i相同，就认为结点也就相同了，下面来看一下我当时错误的代码。❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌❌
SLTNode* CreateSList(int n)//插入n个连续的数
{
SLTNode* phead = NULL;
SLTNode* ptail = NULL;
for (int i = 0; i < n; i++)
{
if (phead == NULL)
{
//SLTNode* newnode = BuySLTNode(i);
phead = ptail = BuySLTNode(i);
}
else
{
ptail->next = BuySLTNode(i);
ptail = BuySLTNode(i);
}
}
return phead;
}
1.3数据打印
在这里尽量养成一个好习惯，不要直接使用形式参数，最好在重新创建一个变量来接收形参，尽管后面不会用到，也要尽量创建新的变量。
void SLTPrint(SLTNode* phead)
{//打印数据
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
1.4单链表尾插
在这里看到用的是二级指针，因为将头结点设为NULL指针了，在传参的时候（形参是实参的一份临时拷贝），所以再传一级指针的时候，改变形参的时候，并不会对头结点（实参）造成影响。所以采用二级指针的方法，或者采用返回值的方法（这里并不提倡用，太麻烦）到后来用带头的链表时这些问题就都不在了。
void SLTPushBack(SLTNode** phead, SLTDataType x)
{//单链表尾插
if (*phead == NULL)//判断头结点是否为NULL
{
*phead = BuySLTNode(x);
}
else
{
SLTNode* ptail = *phead;
while (ptail->next)
{
ptail = ptail->next;
}
ptail->next = BuySLTNode(x);
}
}
1.5单链表尾删
在尾删的情况下就要判断一下该链表是否为NULL，在NULL的情况下在删除也会出现错误。还要判断一下是否就只有头结点一个结点，如果是就可以直接释放头结点就可以了，因为是动态开辟的空间所以需要释放。
void SLTPopBack(SLTNode** phead)
{//单链表尾删
assert(*phead);
if ((*phead)->next == NULL)
{
free(*phead);
*phead = NULL;
}
else
{
SLTNode* ptail = *phead;
while (ptail->next->next)
{
ptail = ptail->next;
}
free(ptail->next);
ptail->next = NULL;
}
}
1.6单链表头插
void SLTPushFront(SLTNode** phead, SLTDataType x)
{//单链表头插
SLTNode* newnode = BuySLTNode(x);
if (*phead == NULL)
{
*phead = BuySLTNode(x);
}
else
{
SLTNode* ptail = *phead;
*phead = newnode;
(*phead)->next = ptail;
ptail = NULL;
}
}
1.7单链表头删
头删和尾删的过程是差不多的，记住要判断是否为NULL,为NULL就不能再删除了。
void SLTPopFront(SLTNode** phead)
{//单链表头删
assert(*phead);
if ((*phead)->next == NULL)
{
free(*phead);
*phead = NULL;
}
else
{
SLTNode* ptail = (*phead)->next;
*phead = ptail;
ptail = NULL;
}
}
1.8查找数据
查找数据，再找到就返回它当前的结点地址，如果没有找到就返回NULL
这里就不需要判断是否为NULL了,因为空也是可以查找的，同样也是没找到所以也返回空。
SLTNode* SLTFind(SLTNode* plist, SLTDataType x)
{//查找数据
SLTNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
1.9在指定位置后面插入
在这里指定的位置需要断言一下，不能为NULL，而在这段代码的下面是在指定位置插入的可以对比一下差别，当在当前位置插入时，指定位置为头结点时可以直接调用头插。
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{//指定当前位置后面删除
assert(pos);
SLTNode* newnode = BuySLTNode(x);
if (pos->next == NULL)
{
pos->next = newnode;
}
else
{
SLTNode* ptail = pos->next;
pos->next = newnode;
newnode->next = ptail;
newnode->data = x;
}
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{//指定位置插入
assert(pos);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* newnode = BuySLTNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
1.10指定位置删除
下面的两段代码分别是在指定位置后面删除，和删除指定位置。这里也是需要断言一下，并且释放被删除的空间，删除指定位置如果是删除头结点一样是可以调用头删。
void SLTEraseAfter(SLTNode* pos)//指定位置后面删除
{
assert(pos);
if ((pos->next) != NULL)
{
SLTNode* ptail = pos->next->next;
free(pos->next);
pos->next = ptail;
}
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{//指定位置删除
assert(pos);
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
}
free(pos);
}
1.11销毁数据
这里是将所有的数据都进行删除，全部释放，并且置为空，这里也是需要断言一下。
void SLTDestroy(SLTNode** pphead)
{
assert(*pphead);
if ((*pphead)->next ==NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
}
在最后简单的说一下为什么有的时候用二级指针，有的时候用一级指针，简单理解就是当你认为需要改变数据的内容时就用二级指针，比如添加数据和删除数据都是需要改变数据所以用二级指针，而打印和查找就只是调用数据并不修改所以用一级指针。
2.SLT.h
SLT.h中是一些头文件，结构体的生成，还有对功能函数的实现，对类型的自定义，因为在这里自定义会对后来如果改数据类型的时候有很大的方便。
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
//自定义
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//创建结构体
SLTNode* BuySLTNode(SLTDataType x);
//创建新的结点
SLTNode* CreateSList(int n);
//创建连续数据的链表
void SLTPrint(SLTNode* phead);
//打印数据
void SLTPushBack(SLTNode** phead, SLTDataType x);
//尾插
void SLTPopBack(SLTNode** phead);
//尾删
void SLTPushFront(SLTNode** phead, SLTDataType x);
//头插
void SLTPopFront(SLTNode** phead);
//头删
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 单链表查找
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 单链表在pos位置之后插入x
void SLTEraseAfter(SLTNode* pos);
// 单链表删除pos位置之后的值
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在pos之前插入x
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos位置
void SLTDestroy(SLTNode** pphead);
//销毁数据
3.test.c
下面就是对链表功能的一些测试。
#define _CRT_SECURE_NO_WARNINGS 1
#include"SLT.h"
int main()
{
SLTNode* SLT = CreateSList(5);
SLTPrint(SLT);
SLTPushBack(&SLT, 6);
SLTPrint(SLT);
SLTPopBack(&SLT);
SLTPrint(SLT);
SLTPushFront(&SLT,9);
SLTPrint(SLT);
SLTPopFront(&SLT);
SLTPrint(SLT);
SLTNode* SLF=SLTFind(SLT, 4);
if (SLF == NULL)
{
printf("没找到\n");
}
else
{
printf("找到了！\n");
}
SLTPrint(SLF);
SLTInsertAfter(SLF,9);
SLTPrint(SLT);
SLTNode* SLC = SLTFind(SLT, 9);
SLTEraseAfter(SLC);
SLTPrint(SLT);
SLTInsert(&SLT,SLT, 8);
SLTPrint(SLT);
SLTErase(&SLT,SLF);
SLTPrint(SLT);
SLTDestroy(&SLT);
SLTPrint(SLT);
return 0;
}
四、顺序表和链表的优缺点
顺序表的优点
1️⃣ 顺序表的内存空间连续,物理上一定连续。
2️⃣ 支持随机访问，可以高效的按下标进行操作，时间复杂度是O(1)。
3️⃣尾插、尾删效率较高，时间复杂度是O(1)。
顺序表的缺点
1️⃣在任意位置和头结点插入删除，效率低，要将数据向后移时间复杂度为O(N)。
2️⃣顺序表长度固定，有时需要扩容，扩容可能还会在成空间浪费。
链表的优点
1️⃣不用担心扩容问题，也不会造成空间浪费。
2️⃣链表的插入和删除操作的效率较高，可以把通过地址直接改变节点的指向。
3️⃣逻辑上连续，但物理上不一定连续。
链表的缺点
1️⃣链表不支持随机访问，查找元素效率低，需要遍历节点，时间复杂度是O(n)。
| 最后：文章有什么不对的地方或者有什么更好的写法欢迎大家在评论区指出 |