1 链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
从以上图片可以看出：
1.链式结构在逻辑上是连续的，但在物理上不一定是连续的。
2.现实中的节点一般是在堆上申请出来的。
3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，可能不连续。
2 链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
2.1单向或双向
2.2带头或者不带头
2.3循环或者非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
3 单向无头链表的实现
在头文件中包含一些函数的声明。
因为每个节点都是一个结构体，所以每个节点都要存放一个结构体的指针，指向下一个节点。
typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; SLTNode* BuyListBNode(SLTDataType x); void PrintSList(SLTNode* phead); void SLTPushBcak(SLTNode** pphead,SLTDataType x);//尾插 void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插 void SLTPopback(SLTNode** pphead);//尾删 void SLTPopFront(SLTNode** pphead,SLTDataType x);//头删 void SLTFind(SLTNode* pphead,SLTDataType x);//查找 //在pos之前插入x void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //在pos之后插入x void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x); //删除pos位置 void SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos的后一个位置 void SLTEraseAfter(SLTNode* pos);
3.1打印链表
打印链表首先要遍历链表，那么循环的条件就是走到空。所以我们创建一个临时变量cur代替头节点用来遍历，这样就可以不用动头节点，打印就是将节点中的数据打印出来，所以先将各个节点的数据打印出来，再指向下一个节点，需要注意的是next就是下一个节点的地址，所以将cur->next赋给cur就可以拿到下一个节点的地址了，拿到地址就可以继续访问下一个节点了。
void PrintSList(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
3.2创建节点
这里malloc一个节点出来就行了，然后判断是否malloc成功，将需要的数据存进data中就行了，然后将next置为NULL，然后返回这个节点。
SLTNode* BuyListBNode(SLTDataType x) { SLTNode* newnode = (SLTNode*) malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
3.3尾插节点
这个函数的第一个参数是一个二级指针，目的是为了修改结构体，尾插节点首先需要创建一个节点，然后·判断一下当前链表是否为空，如果为空则将这个节点设置为头节点，所以解引用这个二级指针，拿到一级指针的地址，就可以修改了。如果不为空，则创建一个临时变量来保存头节点的地址，然后使用这个变量来遍历链表找到尾节点，循环的结束条件就是tail的next为空，因为尾节点的next是NULL，循环结束之后tail就走到了尾节点的位置，然后将新节点赋给tail的next即可。
void SLTPushBcak(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuyListBNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
3.4头插节点
尾插节点还是需要创建一个节点，然后将这个节点的next指向这个头节点，但是头插之后头节点就是新插入的这个节点，所以需要使用二级指针，最后将新节点newnode赋给*pphead，这样头节点就更新了。
void SLTPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuyListBNode(x); newnode->next = *pphead; *pphead = newnode; }
3.4尾删节点
尾删需要分很多种情况：
1.没有节点，这种情况就直接暴力检查，没有节点是删除不了的，直接assert即可。
2.一个节点，如果是一个节点的话，这个节点的next一定是NULL，所以使用if判断*pphead->next是否为NULL，如果是的话直接free掉这个节点然后置为空就行了。
3.如果是多个节点的话创建一个临时变量来遍历链表找到尾，需要注意的是，这个循环的结束条件是tail->next->next为空。下面这段代码就是错误的，因为free（tail）的本质是将tail指向的节点free，再将tail置为空相当于给tail赋值0x00000000，局部变量出了作用域就销毁了，但是前一个节点还是野指针，next虽然还是指向这个节点，但是这个节点已经free了。所以解决的方法就是找到tail的前一个节点，然后free掉tail->next，再置空。
正确的方法：
void SLTPopback(SLTNode** pphead) { assert(*pphead); //一个节点 if ((*pphead)->next = NULL) { free(*pphead); *pphead = NULL; } else//多个节点 { SLTNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
3.5头删节点
头删也需要用到二级指针，然后暴力检查链表是否为空，不为空则创建一个变量newnode来保存头节点的next，然后free掉头节点，再将newnode赋给*pphead。
void SLTPopFront(SLTNode** pphead) { assert(pphead); SLTNode* newhead = (*pphead)->next; free(*pphead); *pphead = newhead; }
3.6查找节点
这个函数很简单，找到data就行，然后返回节点。
SLTNode* SLTFind(SLTNode* pphead, SLTDataType x) { SLTNode* cur = pphead; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
3.6在pos位置之前插入节点
pos的位置也需要分情况：
1.暴力检查
2.如果是头插，直接调用头插函数。
3.正常情况，创建一个结构体变量来遍历链表寻找pos节点，但是循环的结束条件设置成pre->next=pos最合适，因为我们需要保存pos的前一个节点，所以循环结束后pre就是pos的前一个节点，此时创建一个需要插入的节点newnode，将pre的next指向newnode，再将newnode的next指向pos，就完成链接了。
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pos); if (*pphead == pos) { SLTPopFront(pphead,x); } else { SLTNode* pre = *pphead; while (pre->next != pos) { pre = pre->next; } SLTNode* newnode = BuyListBNode(x); pre->next = newnode; newnode->next = pos; } }
3.7在pos位置之后插入节点
首先暴力检查，再创建一个新节点newnode，插入需要注意的是以下这种写法是错误的，因为当我们将pos的next指向newnode的时候，就与后面的节点完全断开了，然后newnode的next又指向pos的next相当于形成了一个死循环。正确的方法应该是pos的next指向newnode的next，相当于先将newnode的next指向pos的后一个节点形成newnode的尾部链接，再将pos的next指向newnode完成newnode的头部链接。
void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuyListBNode(x); newnode->next = pos->next; pos->next = newnode; }
3.8删除pos位置的节点
首先暴力检查，再判断pos是不是头删，正常删除就是创建一个变量遍历链表，pos的next为空作为循环的结束条件，循环结束之后pre就是pos的前一个节点，这个时候将pre的next指向pos的next也就是pos的下一个节点就行了，然后frre掉pos，这时候就不需要置空了。
void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pos); if (pos == *pphead) { SLTPopFront(pphead); } else { SLTNode* pre = *pphead; while (pre->next != pos) { pre = pre->next; } pre->next = pos->next; free(pos); } }
3.9删除pos位置之后的节点
首先暴力检查，然后再检查是否为尾节点。创建一个变量posNext保存pos的下一个节点，然后即将pos的下一个节点指向pos的下下个节点即可。然后free掉posNext。
void SLTEraseAfter(SLTNode* pos) { assert(pos); assert(pos->next);//检查是否是尾节点 SLTNode* posNext = pos->next; pos->next = posNext->next; free(posNext); }
