一.链表的概念和结构
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的
链表其实有很多种类：
1.单向 双向
2.带头 不带头
3.循环 不循环
其中共能组合出8种形式的链表；
这篇文章讲的是结构最简单的链表，也就是单向不带头不循环链表，即单链表。
单链表中的元素称为节点，节点有一个数据data，还有一个结构体指针next 存储下一个节点的地址，最后一个节点的next是NULL。
二.单链表的逻辑结构和物理结构
1.逻辑结构
2.物理结构
三.结构体的定义
1. typedef int SLdatatype; //对数据类型重定义，方便后续更改 2. 3. typedef struct SListNode 4. { 5. SLdatatype data; 6. struct SListNode* next; 7. }SLNode;
四.增加
1.尾插 SListpushback
想要实现尾插，就要先找到尾节点，但要注意，当链表是空时，就没有尾节点，这个时候直接插入就行了；
我们可以申请一个新的节点newnode，然后插入链表中，由于尾插和头插都需要申请新的节点，所以我们可以将这封装成一个函数；
注意，不管是尾插还是头插，最后都会使链表发生改变，所以我们要传二级指针进去。
找尾节点时，while里的循环条件要写成 tail->next !=NULL
请看逻辑结构：
申请新节点 BuySListNode
1. SLNode* BuySListNode(SLdatatype x) 2. { 3. SLNode* newnode = (SLNode*)malloc(sizeof(SLNode)); 4. assert(newnode); 5. newnode->data = x; //x是要插入的数据 6. newnode->next = NULL; 7. return newnode; 8. }
尾插 SListpushback
1. void SListpushback(SLNode** pphead,SLdatatype x) //注意传的是二级指针 2. { 3. SLNode* newnode = BuySListNode(x); 4. if (*pphead == NULL) //判断链表是否为空 5. { 6. *pphead = newnode; 7. } 8. else 9. { 10. SLNode* tail = *pphead; //寻找尾节点 11. while (tail->next != NULL) //注意这里不能写成 while(tail!=NULL) 12. { 13. tail = tail->next; 14. } 15. tail->next = newnode; 16. } 17. }
2.头插 SListpushfront
头插时只需让新节点的 next 指向旧的头节点，然后再把 newnode 赋给头节点，使之成为新的头节点，即使是空表也没关系，newnode 会直接成为头节点。
1. void SListpushfront(SLNode** pphead, SLdatatype x) 2. { 3. SLNode* newnode = BuySListNode(x); 4. newnode->next = *pphead; 5. *pphead = newnode; 6. }
五.删除
1.尾删 SListpopback
尾删前，我们需要判断：
1.若为空表，则直接结束函数；
2.若链表中只有一个节点，则直接 free 头节点，然后置为NULL；
3.寻找尾节点 tail 和尾节点的前一个节点 pre ,因为我们释放掉尾节点后，pre就成为了新的尾节点，而尾节点的 next 是 NULL ，所以我们需要找到尾节点的前一个节点。
找尾的方法和之前的一样。
1. void SListpopback(SLNode** pphead) 2. { 3. if (*pphead == NULL) 4. { 5. return; 6. } 7. else if ((*pphead)->next == NULL) //注意这里因为优先级的问题，*pphead 要打括号 8. { 9. free(*pphead); 10. *pphead = NULL; 11. } 12. else 13. { 14. SLNode* pre = NULL; 15. SLNode* tail = *pphead; 16. while (tail->next != NULL) 17. { 18. pre = tail; //记录 tail 的前一个节点 19. tail = tail->next; 20. } 21. pre->next = NULL; //next 置为NULL 22. } 23. }
2.头删 SListpopfront
在头删前：
1.判断是否为空表；
2.定义一个 next 用来保存头节点中的 next ，释放完后，这个 next 就成为了新的头节点。
1. void SListpopfront(SLNode** pphead) 2. { 3. if (*pphead == NULL) 4. { 5. return; 6. } 7. else 8. { 9. SLNode* next = (*pphead)->next; 10. free(*pphead); 11. *pphead = next; 12. } 13. }
