目录
为什么有了顺序表，还需要有链表这样的数据结构呢？
顺序表的问题：
1，中间/头部的插入删除，时间复杂度为O(N)
2，增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗
3，增容一般是呈2倍的增长，势必会有一定的空间浪费，例如当前容量为100，满了以后增容到200，我们再继续插入5个数据，后面没有数据插入了，那么久浪费了95个数据空间
链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
下面实现一个简单的链表：
注意：
1.链表结构在逻辑上是连续的，但是在物理上不一定连续
2.现实中的结点一般都是从堆上申请出来的
3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续,也可能不连续
尾插：
注意：这里用二级指针，因为要改变phead，不改变就传一级
当链接是空的时候，就有可能改变phead
//创建一个新的结点
SLTNode* BuyListNode(SLTDataType x)
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
if (node == NULL)
{
printf("malloc fail\n");
exit(-1);
}
node->data = x;
node->next = NULL;
return node;
}
void SListPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
assert(pphead);//头指针有可能为空，头指针地址不能为空
if (*pphead == NULL)
{
SLTNode* newnode = BuyListNode(x);
*pphead = newnode;
}
else
{
//找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
SLTNode* newnode = BuyListNode(x);
tail->next = newnode;
}
}头插：
思路分析：
void SlistPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
//思考：如果链表为空，头插这样会不会出问题
}尾删：
void SlistPopBack(SLTNode** pphead)
{
assert(pphead);
SLTNode* tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
free(tail);
tail = NULL;
}如上会出现什么问题呢？
当最后一个删掉，倒数第二个就变成尾了
如下提供2种解决方案：
void SlistPopBack(SLTNode** pphead)
{
assert(pphead);
SLTNode* tail = *pphead;
//方法1：
//while (tail->next->next!=NULL)
//{
// tail = tail->next;
//}
//free(tail->next);
//tail->next = NULL;
//方法2：
SLTNode* prev = NULL;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}思考上面会出现什么问题？
当没有结点的时候，报错！
当只有一个结点的时候，plist没有置为NULL
assert(pphead);
//没有结点断言报错---处理方式较为激进
assert(*pphead);//链表为空，还在调用尾删
/*if (*pphead == NULL)
{
return;
}*/
//1,一个结点
//2,多个结点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
SLTNode* prev = NULL;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}头删：
void SlistPopFront(SLTNode** pphead)
{
//plist一定有地址，所以pphead不为空
assert(pphead);
//1.链表为空
assert(*pphead);
//2.只有一个结点
//3.多个结点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* node = (*pphead)->next;
free(*pphead);
*pphead = node;
}
}思考如何进行优化？——可以直接进行合并
void SlistPopFront(SLTNode** pphead)
{
//plist一定有地址，所以pphead不为空
assert(pphead);
//1.链表为空
assert(*pphead);
//2.只有一个结点
//3.多个结点
SLTNode* node = (*pphead)->next;
free(*pphead);
*pphead = node;
}计算大小：
int SListSize(SLTNode* phead)
{
int size = 0;
SLTNode* cur = phead;
while (cur != NULL)
{
size++;
cur = cur->next;
}
return size;
}
bool SListEmpty(SLTNode* phead)
{
return phead == NULL;
}
查找 & 在pos位置之前去插入x:
//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
}
//在pos位置之前去插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SlistPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuyListNode(x);
newnode->next = pos;
prev->next = newnode;
}
}思考：如果在其pos后插入会不会简单一点？
注意点：注意顺序！
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}单链表不适合在pos位置之前插入，因为需要找前一个位置，更适合在之后的位置插入！
删除pos位置的数&删除pos位置的下一个数：
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
//1.头删
//2.后面结点的删除
if (pos == *pphead)
{
SlistPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
next = NULL;
}