在这篇文章中，你将熟练应用单链表，彻底玩转单链表，你会发现单链表真的很简单。
首先，来介绍一下单链表的构成，单链表由一个或者多个内存不连续的独立节点构成，每一个节点都是一个结构体，节点内部具有两个属性：1.节点所存储的数据 2.下一个节点的地址。、
代码布局
- 在SingleList.h文件中申明节点和函数
- 在SingleList.c文件中实现函数
- 在test.c文件中测试代码
一.创建单链表
在SingleList.h文件中创建单链表
1. typedef struct SingleList 2. { 3. datetype date;//存放数据 4. struct SingleList* next;//存放下一个节点的地址 5. }SLT;
为了方便观察链表中的数据，我们可以写一个函数printSLT来方便测试代码。
二.打印链表
1. void printSLT(SLT* phead) 2. { 3. SLT* cur = phead;//头节点备份 4. while (cur != NULL) 5. { 6. printf("%d->", cur->date);//打印当前节点数据 7. cur = cur->next;//节点后移 8. } 9. printf("NULL");//打印结尾 10. }
三.链表头部节点插入
链表的插入，从本质分析无非就是创建一个新节点---->将新节点与链表链接起来。只要做好这两步，我们就可以插入函数了。
插入的第一步是创建新节点，为了减少代码的冗余，写一个创建新节点的函数来完成这个任务。
1. SLT* buynewnode(datetype n) 2. { 3. SLT* newnode = (SLT*)malloc(sizeof(SLT));//在堆上申请空间,防止处函数空间被销毁 4. if (newnode == NULL)//判断是否申请成功 5. { 6. printf("malloc失败"); 7. return NULL; 8. } 9. newnode->date = n;//将节点数据初始化 10. newnode->next = NULL; 11. return newnode;//返回创建的节点的地址 12. }
插入的第二步就是将新节点与链表链接起来。
看图，要想将newnode与原链表链接起来，需要让newnode->next指向*pphead（头节点地址），并且将新的头节点地址改为newnode的地址。代码如下
1. void pushhead(SLT** pphead, datetype n) 2. { 3. SLT* newnode = buynewnode(n);//创建新节点 4. //链接新节点 5. newnode->next = *pphead;//newnode指向*pphead 6. *pphead = newnode;//头节点地址改为newnode的地址 7. }
这里就体现了二级指针的作用了，要改变头节点地址，就必须把头节点地址 的地址传过来，解引用 头节点地址 的地址，才可以访问到头节点地址，进而改变头节点地址。
四.链表尾部节点插入
尾部插入逻辑相同，只需要创建新节点，链接新节点。需要分两种情况讨论，1，链表为空.2，链表不为空。当链表不为空时，需要找到尾节点tail，再将尾节点与新节点链接起来。当链表为空时，只需要将头节点地址改为新节点地址。代码如下
1. void pushback(SLT** pphead, datetype n) 2. { 3. SLT* newnode = buynewnode(n);//创建新节点 4. SLT* tail = *pphead;//使用tail找到尾节点 5. if (tail != NULL)//链表不为空 6. { 7. while (tail->next != NULL)//利用尾节点特征:tail->next==NULL，找到尾节点 8. { 9. tail = tail->next; 10. } 11. tail->next = newnode;//链接尾节点与新节点 12. } 13. else//链表为空 14. { 15. *pphead = newnode;//把头节点地址改为新节点地址（二级指针作用） 16. } 17. }
五.链表头部节点删除
链表节点的删除，首先要断言一下链表（空链表不可以删除），其次头部节点的删除只需要将头节点地址改为头节点下一个节点的地址，然后释放原头节点的空间。
1. void pophead(SLT** pphead) 2. { 3. assert(*pphead);//断言链表，保证链表不为空 4. SLT* tmp = *pphead;//备份原头节点地址，防止头节点地址改后找不到 5. *pphead = (*pphead)->next;//把头节点地址改为头节点下一个节点的地址 6. free(tmp);//释放原头节点空间,使用备份 7. }
当链表只有一个节点，这种删除方式也是可行的。
六.链表尾部节点删除
首先，断言一下链表（空链表不可以删除），其次，如果链表有两个以及两个以上节点，要想删除尾节点，必须先找到倒数第二个节点(tail)，再释放尾节点(tail->next)内存空间，倒数第二个节点的next设置为NULL。如果链表只有一个节点，只需要释放头节点内存空间，再将头节点地址改为NULL。代码如下
1. void popback(SLT** pphead) 2. { 3. assert(*pphead);//断言链表，保证链表不为空 4. SLT* tail = *pphead;//倒数第二个节点tail 5. if (tail->next != NULL)//两个以及两个以上节点 6. { 7. while (tail->next->next != NULL)//找到倒数第二个节点 8. { 9. tail = tail->next;//找到下一个节点 10. } 11. free(tail->next);//释放尾节点空间 12. tail->next = NULL;//倒数第二个节点的next置为空 13. } 14. else//一个节点 15. { 16. free(*pphead);//直接释放节点空间 17. *pphead = NULL;//将头节点地址改为空 18. } 19. }
七.链表节点查找
链表节点查找 要实现的功能是找到存放指定date的节点，并返回该节点的地址。具体代码如下，注释很明确。
1. SLT* SLTfind(SLT* phead,datetype n) 2. { 3. SLT* cur = phead;//备份头节点地址 4. while (cur->date!=n)//循环遍历找到cur->date==n的节点cur 5. { 6. if (cur->next == NULL)//如果找到尾节点还没找到则返回NULL 7. return NULL; 8. 9. cur = cur->next; 10. } 11. return cur;//尾节点前，提前找到则返回这个节点地址 12. }
八.链表节点修改
链表节点修改 要实现的功能是修改该节点的数据。要想将数据为n的节点的数据改为m，需要先找到数据为n的节点的地址，再改为m。
1. void modifySLT(SLT* phead, datetype n,datetype m)//数据为n的节点数据改为m 2. { 3. SLT* pos = SLTfind(phead, n);//找到date==n的节点的地址 4. pos->date = m;//该节点数据改为m 5. }
九.链表指定节点之后插入
插入节点的本质就是创建新节点，将新节点与链表链接起来。所以，要在指定位置之后插入只需要将pos->next与新节点链接起来，再将新节点与原来pos后面的那个节点链接起来。(注意顺序问题)
1. void pushafterpoint(SLT* pos, datetype n) 2. { 3. SLT* newnode = buynewnode(n);//创建新节点 4. //链接新节点 5. newnode->next = pos->next;//新节点的next存放pos位置节点的下一个节点地址 6. pos->next = newnode;//pos指向新节点 7. }
十.链表指定节点之前插入
链表在指定位置之前插入，本质也是插入，只不过是链接新节点的细节不同。注意:如果指定位置是头节点，那么指定位置之前插入便是头插，所以分开来写。
1. void pushbehindpoint(SLT** pphead, SLT* pos, datetype n) 2. { 3. SLT* newnode = buynewnode(n);//创建新节点 4. if (pos == *pphead)//如果指定位置是头节点，头插 5. { 6. *pphead = newnode; 7. newnode->next = pos; 8. } 9. else 10. { 11. SLT* tail = *pphead;//备份头节点地址 12. while (tail->next != pos)//找到指定位置的上一个节点 13. { 14. tail = tail->next; 15. } 16. //在上一个节点与pos之间链接新节点 17. tail->next = newnode;//上一个节点指向新节点 18. newnode->next = pos;//新节点指向指定位置节点 19. } 20. }
十一.链表指定位置删除节点
首先，要断言一下链表(空链表不能删除)。这个函数要实现的功能是要删除指定位置的节点，步骤为：将指定位置前一个节点与指定位置后一个节点链接起来，然后释放指定位置节点的内存空间。
1. void poppoint(SLT** pphead, SLT* pos) 2. { 3. assert(*pphead);//保证链表不为空 4. SLT* cur = *pphead;//备份pphead 5. if (pos == *pphead)//如果指定位置是头节点，头删 6. { 7. *pphead = (*pphead)->next; 8. free(cur); 9. } 10. else 11. { 12. while (cur->next != pos)//找到指定位置之前的节点 13. { 14. cur = cur->next; 15. } 16. //链接指定位置之前与之后 17. cur->next = pos->next; 18. //释放指定位置内存空间 19. free(pos); 20. } 21. }
到这里，单链表的基本操作几乎了解完了，但是要想熟练应用，融汇贯通，还要多加练习，做一些链表有关的OJ来加强理解，相信进步一定会很明显。
