文章目录
前言
为什么存在链表？因为顺序表存在一定问题，需要优化，而链表可以将顺序表的这些问题优化。
顺序表的问题：
- 中间/头部的插入删除，时间复杂度为O(N)
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到
200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
一、单链表的概念及结构
链表概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
单链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
注意：
1.链式结构在逻辑上是连续的，在物理结构上不一定连续，也就是说实际上链表是没有那个箭头的连接的，只是结点的指针域存储着下一个结点的地址（结构体变量的地址），才得以在逻辑上是连续的。
2.结点，即一个结构体变量，一般是在堆上申请，在堆上申请的空间，是操作系统按一定的策略来分配的，两次动态开辟的空间可能连续，也可能不连续。
3.结点包括数据域和指针域，假设在32位系统上，结点的值域为int类型，则一个结点的大小为8个字节（指针变量的大小是4个字节）。
4.最后指向NULL
二、单链表的实现
1.单链表初始化
void TestSList()
{
//单链表一般不需要初始化
//头结点一般没有数据域，只有指针域为null
SLTNode* pList = NULL;
SListPrint(pList);
}
2.单链表打印
void SListPrint(SLTNode* phead)
{
//这里不需要断言，因为phead有可能是空指针的
//创建结构体辅助指针cur
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;//cur->next存的是下一个结点的地址,这样操作cur就从逻辑上移到下一个结点了
}
printf("NULL\n");
}
3.创建结点
//创建新结点
//返回类型为SLTNode*，即新的结点的地址
SLTNode* BuyNewnode(SLTDataType x)
{
//创建结点:结点是在堆区创建的，这样出函数后，才不会被销毁
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
{
perror("mallo fail");
exit(-1);//exit(0)表示程序正常退出；除了0之外，其他参数均代表程序异常退出，如：exit(1),exit(-1)。
//但是在函数中就会有所区别，return会跳出函数，而exit会结束程序。
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
4.单链表头插
//单链表头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
//SLTNode newnode;我们不能定义局部变量的结构体结点，因为它出了作用域就销毁了
SLTNode* newnode = BuyNewnode(x);
newnode->next = *pphead;//phead接收的是pList的地址
*pphead = newnode;
}
头插测试
5.单链表尾插
//单链表尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
//传过来的是pList的地址，不是pList的值，所以可以断言
assert(pphead);
//尾插前要创建新结点
SLTNode* newnode = BuyNewnode(x);
//1.空
if (*pphead == NULL)//即pList为NULL，还没创建新结点
{
//这里要注意一点：
//*pphead就是pList，pList是指针，指针就是地址
//也就是说pList就是下一个结点的地址
*pphead = newnode;
}
//2.非空
//(1)先找到最后一个结点,特征是指针域为NULL
else
{
SLTNode* tail = *pphead;//第一个结点的地址
while (tail->next != NULL)
{
tail = tail->next;
}
//当tail->next==NULL时
//连接新的结点的地址
tail->next = newnode;
}
}
尾插测试
6.单链表头删
//头删
void SListPopFront(SLTNode** pphead)// 传pList的地址过来
{
assert(pphead);
//有可能删到最后，pList为NULL，就不能头删
assert(*pphead != NULL);
//保留头结点的地址
SLTNode* del = *pphead;
//让pList指针保存删除的头结点的下一个结点的地址
*pphead = (*pphead)->next;
//释放被头删的结点
free(del);
del = NULL;
}
7.单链表尾删
注意要分为一个结点和多个结点的情况
//尾删
void SListPopBack(SLTNode** pphead)
{
assert(*pphead);
//目标：找到尾部的结点
//释放尾部结点的空间
//让尾部结点的上一个结点的指针域为NULL
//只有一个结点的情况
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//写法1:只使用于有两个及两个以上的结点
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
prev->next = NULL;
free(tail);
tail = NULL;
}
写法2：
//SLTNode* tail = *pphead;
//while (tail->next->next != NULL)
//{
// tail = tail->next;
//}
//free(tail->next);
//tail->next = NULL;
}
8.单链表销毁
注意有可能有结点，有可能没有结点
//销毁链表
void SListDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
9.单链表查找
//链表的查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;//返回结点地址
}
cur = cur->next;
}
//找不到返回空指针
return NULL;
}
测试结果
10.单链表插入
注意一定要先用单链表查找函数找到位置为pos的结点
特殊情况：要插入位置的是第一个结点
在pos之前插入
//链表插入:在pos之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//在pos之前插入你
{
assert(pphead);
assert(pos);//要在pos的位置插入，所以pos不能为空
//要插入的是第一个位置
if (pos == *pphead)
{
SListPopFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
//找到pos的位置，和pos之前的结点prev的地址
while (prev->next != pos)
{
prev = prev->next;
//暴力检查：pos是否为NULL
assert(prev);
}
//创建一个新结点
SLTNode* newnode = BuyNewnode(x);
prev->next = newnode;
newnode->next = pos;
}
}
在pos之后插入
//在pos之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuyNewnode(x);//先创建一个新结点
newnode->next = pos->next;
pos->next = newnode;
}
11.单链表删除
//删除pos的位置
void SListDele(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
//删除的是第一个结点
if (*pphead == pos)
{
//调用头删
SListPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
//找pos
while (prev->next != pos)
{
prev = prev->next;
//检查pos是否存在
assert(prev);
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
删除pos后面的位置
//删除pos后面的位置
void SListDeleAfter(SLTNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;
}
else
{
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
}
}