链表链表节点设计链表项目链表中的传址调用检查申请空间链表尾插链表头插链表尾部删除链表头部删除链表的查找指定位置之前插入指定位置之后插入数据删除指定位置（节点）数据删除指定位置（节点）之后的数据链表的销毁
前面学习了顺序表，在顺序表中，虽然可以用动态内存开辟的方法来灵活改变空间大小，但顺序表本身仍然存在着一些局限性：
头插/尾插中，每插入一次数据，其它数据要提前挪动以空出空间。开辟空间是以现有空间的倍数进行的，一般为2~3倍。而随之带来空间和时间两个方向上的问题：
数据频繁地挪动需要占用时间和性能。空间开辟后还是会不可避免的浪费。链表概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针（也叫节点、结点）链接次序实现的。
节点节点组成部分：
数据（实际往往是运用 / 保存指针）指向下一个节点的指针定义链接的节点结构：
struct SlistNode //single list node 单链表
{
int data;
struct SlistNode* next;
};
设计链表项目文件有
源文件：Slist.c、test.c头文件：Slist.h链表中的传址调用链表中，经常会出现函数传值调用的错误。 如图，想要改变链表plist，就要传址操作。而其本身就是地址，因此函数的参数类型应该是二级指针。
链表的创建是下面这两行代码，创建数据和指向下一个节点的指针。数据要开辟空间，所以内容使用指针接收。
SN* Node1 = (SN*)malloc(sizeof(SN));
Node1->Data = 21;
检查申请空间在对链表进行操作（尤其是增删）的时候，要先对空间进行检查，防止内存溢出或者越界访问。 此函数，申请成功返回新节点，失败报错。
SN* Creat_newlistNode(DataType i)
{
SN* newNode = (SN*)malloc(sizeof(SN));
if (newNode == NULL)
{
perror("malloc");
exit(1);
}
newNode->Data = i;
newNode->next = NULL;
return newNode;
}
此函数真正使用如下：
SN* newNold = Creat_newlistNode(i);
//创建一个保存数据i的链表。
链表尾插先考虑非空链表 链表尾插，遍历链表找尾，将要插入的节点放到最后。 接着，要考虑无法遍历的情况——空链表。 以上思路完成后，考虑将代码更为严谨、完善。如指针的合法等。 最后进行最终的测试。（每完成一个功能，也就应该测试一次。）
void SNPushBack(SN** pphead, DataType i)
{
assert(pphead);
SN* new = Creat_newlistNode(i);
assert(new);
//空链表和非空链表
if (*pphead==NULL)
{
*pphead = new;
}
else
{
SN* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
ptail->next = new;
}
}
链表头插现申请一个新的节点newnold。 将新节点和原有链表连接起来，并且新节点将作为头结点使用。
void SNPushFront(SN** pphead, DataType i)
{
assert(pphead);
SN* newNold = Creat_newlistNode(i);
newNold->next= *pphead;
*pphead = newNold;
//空链表、非空链表都需要考虑（此代码两者都已通过）
}
链表尾部删除链表的尾删，分为两个方向考虑：存在一个节点、存在多个节点。 判断一个节点时，直接删除 多个节点时，循环找到最后一个（并且保留前一个），然后删除并将保留的那个指针指向置为空。
void SNPopBack(SN** pphead)
{
assert(pphead &&
*pphead);
//分为只有一个节点、多个节点
if ((*pphead)->next == NULL)// -> 优先级高于 *
{
free(*pphead);
*pphead = NULL;
}
else
{
SN* ptail = *pphead;
SN* prev = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}
链表头部删除头删只需要将链表指向改为下一个（在更改指向前创建临时变量保存）， 后使用临时变量释放掉第一个节点的空间。 最后一步是测试，多个节点、一个节点是否有问题。
void SNPopFront(SN** pphead)
{
assert(pphead&&
*pphead);
SN* tmp = (*pphead)->next;
free(*pphead);
*pphead = tmp;
}
链表的查找链表的修改，只需遍历寻找即可。 由于查找不涉及链表修改，因此函数参数的形参为一级指针。 往后遍历直到找到即可：
SN* FindSN(SN* phead, DataType i)
{
assert(phead);
SN* tmp = phead;
while (tmp)
{
if (tmp->Data == i)
{
return tmp;
}
tmp = tmp->next;
}
return NULL;
}
在此函数的使用时，不要给参数带上 & 符号！！！（链表节名本身就是地址类型不可再乱加&）
void test3()
{
SN* one = NULL;
SNPushBack(&one, 99);
SNPushBack(&one, 88);
SNPushBack(&one, 77);
SNPushBack(&one, 66);
SNPushBack(&one, 55);
SNPushBack(&one, 44);
SNPrint(one);
SN* find=FindSN(one, 66);
//注意此时不涉及改变不需要使用 & 符号
if (find==NULL)
{
printf("找不到");
}
else
{
printf("可以找到%d", find->Data);
}
}
指定位置：使用上面用于查找链表的函数，返回值即是这个位置
指定位置之前插入首先考虑正常情况的多个节点。 链表中，只能由前找后，不能从后找到前。 因此确立分清三个节点：插入节点之前的节点，插入的节点，指点位置的节点。 创建插入的节点后，建立三个结点之间的联系。 再考虑特殊情况（只有一个节点的时候） 此时插入原理就是头插。 不需考虑无节点情况。
void SNInsert(SN** pphead, SN* pos, DataType i)//指定位置之前插入数据
{
assert(*pphead);
assert(pphead);
SN* NewNold = Creat_newlistNode(i);
//分为一个节点、多个节点
if (*pphead == pos)
{
SNPushFront(pphead,i);
}
else
{
SN* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = NewNold;
NewNold->next = pos;
}
}
指定位置之后插入数据参数只需要指定的位置和数据即可。
void SNInsertAfter(SN* pos, DataType i)
{
assert(pos);
SN* NewNold = Creat_newlistNode(i);
NewNold->next = pos->next;
pos->next = NewNold;
}
需要特别提出来说明的是，这两句代码的顺序问题。
NewNold->next = pos->next;
//1
pos->next = NewNold;
//2
如果顺序颠倒，先进行
pos->next = NewNold;
//2
再进行
NewNold->next = pos->next;
//1
造成的结果等价于NewNold->next = NewNold，这个代码将会自己指向自己。
删除指定位置（节点）数据指定位置删除数据，先考虑正常多节点情况 依旧需要弄清楚：删除位置之前的节点、删除位置的节点、删除位置之后的节点。 使用循环找到删除位置之前的节点，然后与后面的节点建立连接。 此时链表之中已不存在要删除的节点，但是空间没有释放一定要释放空间。
我们会发现，如果是一个节点，我们要指定位置删除。 代码并不适用。 所以要分情况来执行代码，使用 if 语句将两种情况分开讨论。 一个节点，指定位置删除的操作其实就是头删。拷贝或调用函数都可以。
void SNErase(SN** pphead, SN* pos)//指定位置删除数据
{
assert(pphead &&
*pphead);
assert(pos);
if (pphead == pos)
{
(*pphead)->next = NULL;
//或者头删函数也行
//SNPopFront(pphead);
}
else
{
SN* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
删除指定位置（节点）之后的数据删除指定位置之后的数据，思路如下：
保存这个数据（指定位置之后的数据的位置）链表重新建立连接（这一步完成后，链表中将不存在指定位置之后的>数据）根据预先保存的数据找到被删除的数据，将其从内存中删除。
void SNEraseAfter(SN* pos)
{
assert(pos && pos->next);
// -> 优先级大于 &&
SN* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
在测试时，出现了错误，记录下来：
在测试指定位置删除时，使用findSN函数找到位置find，然后删除了这个位置的节点。后面又想测试指定位置之后删除，可是find这个位置的节点已经被删除，所以无法找到find，更无法找到find后面的节点了。
链表的销毁链表是一个一个创建的，销毁也是一个一个的销毁。 思路是：创建两个指针，一个指针销毁节点使用，一个指针保存下一个节点。循环直到链表结束。
void DestorySN(SN** pphead)
{
assert(pphead &&
*pphead);
SN* pcur = *pphead;
while (pcur)
{
SN* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}
以上就是我对于单链表的学习记录了，单链表的理论到此结束。