在学习链表之前我们要看看前面的顺序表的缺陷：
1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
正是有这些缺陷，所以才会有链表来解决这些问题，接下来我们要学习的是单链表，单链表的缺陷也不少，等后续到双向循环带头链表的时候就能比较好的解决这些问题了
链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。
上述就是链表的形式，有一个数据再加一个指针进行维护，防止数据的丢失。
链表的分类
1. 单向或者双向 2 . 带头或者不带头 3. 循环或者非循环
根据排列组合我们可以知道，总共有8种链表，当然，我们只学习其中最简单和最复杂的结构，因为这样更有针对性；
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都 是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了。
这次我们就来实现单链表
链表的实现
先来看看接口
对于数据结构来说，一般我们主要抓住增删查改来展开学习。
首先从打印开始，我们只要遍历一次就可以打印
void SLTNodePrint(SLTNode* phead)//打印
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}SLTNode* BuySLTNode(SLTDatatype x)//创建节点
{
SLTNode* tmp = (SLTNode*)malloc(sizeof(SLTNode));
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
else
{
tmp->data = x;
tmp->next = NULL;
}
return tmp;
}头插头删尾插尾删：这里要传二级指针的原因是因为我们要改头节点，要改变一级指针我们就要传二级指针，而打印函数不会改变头节点，所以不需要传二级指针。
void SLTNodePushFront(SLTNode** pphead, SLTDatatype x)//头插
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;//处理没有数据的时候
}
else
{
//处理有数据
newnode->next = *pphead;
*pphead = newnode;
}
}
void SLTNodePopFront(SLTNode** pphead)//头删
{
assert(pphead);
assert(*pphead);//确保头部有数据可删
SLTNode* cur = *pphead;
*pphead = (*pphead)->next;
free(cur);
cur = NULL;//养成好习惯，free了之后置为空指针
}
void SLTNodePushBack(SLTNode** pphead, SLTDatatype x)//尾插
{
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;//没有数据
}
else
{
SLTNode* cur = *pphead;
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = newnode;
}
}
void SLTNodePopBack(SLTNode** pphead)//尾删
{
assert(pphead);
assert(*pphead);//防止没有数据的时候也删除
if ((*pphead)->next == NULL)//只有一个头节点
{
free((*pphead)->next);
*pphead= NULL;
}
else
{
//多个节点
SLTNode* cur = *pphead;
while (cur->next->next != NULL)
{
//这里要保证前一个节点的地址要有
//才能删下个节点，并链接下下个节点
cur = cur->next;
}
free(cur->next);
cur->next = NULL;
}
}下面是链表的销毁：因为链表存在链接关系，如果没有指针进行维护，链表就没有办法再链接起来，导致数据的丢失。
void SLTNodeDestroy(SLTNode** pphead)//链表销毁
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;//记录下一个节点，防止找不到
free(cur);
cur = next;
}
*pphead = NULL;
}查找：
SLTNode* SLTNodeFind(SLTNode* phead, SLTDatatype x)//查找
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}实现了查找其实也实现了修改，一节对任意地方的插入删除也更加方便了：以下就是通过查找后实现修改
void test3()
{
SLTNode* plist = NULL;
SLTNodePushBack(&plist, 1);
SLTNodePushBack(&plist, 2);
SLTNodePushBack(&plist, 3);
SLTNodePushBack(&plist, 4);
SLTNode* pos = SLTNodeFind(plist, 2);
if (pos)
{
pos->data *= 30;//这里相当于实现了改数据
printf("找到了%d\n",pos->data);
}
else
{
printf("找不到\n");
}
SLTNodePrint(plist);
}从数据前面插入或者删除数据还是比较麻烦的，但由于前面插入的需求也比较大，所以要必要实现：
void SLTNodeInsert(SLTNode** pphead, SLTDatatype x,SLTNode* pos)
{
//从x的前面插入数据
assert(pphead);
SLTNode* newnode = BuySLTNode(x);
if (*pphead == pos)
{
SLTNodePushFront(pphead, x);//头插
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
assert(prev);//防止pos传错，传成空指针，会导致死循环
}
newnode->next = prev->next;
prev->next = newnode;
}
}
void SLTNodeErase(SLTNode** pphead, SLTNode* pos)
{
//pos前删除
assert(pphead);
assert(*pphead);//防止删空
if (*pphead == pos)
{
SLTNodePopFront(pphead);//头删
}
else
{
SLTNode* prev = *pphead;
while (prev->next->next != pos)
{
prev = prev->next;
}
free(prev->next);
prev->next = pos;
}
}从pos的后一个位置进行插入或者删除比较简单，这里就不多赘述：直接上代码
void SLTNodeInsertAfter( SLTDatatype x, SLTNode* pos)
{
//在x的后面插入数据
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;//这两部不能反，否则无法链接起来
pos->next = newnode;
}
void SLTNodeEraseAfter(SLTNode* pos)
{
//pos之后删除
assert(pos->next);//防止没有后一个
SLTNode* tail = pos->next;
pos->next = tail->next;
free(tail);
tail = NULL;
}在最后要说明的是单链表其实不适合存储数据，只是作为其他数据结构的子结构，但是，对于面试来说，单链表非常重要，因为对于双向循环带头链表来说，结构比较完善，没什么值得考的，所以考察单链表更加考验我们的能力。