目录
一.链表概念
链表是线性表的一种，与顺序表不同的是，链表在物理存储结构上不连续，在逻辑结构上连续。链表中数据元素的逻辑结构是通过指针链接实现的。
链表的结构跟火车车厢类似，链表的每一个节点都是独立的，如同火车的车厢一样，火车的车厢可随时进行拆卸，链表的单独一个节点也是可随时根据需求进行创建和销毁。所有车厢可以链接成一个整体，链表的节点也是，通过一个个指针将各个节点链接。
如此，那么一个节点的结构体类型就能进行定义了， 该节点需要包含两个内容：数据data和指向下一个节点的指针next。当然存储的数据是何种类型由需求而定，在此重命名SLTdatatype为数据类型。定义SLTNode结构体类型，包含data和next。
下图就是链表的整体结构示意图，每一个节点都有自己的地址，并且每一个节点内又有下一个节点的地址，最后一个节点指向NULL，在此还需一个火车头，即结构体指针plist储存第一个节点的地址，如此就能形成环环相扣的链表。
二.链表实现
1.创建新节点
使用malloc函数创建新节点并用newnode接收节点地址，判断是否开辟成功后进行赋值，value是创建时输入的值，将其赋值到data中，而next指向哪暂且不清（看是尾插还是头插），创建时就仅设置为NULL，随后返回该节点地址。
//创建新节点
SLTNode* SLTBuynode(SLTdatatype value)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
//判断是否开辟成功
if (newnode == NULL)
{
perror("malloc");
exit(1);
}
newnode->data = value;
newnode->next = NULL;
return newnode;
}2.打印链表
从头开始打印链表，因此需要传入第一个节点的地址（此处用cur接收），打印该节点的data后使cur等于该节点的next，如此cur就指向了下一个节点，重复执行知道最后一个节点，其next为NULL，即cur为NULL时停止。
//打印链表
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}3.尾插、头插
在尾插中首先考虑一种特殊情况，即链表为空的情况。链表为空的话，尾插的节点就是第一个节点了，那么之前提到的火车头（指向第一个节点的指针plist）就要由指向NULL改为指向新节点地址了。这种情况需要在函数内修改一个指针的值，那么需要传什么类型的参数呢？当然是二级指针，在函数内修改一个int类型的值就需要传int*，现在修改一级指针必然就该传参二级指针，就是一个经典的易错点。
再考虑普遍情况，链表不为空，这时就需要找到最后一个节点，用ptail循环进行寻找，找到后将之前最后一个节点的next改为新节点地址即可，新节点中的next在创建时已经置为NULL了。
头插更为简单，只需要修改原本指向第一个节点的指针和新节点内的next,不过不用考虑空链表的特殊情况。
//尾插
void SLTPushBack(SLTNode** pphead, SLTdatatype value)
{
assert(pphead);
SLTNode* newnode = SLTBuynode(value);
if (*pphead == NULL) //*pphead就是第一个节点的地址
{
*pphead = newnode;
}
else
{
SLTNode* ptail = *pphead;
while (ptail->next != NULL)
{
ptail = ptail->next;
}
ptail->next = newnode;
}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTdatatype value)
{
assert(pphead);
SLTNode* newnode = SLTBuynode(value);
//if (*pphead == NULL)
//{
// *pphead = newnode;
//}
//此处无需判断NULL，下列能包含空链表情况
newnode->next = *pphead;
*pphead = newnode;
}4.尾删、头删
尾删仍然考虑两种情况，就只有一个节点的情况下直接释放该节点就行。如果不只一个节点的情况下，需要进行两个步骤，将ptail（最后一个节点）释放掉，再将前一个节点中的next改为NULL。
至于头删，只需要先用next储存第二个节点的地址，释放第一个节点地址，再将*pphead赋为next即可。注意此处要先储存，否则释放后找不到第二个节点的地址。
//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
if ((*pphead)->next == NULL)//不要忘记加括号，考虑操作符优先性
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* ptail = *pphead;
SLTNode* prev = *pphead;
while (ptail->next != NULL)
{
prev = ptail;
ptail = ptail->next;
}
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}5.查找
如果找到查找的值则返回其地址，否则返回NULL。
//查找
SLTNode* SLTFind(SLTNode* phead, SLTdatatype value)
{
SLTNode* pcur = phead;
while (pcur)//等价与 pcur != NULL
{
if (pcur->data == value)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}6.指定位置前插入
其中pos是指定的位置，此时分两种情况，如果指定位置是链表头时，这种情况直接头插就能解决。另一普通情况下，使用prev找到pos前的一个节点，将pos前一个节点的next赋为newnode，而newnode的next赋为pos就能插入成功。
//指定位置前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTdatatype value)
{
assert(pphead);
assert(*pphead);
assert(pos);
if (*pphead == pos)
{
SLTPushFront(pphead, value);
}
else
{
SLTNode* newnode = SLTBuynode(value);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}7.指定位置后插入
相比之下在指定位置后插入简单一些，特殊情况在链表最后插入也包含在普通情况中。这里也不需要链表头的地址，只需要创建临时指针tmp储存pos中的next即可，防止next改为newnode后丢失。
//指定位置后插入
void SLTInsertBack(SLTNode* pos, SLTdatatype value)
{
assert(pos);
SLTNode* newnode = SLTBuynode(value);
SLTNode* tmp = pos->next;
pos->next = newnode;
newnode->next = tmp;
}8.指定位置删除
同样分为两种情况（在需要用到prev时都要考虑到指定位置是链表头的情况），指定位置是链表头时，prev的寻找会失效，直接使用头删。普通情况下，先找到prev，再将prev的next改为pos的next，进行释放pos。
//指定位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}9.指定位置后删除
在该情况下指定位置后不能为空，因此要注意assert(pos->next)，其余与上同理。
//指定位置后删除
void SLTEraseBack(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* tmp = pos->next->next;
free(pos->next);
pos->next = tmp;
}10.销毁链表
使用临时变量存放pcur中的next，在pcur对应的空间释放后再将tmp赋给pcur直到空为止。
//销毁链表
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* tmp = pcur->next;
free(pcur);
pcur = tmp;
}
*pphead = NULL;
}三.完整代码
头文件：SList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTdatatype;
typedef struct SListNode
{
SLTdatatype data;
struct SListNode* next;
}SLTNode;
//创建节点
SLTNode* SLTBuynode(SLTdatatype value);
//打印
void SLTPrint(SLTNode* ps);
//尾插
void SLTPushBack(SLTNode** pphead, SLTdatatype value);
//头插
void SLTPushFront(SLTNode** phead, SLTdatatype value);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTdatatype value);
//指定位置前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTdatatype value);
//指定位置后插入
void SLTInsertBack(SLTNode* pos, SLTdatatype value);
//指定位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos);
//指定位置后删除
void SLTEraseBack(SLTNode* pos);
//销毁
void SLTDestroy(SLTNode** pphead);源文件：SList.c
#include"SList.h"
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
SLTNode* SLTBuynode(SLTdatatype value)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc");
exit(1);
}
newnode->data = value;
newnode->next = NULL;
return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTdatatype value)
{
assert(pphead);
SLTNode* newnode = SLTBuynode(value);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* ptail = *pphead;
while (ptail->next != NULL)
{
ptail = ptail->next;
}
ptail->next = newnode;
}
}
void SLTPushFront(SLTNode** pphead, SLTdatatype value)
{
assert(pphead);
SLTNode* newnode = SLTBuynode(value);
//if (*pphead == NULL)
//{
// *pphead = newnode;
//}
//此处无需判断NULL，下列能包含空链表情况
newnode->next = *pphead;
*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
if ((*pphead)->next == NULL)//不要忘记加括号，考虑操作符优先性
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* ptail = *pphead;
SLTNode* prev = *pphead;
while (ptail->next != NULL)
{
prev = ptail;
ptail = ptail->next;
}
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
SLTNode* SLTFind(SLTNode* phead, SLTdatatype value)
{
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == value)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTdatatype value)
{
assert(pphead);
assert(*pphead);
assert(pos);
if (*pphead == pos)
{
SLTPushFront(pphead, value);
}
else
{
SLTNode* newnode = SLTBuynode(value);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}
void SLTInsertBack(SLTNode* pos, SLTdatatype value)
{
assert(pos);
SLTNode* newnode = SLTBuynode(value);
SLTNode* tmp = pos->next;
pos->next = newnode;
newnode->next = tmp;
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
void SLTEraseBack(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* tmp = pos->next->next;
free(pos->next);
pos->next = tmp;
}
void SLTDestroy(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* tmp = pcur->next;
free(pcur);
pcur = tmp;
}
*pphead = NULL;
}源文件：test.c
#include"SList.h"
void SLTtest01()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPushFront(&plist, 2);
SLTPushFront(&plist, 1);
SLTPrint(plist);
/*SLTPopBack(&plist);
SLTPopBack(&plist);
SLTPopBack(&plist);
SLTPopBack(&plist);*/
/*SLTPopFront(&plist);
SLTPopFront(&plist);
SLTPopFront(&plist);
SLTPrint(plist);*/
SLTNode* ret = SLTFind(plist, 2);
/*if (ret != NULL)
{
printf("找到了\n");
printf("%d\n", ret->data);
}
else
{
printf("找不到");
}*/
//SLTInsert(&plist, ret, 8);
//SLTInsertBack(ret, 8);
//SLTPrint(plist);
//SLTErase(&plist, ret);
SLTEraseBack(ret);
SLTPrint(plist);
SLTDestroy(&plist);
}
int main()
{
SLTtest01();
return 0;
}