目录
一、链表的定义
二、创建一个节点
三、对链表进行头插
四、对链表进行头插
五、对链表进行头删
六、对链表进行尾删
七、对链表的打印
一、链表的定义
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
为了往后使用数据类型的变换，这里通过typedef 给int换了一个名字，后面我们要换其他的数据类型可以直接吧第一行的int换成你想要的类型。
结构体内data储存数据，next储存下一个节点的地址。
我们接下来创建一个节点。
二、创建一个节点
SLTNode* BuyNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)//当内存申请失败了需要报错并停止运行
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
return newnode;
}
我们需要用到一个SLTNode *类型的函数，因为我们要返回创建节点的地址。
这样我们就可以创建一个链表并在里面插入数据了
int main()
{
SLTNode* plist = NULL;
phead = BuyNode(1);
}
phead表示为头结点。
三、对链表进行头插
void PushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode *newnode=BuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
这里要注意的是，用到了二级指针，之所以要用二级指针是因为：我们需要改变phead的值，所以我们必须要把plist的地址传进来。
四、对链表进行头插
这里需要分情况讨论：1、链表非空。2、链表为空。
当链表非空的时候，我们只需要找到尾节点，然后接上新节点就可以了。
但当链表为空的时候，我们就要让头指针指向新节点（需要改变头指针phead），所以还是需要用到二级指针。
void SlistPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuyNode(x);
if (*pphead == NULL)
*pphead = newnode;
else
{
//找到尾节点
SLTNode* tail=*pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
五、对链表进行头删
这里我们设置了一个del变量储存将要删除的节点，每次删除节点我们都要free掉这个节点，不然会有内存泄露的风险。
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* del = *pphead;
*pphead = (*pphead)->next;
free(del);
del = NULL;
}
六、对链表进行尾删
void SListPopBack(SLTNode** pphead)
{
assert(pphead);
if (*pphead == NULL)
return;
//一个节点
//多个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
prev->next = NULL;
free(tail);
tail = NULL;
}
}
因为尾结点需要找到为节点的前一个节点，并将其next值设置为NULL，所以需要分情况讨论。
七、对链表的打印
void SLTPrint(SLTNode* phead)
{
if (phead = NULL)
return;
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULLn");
}
八、对链表的销毁
与上面的删除同理，链表的节点都是malloc出来的，养成好习惯，把每个malloc的空间的返回给系统避免资源浪费。
void SLTistDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
最后记得把phead指向NULL（也就是*pphead），避免野指针的产生。
九、对链表的查找注意它的返回类型是节点的指针型，在没找到节点时返回NULL。
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
if (phead == NULL)
return;
SLTNode* cur=phead;
while (cur)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
十、对链表某个数据前插入
我们需要通过上面的find函数，找到我们想在哪个元素前插入的位置（pos）。我们需要找到pos亲一个节点prev，然后再把新节点插入prev节点与pos节点之间。
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assrtt(pphead);
assert(pos);
if (*pphead == pos)
{
SListPopFront(x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
prev = prev->next;
SLTNode* newnode = BuyNode(x);
newnode->next = pos;
prev->next = newnode;
}
}
十一、对链表某个数据后插入
因为单向链表只能从前往后查找，所以我们需要从头结点一个个往下找，才能找到插入的位置。
但是如果你想在某个元素后面插入数据的话，只需要往下找一个就行了。
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* next = pos->next;
SLTNode* newnode = BuyNode(x);
newnode->next = next;
pos->next = newnode;
}
十二、对链表某个位置删除
需要分情况讨论，我这里用了两个指针，当链表只有一个元素的时候不需要两个指针，所以需要分情况讨论。
void SListErase(SLTNode **pphead,SLTNode* pos)
{
assert(pphead);
assert(pos);
SLTNode* prev=*pphead;
if (pos == prev)
{
*pphead = pphead->next;
free(pos);
pos = NULL;
}
else
{
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
思路就是把要删除位置的前一个（prev）找到，然后吧prev的next改成pos的next，最后释放pos
后续还会有更多细节补充
