一:什么是链表
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
这里简单介绍一下逻辑结构和物理结构
逻辑结构: 人为想象出来的,实际并不存在.
物理结构: 实际存在,可以被观察到
二:链表的种类
共有8种链表结构，请看图！
根据排列组合，2*2*2共有八种情况。
三:单链表的特点
特点
(1)用链表存储实现的线性结构
(2)一个结点存储一个数据元素
(3)各结点之间先后关系用一个指针表示
下面我们实现的是无头单向非循环链表
结构体数据域存数据，指针域存下一个节点的地址。
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
四：创建项目
工程文件 存放的内容
SeqList.h 函数声明，宏定义
SeqList.c 实现顺序表函数接口的定义
test.c 测试函数接口是否能实现功能
五：接口实现
1.创建结构体类型
为了后续我们想更改数据类型时方便，我们一般对类型进行typedef操作。
typedef int SLTDataType; typedef struct SListNode { SLTDataType data; //存放数据 struct SListNode* next; //指向下一个节点 }SLTNode;
2. 链表开辟空间
我们接下来实现的是不带哨兵位的，即不带头节点。 我们要定义结构体指针。
SLTNode* phead = NULL; //头指针
带头和不带头（使用头指针）的有什么区别？
带头：使用哨兵位（头节点）
此时phead指向的下一个节点才是单链表的第一个节点，带头结点就不需要改变传过来的指针，也就意味着不需要传二级指针。
不带头：使用头指针
此时phead指向的就是单链表的第一个节点。因为若要对phead的指向做修改，若传一级指针，就相当于传值，形参的改变并不会影响实参！所以我们应该把phead的地址传过去，用二级指针接收！
像打印数据，查找数据这一类并不会对单链表内容修改的，我们传值也可以，传址也可以。
3.打印数据
只需要遍历链表，把每个节点的数据打印出来。最后一个节点的next为NULL跳出循环。
//打印 void SlistPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) //遍历链表 { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
4.创建节点
使用malloc动态开辟节点！要判断空间开辟是否成功！ 新节点的next要置空
//创建节点(带值) SLTNode* BuySlistNode(SLTDataType x) { //malloc一个节点 开辟空间 SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { printf("malloc is fail\n"); return NULL; } newnode->data = x; newnode->next = NULL; return newnode; }
5.尾插数据
尾插：
情况1：链表为空时：直接将phead指向新开的节点
情况2：链表有节点了，->遍历链表找到尾指针，将尾指针的next链接新节点。
//尾插 void SListPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead);//防止pphead为空指针 //先新建一个节点 SLTNode* newnode = BuySlistNode(x); //当链表为空时，直接将phead指向新节点 if (*pphead == NULL) { *pphead = newnode; } else { //找尾指针,进行链接 SLTNode* tail = *pphead; //遍历链表找尾指针 while (tail->next) { tail = tail->next; } //链接新节点 tail->next = newnode; //newnode->next = NULL; newnode 初始化时next已经置空 } }
6.头插数据
头插：
1.新开一个
2.newnode先链接原来的第一个节点
3.phead指向newnode
顺序不可以反转，不然就找不到原来的第一个节点了。 按照上面的顺序，链表为空也无影响。原来第一个节点为NULL。
//头插 void SListPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); //先新建一个节点 SLTNode* newnode = BuySlistNode(x); //phead指向的节点给newnode->next 链表为空也无影响 newnode->next = *pphead; //phead指向新节点 *pphead = newnode; }
7.尾删数据
尾删：
情况1：链表为空就不删了
情况2：只有一个节点时，free掉第一个节点，然后phead 置空
情况3：多节点时，找到尾节点，把尾节点空间释放掉，把还要找到尾节点前面的节点，将该节点的指向下一个节点的指针置空！否则会造成野指针情况！
//尾删 void SListPopBack(SLTNode** pphead) { //1.链表为空就不删了 if (*pphead == NULL) return; //2.只有一个节点 //！！！容易忽略 else if ((*pphead) ->next == NULL) { free(*pphead); *pphead = NULL; } //3.多节点 else { //找到尾指针及尾指针前面的指针 SLTNode* prev = NULL; SLTNode* tail = *pphead; while (tail->next) { prev = tail; tail = tail->next; } //将尾指针前面的指针置NULL 否则会造成野指针 prev->next = NULL; free(tail); } }
8.头删数据
头删：
情况1：链表为空不删
情况2：有节点（1个或多个）
先保存第二个节点，然后释放掉第一个节点，phead指向原来的第二个节点。（只有一个节点也没问题，第一个节点的next为NULL）
//头删 void SListPopFront(SLTNode** pphead) { //链表为空就不删了 if (*pphead == NULL) return; else { SLTNode* next = (*pphead)->next; //先保存第二个节点的位置 free(*pphead); //释放第一个节点 注意释放的是*pphead 不是pphead！！ *pphead = next; } }
9.查找数据所在位置
遍历查找即可，找到了返回所在的位置，找不到返回空指针。
//查找位置 SLTNode* SListFind(SLTNode* phead, SLTDataType x) { //遍历查找 SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } //找不到/空链表返回NULL return NULL; }
10.在pos位置之前插入数据
情况1：在第一个节点前插入：相当于头插，直接调用头插的接口
情况2：多节点
1.找到pos位置前的节点
2.创建新节点
3.目标节点前的结点链接新节点
4.新节点链接目标节点
//在pos位置前插入x void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { //当在第一个节点前插入：头插 if (pos == *pphead) { SListPushFront(pphead, x); } else { //开辟新节点 SLTNode* newnode = BuySlistNode(x); //找到pos前面的节点 SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } //此时prev在pos前面 prev->next = newnode; newnode->next = pos; } }
11.删除pos位置
情况1：链表为空 不删除
情况2：删除的是第一个节点 ->相当于头删 ->调用头删接口
情况3：多节点
1.找到pos位置前的节点
2.pos位置前的节点链接pos位置后的节点
3.free掉pos位置节点
//删除pos位置的节点 void SListErase(SLTNode** pphead, SLTNode* pos) { //空链表时不删除 if (*pphead == NULL) return; //删除第一个节点时 if (pos == *pphead) { SListPopFront(pphead); //头删 } else { // 找到pos前的节点 SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
12.判断单链表是否为空
若phead指向的为空指针就说明为空链表
bool SListEmpty(SLTNode* phead) { return phead == NULL; //phead== NULL为真则返回真 }
13.计算单链表长度
使用计数器计数。因为不改变头指针phead，所以传值传址都可以。我们这里选择传值方式
int SListSize(SLTNode* phead) { SLTNode* cur = phead; int size = 0; while(cur->next != NULL) { size++; cur = cur->next; }; return size; }
14.销毁单链表
使用两个指针，一个保存下一个节点，一个用来遍历。free即可，最后把phead置空
void SListDestory(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead; while (cur) { SLTNode* next = cur->next; //保存下一个节点 free(cur); cur = next; } *pphead = NULL; }
六.精华总结：
注意事项：
1.使用头指针 or 使用头节点
2.插入删除注意分情况讨论！如：链表为空。只有一个节点，多节点情况！不然容易出BUG
3.注意链接顺序！防止找不到上一个/下一个节点。
