一. 为什么使用链表
1.1顺序结构的缺点
在我们的顺序表结构中 有以下这么几个缺陷
1 空间不够了 需要扩容 扩容是有消耗的
2 头部或者中间位置的插入删 除 需要挪动 挪动数据也是有消耗的
3 避免频繁扩容 依次一般都是按倍数去扩 容易造成空间浪费
我们来举几个例子来论证上面三点
首先 空间不够需要扩容 这个大家没有疑问的吧
其次 头部和中间位置插入数据的时候 因为顺序表是连续存储的
所以说想要插入前面的位置的时候 后面的数据就必须要向后挪动
最后 我们如果说 不按照倍数来扩容的话 可能会更加频繁的扩容
会造成时间和效率上的浪费
按照以空间换时间的思路 还是按倍数 扩容这种解决方法更加优秀一点
1.2 链表的诞生及优点
为了解决以上顺序表的缺点 我们设计出了链表
链表的优点有
1 按需申请空间 不用了就释放空间（更合理的使用空间）
2 头部中间插入删除数据 不需要挪动数据
但是链表其实也是有缺点的
1 每一个数据 都要存一个指针去链接后面的数据节点
2 不支持随机访问
（这里简单解释下随机访问 其实就是能够通过下标直接访问第i个 然而顺序表就支持随机访问 ）
这里画个图简单对比下两种数据结构
所以说 这里我们就能得出一个结论
顺序表和链表并不是对立的关系 而是互补的关系
二. 链表的接口函数实现
2.1 类型定义
还是和顺序表那一节一样 咱们先来定义类型
struct SLlist
{
int x;
struct SList* next;
};
首先因为咱们这个链表储存的类型可能不是整型类型的数据
为了防止以后改来改去 我们首先先使用typedef定义一个类型
如果我们以后想要储存其他类型的数据 只需要改变一行就可以了
代码表示如下
typedef int SLType;
typedef struct SLlist
{
SLType x;
struct SList* next;
}SL;
创建一个结构体变量
SL a1;
2.2 遍历（打印）
首先直接上代码
void SListPrint(SL* phead)
{
SL* cur = phead;
while (cur!=NULL)
{
printf("%d-> ", cur->date);
cur = cur->next;
}
}
我们这里画图给大家解释一下
phead是一个指针 它指向着第一个链表数据
第一它可以访问结构体中的date数据 可以对这个数据进行
打印 修改等操作
第二 它可以访问结构体中的next指针 而这个指针指向第二个数据
它可以通过这个指针修改自身指向的位置 从而找到链表第二
个数据
2.3 尾插数据
首先我们要尾插数据 我们首先要找到尾在哪里
我们观察图可以发现 尾部的数据跟其他的数据有一个明显的
区别就是它最后的指针指向NULL
我们可以写出以下代码
void SListPushBack(SL* phead, SLType x)
{
SL* newnode = (SL*)malloc(sizeof(SL));
newnode->date = x;
newnode->next = NULL;
//找到尾节点
SL* tail = phead;
while (tail->date!=NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
但是呢 只写下这段代码的话 可能会出现一些bug
如果一开始一个数据都没有phead指向空呢？
这样子的话 下面这一段代码是不是就会出问题了
// 空指针无法指向next
while (tail->date!=NULL)
{
tail = tail->next;
}
tail->next = newnode;
所以说呢 我们还要判断下phead是不是空指针
如果是空指针 我们还要先给它赋值
加上这一行代码
if (phead==NULL)
{
phead = newnode;
}
但是我们想想 这样子真的能成功嘛？
我们可以来实验一下
调试以下代码
void test1()
{
SListPushBack(PList,1);
SListPrint(PList);
}
int main()
{
test1();
return 0;
}
我们可以发现 虽然说phead指针指向的位置改变了 但是说PList指向的位置没有变
这就是形参和实参的区别 想要具体了解的同学可以看看这两篇博客
所以说呢 我们要想改变PList的值 我们必须要将它的地址传进去
这样子我们就需要用二级指针来接受
我们改变以上代码和传参方式
void SListPushBack(SL** pphead, SLType x)
{
SL* newnode = (SL*)malloc(sizeof(SL));
newnode->date = x;
newnode->next = NULL;
if (*pphead==NULL)
{
*pphead = newnode;
}
//找到尾节点
else
{
SL* tail = *pphead;
while (tail->date != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
然后打印试试
我们发现就可以完美运行
2.4 头插
这里我们只需要改变两个数据
一个是新链表的next
一个是phead指向的位置
void SListPushFront(SL** pphead, SLType x)
{
SL* newnode = (SL*)malloc(sizeof(SL));
newnode->date = x;
newnode->next = NULL;
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
newnode->next = *pphead;
*pphead = newnode;
}
}
这里需要注意的是 其实不需要加if判断也可以
这里为了增加代码的可读性我就写上
2.5 尾删
我们要做到尾删的话首先要找到最后一个数据存储的空间 然后将它释放掉
类似这样子操作
但是呢 这样子就会出现一个问题
前面一个数据的next还是指向这一片空间 这就形成了经典的野指针问题
为此我们就必须要使用一个指针储存tail的上一个值
这样子在tail找到最后一个数据的时候 pre就能够找到倒数第二个数据的位置
代码表示如下
void SListPopBack(SL** pphead, SLType x)
{
SL* pre = NULL;
SL* tail = *pphead;
while (tail->next)
{
pre = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
pre->next = NULL;
}
结果表示如下
void test1()
{
SListPushBack(&PList,1);
SListPushBack(&PList, 2);
SListPushBack(&PList, 3);
SListPushBack(&PList, 4);
SListPushBack(&PList, 5);
SListPushFront(&PList,1);
SListPushFront(&PList, 2);
SListPushFront(&PList, 3);
SListPushFront(&PList, 4);
SListPushFront(&PList, 5);
SListPrint(PList);
printf("\n");
SListPopBack(&PList);
SListPopBack(&PList);
SListPopBack(&PList);
SListPrint(PList);
}
int main()
{
test1();
return 0;
}
当然这种方法也是有问题的 如果说只有一个节点 这是偶tail指向的next本来就是空
而这个时候pre再对空指针进行解引用 （也是一个明显的野指针错误）
所以说我们要分类讨论
代码表示如下
void SListPopBack(SL** pphead, SLType x)
{
assert(*pphead);
if ((*pphead)->next==NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SL* pre = NULL;
SL* tail = *pphead;
while (tail->next)
{
pre = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
pre->next = NULL;
}
}
报错显示如下
2.6 头删
对比来说头删就简单很多了
我们也来分类讨论
当然这里23情况其实对于头删来说是一样的
代码表示如下
void SListPopFront(SL** pphead)
{
assert(*pphead);
SL* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
结果如下
以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏
希望大佬们看到错误之后能够不吝赐教 在评论区或者私信指正 博主一定及时修正
那么大家下期再见咯