1.概念及结构
概念：
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。它包括两个域，其中存储数据元素信息的称为数据域，存储直接后继存储位置的域称为指针域。
结构如下：
然而在我们实际的运用中，它的结构却是以下类型：
因此这里有我们需要注意的地方：
1.链式结构逻辑上是连续的，但物理上并不一定是连续的；
2.现实中的节点一般是从堆上申请来的；
3.从堆上申请的空间，是按照一定的策略的，在次申请可能是连续的也可能是不连续的。
2. 链表的分类
根据链表结点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等。其中单链表、循环链表和 向链表用于实现线性表的链式存储结构，其他形式多用于实现树和图等非线性结构。
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
- 单向或者双向
- 带头或者不带头
- 循环或者非循环
注意：虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
3.接口实现
// 动态申请一个结点 SLTNode* BuySLTNode(SLTDataType x); SLTNode* CreateSList(int n); // 单链表打印 void SLTPrint(SLTNode* phead); // 单链表尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x); // 单链表的尾删 void SLTPopBack(SLTNode** pphead); // 单链表的头插 void SLTPushFront(SLTNode** pphead, SLTDataType x); // 单链表头删 void SLTPopFront(SLTNode** pphead); // 单链表查找 SLTNode* SListFind(SLTNode* plist, SLTDataType x); // 单链表在pos位置之后插入x void SListInsertAfter(SLTNode* pos, SLTDataType x); // 单链表删除pos位置之后的值 void SListEraseAfter(SLTNode* pos); // 在pos之前插入x void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); // 删除pos位置 void SListErase(SLTNode** pphead, SLTNode* pos);
接下来我们便一一进行实现！
3.1动态申请一个结点
代码如下：
SLTNode* BuySLTNode(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.2创建单链表
SLTNode* CreateSList(int n) { SLTNode* phead = NULL, *ptail = NULL; int x = 0; for (int i = 0; i < n; ++i) { SLTNode* newnode = BuySLTNode(i); if (phead == NULL) { ptail = phead = newnode; } else { ptail->next = newnode; ptail = newnode; } } return phead; }
3.3遍历单链表
void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n");//便于调试 }
思路：
我们对单链表进行遍历操作，整体思路还是从开头挨着遍历，直到我们的指针指向空的时候就完成相应的操作。
3.4尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* tail = *pphead; // 找尾 while (tail->next) { tail = tail->next; } tail->next = newnode; } }
思路：
每次都将新的结点链接到链表的最后一个结点的后面，从而达到创建单链表的过程，我们这里用到二级指针来接收实参，因为在函数传参时如果想改变实参，则需要我们传递实参的地址，那么同样想要改变首地址，则需要传递首地址的地址。
3.5尾删
void SLTPopBack(SLTNode** pphead) { // 暴力的检查 assert(*pphead); // 温柔的检查 //if (*pphead == NULL) // return; if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* tail = *pphead; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
思路：
当进行尾删操作时我们有两种情况需要进行考虑：
如果是正常情况下的删除操作，我们就需要找到该链表最后一个节点的前一个节点，然后将这个节点的 next指针指向由最后一个节点改变为null；
如果链表最后只剩下一个结点，则直接释放到即可，然后还是数据域置空。
3.6头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySLTNode(x); newnode->next = *pphead; *pphead = newnode; }
思路：
首先初始化一个单链表，其头结点为空，然后循环插入新结点：将新节点的next指向头结点的下一个结点，然后将头结点的next指向我们的新节点。（思路同尾插类似）
3.7头删
void SLTPopFront(SLTNode** pphead) { assert(*pphead); SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; }
思路：
删除第一个结点依然需要修改我们的头部指针，所以还是需要用到二级指针。
3.8查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
思路：
查找值x在单链表L中的结点指针，从单链表的第一个结点开始，依次比较表中各个结点的数据域的值，若某结点数据域的值等于x，则返回该结点的指针；若整个单链表中没有这样的结点，则返回空。
3.9在pos后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuySLTNode(x); newnode->next = pos->next; pos->next = newnode; }
思路：
这里注意的是指针链接的顺序问题，如果改变链接的顺序则会出现自己指向自己的情况！
3.10在pos之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pos); if (*pphead == pos) { SLTPushFront(pphead, x); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } SLTNode* newnode = BuySLTNode(x); prev->next = newnode; newnode->next = pos; } }
思路：
这种操作的情况还是有两种：
第一种就是当我们以头结点为pos位置，那么就演变为头插操作；
第二种就是正常的插入，我们就需要从头开始去查找pos位置的前一个位置，接着就是结点的链接的顺序一定要注意。
3.11删除pos之后的值
void SLTEraseAfter(SLTNode* pos) { assert(pos); if (pos->next == NULL) { return; } else { SLTNode* nextNode = pos->next; pos->next = nextNode->next; free(nextNode); } }
思路：
最后一个位置我们需要特别注意，开始时先判断。不能写成pos->next=pos->next->next，使用这种我们需要开始时先保存pos->next。
3.12删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pos); assert(*pphead); if (pos == *pphead) { SLTPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); //pos = NULL; } }
思路：
这里还是两种情况：
第一种当删除的pos位置为最后一个结点时，相当于尾删操作此时；
第二种就是正常的删除操作，跟之前的有类似
总结：以上就是关于单链表的所有的内容知识，希望大家多多指教！
