一、什么是链表
在线性表结构中，可以分为顺序存储结构与链式存储结构，顺序存储结构就好比数组，在一块连续的空间中存放对应的数据。
而链式存储结构与顺序存储结构相比较下就不存在连续存储的空间，而是不同的空间通过指针联系在一起。
由上图可知，链表在逻辑上是连续的，但是在物理上并不是连续的，每块空间都是在堆上被申请出来的，malloc函数每次申请的空间可能是连续的也可能不是连续的。
二、链表种类
链表也有多种的类型：单向链表，双向链表，带头（哨兵位）链表，不带头（哨兵位）链表，循环链表和不循环链表；同时这几种属性可以相互搭配：
- 单向不带头不循环
- 单向不带头循环
- 单向带头不循环
- 单向带头循环
- 双向不带头不循环
- 双向不带头循环
- 双向带头不循环
- 双向带头循环
共有8种；
三、单向不带头不循环链表的实现
（一）链表的初始化
因为链表所储存的数据还不确定，所以可以先使用typedef将链表所储存的数据类型进行重命名，当需要重新更改数据类型时只需要更改被重命名的类型即可。
typedef int SLTDataType; typedef struct SListNode//声明一个结构体 { SLTDataType date;//用来存放数据 struct SListNode* next;//用来记录下一个内存的地址或是空指针 }SLTNode;//使用typydef将结构体重命名为STLTNode
在实现链表之前应先声明一个相对应的结构体类型，使得每次malloc节点时的类型都能为该结构体类型。
（二）链表的打印
链表的打印涉及到了链表的遍历，若是数组即可使用循环以及数组中各个元素的下标来达到访问数组中的各个元素；根据链表的结构可知，每个节点的next都存放着下一个节点的地址，故在此也可使用循环，使用一个指针赋上头指针的地址，若是该指针的值不为NULL，即打印各个节点中的data；
void SLTPrint(SLTNode* phead)//链表的遍历 { SLTNode* cur = phead; while (cur != NULL) { printf("%d->",cur->date); cur = cur->next; } printf("NULL\n"); //本质上也可以移动phead，形参的改变不影响实参 }
该处在函数内创建了一个cur指针用来进行链表的遍历，本质上此处也可直接使用phead指针，函数内的phead指针为形参，形参的改变不会影响到实参；
（三）新节点的开辟
当需要插入数据的时候即需要向内存开辟空间，在此存在多个插入接口（头插、尾插、中间插入），故可以将开辟空间封装为一个函数；
SLTNode* BuyLTNode() { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("SLPushFront::malloc"); return NULL; } newnode->next = NULL;//保险起见应先提前将新节点的next置空 return newnode; }
（四）链表的尾插
单链表的尾插，即将尾节点的next指向新节点，同时新节点的next指向NULL；
void SLPushBack(SLTNode** pphead, SLTDataType x)//尾插 { SLTNode* newnode = BuyLTNode(); newnode->date = x; if (*pphead==NULL) { *pphead = newnode; } else { SLTNode* tmp = *pphead; while (tmp->next!=NULL) { tmp = tmp->next; } tmp->next = newnode; } }
（五）链表的尾删
链表的尾删即为，遍历到尾节点的前一个节点，并将尾节点释放，同时将尾节点的前一个节点的next处置为空；
该处需要注意的是典型的边界性问题：
- 尾删时链表不能为空；
- 尾删时若是链表只存在一个节点，则可能出现非法解引用访问；
void SLPopBack(SLTNode** pphead)//尾删 { assert(*pphead);//空链表 SLTNode* tmp = *pphead; if (tmp->next == NULL) { free(tmp); *pphead = NULL; } else { while (tmp->next->next != NULL) { tmp = tmp->next; } free(tmp->next); tmp->next = NULL; } }
（六）链表的头插
链表的头插与链表的尾插步骤差不多，但是相比不同的时，头插对于尾插来说多了一个步骤就是更新head头指针，从上面的尾删尾插可以看到采用了二级指针，但对于二级指针的用处并没有实质性的体验出来，而这次因为需要换头指针，所以应该传递头指针的地址，通过地址解引用访问找到头指针针并对其进行修改；
void SLPushFront(SLTNode**phead,SLTDataType x) //头插 { SLTNode* newnode = BuyLTNode(); newnode->date = x; newnode->next = NULL;//初始化置空 newnode->next = *phead; *phead = newnode; }
（七）链表的头删
链表的头删与头插也有异曲同工之处，都需要使用二级指针来更新头指针head的指向；
void SLPopFront(SLTNode** pphead)//头删 { assert(*pphead); /*if ((*pphead)->next == NULL) { SLTNode* tmp = *pphead; free(tmp); *pphead = NULL; } //注释掉的步骤为冗余的步骤； else {*/ SLTNode* tmp = (*pphead)->next; free(*pphead); *pphead = tmp; //} }
（八）链表的查找
链表的查找即为查找对应的数据，并返回对应的地址，只需要遍历链表并找出相应值即可，若是没找到则返回空指针NULL；
SLTNode* SLFind(SLTNode* phead, SLTDataType x) { assert(phead); SLTNode* tmp = phead; while (tmp->next != NULL) { if (tmp->date == x) { return tmp; } tmp = tmp->next; } return NULL; }
（九）链表中间插入（pos之后）
该处的pos即为所给位置的节点，一般在单链表中的中间插入都为pos之后，单链表与双链表不同，单链表只能依靠结构中的next访问下一个节点，而不能通过该节点访问该节点的前一个节点。
void SListInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode*newnode = BuyLTNode(); newnode->date = x; SLTNode* tmp = pos->next; pos->next = newnode; newnode->next = tmp; }
（十）链表的中间删除（pos之后）
单链表的中间删除与中间插入相同，因为单链表不像双链表一样可以访问到pos之前的节点，故一般只能删除pos之后的节点；
void SListEraseAfter(SLTNode* pos) { assert(pos&&pos->next); SLTNode* tmp = pos->next->next; free(pos->next); pos->next = tmp; }
（十一）链表的修改
链表的修改只需要将所给指针pos节点内的val改为需要修改的值即可，但也需要对pos指针进行assert断言，防止对非法指针的解引用访问；
void SLModify(SLTNode* phead, SLTDataType x) { assert(phead); phead->date = x; }
（十二）链表的销毁
只要是涉及到内存申请的问题，在申请并用完过后应及时进行释放，一般情况下程序结束时会自动将程序内所申请的空间还给操作系统，但若是程序未结束，所申请的内存即不将还给操作系统，可能会发生内存泄漏等问题；
链表的销毁只需将链表中的各个节点进行释放并将头指针head置为空防止出现野指针问题即可；
void SListDestroy(SLTNode** plist) { assert(*plist); SLTNode* tmp; SLTNode* pos = *plist; while (pos != NULL) { tmp = pos->next; free(pos); pos = tmp; } *plist = NULL; }
利用两个指针对链表进行遍历，使用指针pos指向头head，另一个指针tmp指向pos所指向的next，并对链表进行遍历，tmp指针用来记录即将被销毁的节点的下一个节点，pos指针用来释放内存；
总结
- 操作链表的几个函数内都要注意对所给参数进行断言，防止对非法指针的解引用访问；
- 单向不带头不循环链表虽然是链表中结构最简单的链表，但相比于其他链表中操作也是最繁琐的，为了防止出现边界问题，总要对链表进行判空；
