链表的实现（文末附完整代码）
链表的概念及结构
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 我们在上一篇文章所学习的顺序表是连续存储的 例如： 顺序表就好比火车上的一排座位，是连续的 而链表就好比是火车的各节车厢，中间有东西将其互相连接的
链表的基本结构图如下： 有一个指针指向下一个节点
链表的概念及结构
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构： 链表可以是单向和双向，循环和不循环，带头和不带头，这样一组合，就会出现八种类型的列表 单向的列表如下：
双向列表： 相比较单向，双向的增删查改较为容易，他会自带一个prev的节点，能顾标记当前节点的前一个节点
循环列表： 其实循环列表就是最后一个节点指向了开头节点
带头和不带头： 头节点我们可以称其为哨兵位，它是不会在链表中存储有效的数据的
其实八种链表我们最常用的只有两种： 无头单向非循环链表：
带头双向循环列表：
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构
- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是后面的学习中你会发现其实他是比较简单的
链表的实现
首先我们要了解的就是单链表的实现： 头文件如下：
#include<stdio.h>
#include<assert.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode** plist);新节点的创建： 我们要创建一个节点，首先就是要为他动态开辟一个空间 然后再将这个新节点newnode的值赋予x，并且将他的next置为空，然后函数返回这个节点
SListNode* BuySListNode(SLTDateType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}链表的打印： 打印链表是我们可以用一个符号->来代替空格，但是链表实际上是没有这个符号的 我们可以首先定义cur，从链表的第一个节点开始遍历，知道cur为空时，就不会打印了，并且打印一次cur的data，cur要等于cue的next
void SListPrint(SListNode* plist)
{
SListNode* cur = plist;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}单链表的尾插： 这里我们要注意的是要记得用二级指针，因为当链表为空时，我们要改变的是节点的地址，而我们要改变地址，就要用地址的地址，也就是二级指针 首先，需要插入一个节点我们要做的就是创建一个新节点，我们之前定义了的一个函数直接使用 然后我们创建一个tail指针，让他从链表的第一个位置开始遍历，一直遍历到最后一个节点，此时令tail的next等于newnode即可
void SListPushBack(SListNode** pplist, SLTDateType x)
{
assert(pplist);
/*assert(*pplist);*///链表为空时可以尾插
SListNode* newnode = BuySListNode(x);
if (*pplist == NULL)
{
*pplist = newnode;
}
else
{
SListNode* tail = *pplist;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}单链表的头插： 头插比较简单，我们直接将新节点的next等于链表的第一个节点即可，也就是*pplist，我们传进来的是**pplist，是节点地址的地址，所以我们需要解引用一次才能将地址给newnode的next
void SListPushFront(SListNode** pplist, SLTDateType x)
{
SListNode* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}单链表的尾删： 尾删的情况我们要分为两种： 1.只有一个节点时： 只有一个节点时我们直接free掉这个节点，其次为了防止野指针，我们要将其置空 2.当有多个节点时： 我们创建一个tail和prev，然后用循环将tail遍历到最后一个节点，循环的终止条件时tail->next为空，条件满足时就将tail赋予prev，当跳出循环时，prev就是尾节点的前一个节点，我们直接将tail给free掉，将其置空，这样尾节点就被删除了
void SListPopBack(SListNode** pplist)
{
assert(*pplist);//链表为空时不能再删，暴力检查
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SListNode* prev = NULL;
SListNode* tail = *pplist;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}单链表的头删： 头删就很简单了，首先定义一个tail存入第一个节点的位置，然后将第一个节点的位置移动到他的next，注意记得将临时存储第一个节点位置的指针给free掉，避免出现野指针的问题
void SListPopFront(SListNode** pplist)
{
assert(*pplist);//链表为空时不能再删，暴力检查
SListNode* tail = *pplist;
*pplist = (tail)->next;
free(tail);
}节点的查找： 节点的查找也比较容易，直接用while循环遍历，如果cur的data和x相等，就返回cur，否则就是没有这个节点，返回null
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
SListNode* cur = plist;
while (cur->next)
{
if (cur->data == x)
{
return cur;
//break;
}
cur = cur->next;
}
return NULL;
}在一个节点之后插入节点： 需要插入节点首先要做的就是创建一个新节点 然后首先要做的是将newnode的next连接到要插入位置pos的next 再将pos的next置为newnode 这里注意，位置不能颠倒，不然newnode的next就找不到了
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}删除一个节点之后的节点： 要删除节点之后的一个节点，首先这个节点之后一定要有一个节点，所以要对pos->next进行断言 我们将pos->next存储到next中，然后将pos->next直接指向next->next即可，也就是把pos->next=pos->next->next
void SListEraseAfter(SListNode* pos)
{
assert(pos);
assert(pos->next);
//pos->next = pos->next->next;
SListNode* next = pos->next;
pos->next = next->next;
free(next);
}单链表的销毁： 直接将pplist置空即可
void SListDestroy(SListNode** pplist)
{
SListNode* node = *pplist;
node = NULL;
free(node);
}好了，今天的分享到这里就结束了，感谢大家的支持！ 完整代码如下：
SListNode* BuySListNode(SLTDateType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListPrint(SListNode* plist)
{
SListNode* cur = plist;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
void SListPushBack(SListNode** pplist, SLTDateType x)
{
assert(pplist);
/*assert(*pplist);*///链表为空时可以尾插
SListNode* newnode = BuySListNode(x);
if (*pplist == NULL)
{
*pplist = newnode;
}
else
{
SListNode* tail = *pplist;
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SListPushFront(SListNode** pplist, SLTDateType x)
{
SListNode* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
void SListPopBack(SListNode** pplist)
{
assert(*pplist);//链表为空时不能再删，暴力检查
//SListNode* tail = pplist;
//while (tail->next->next)
//{
// tail = tail->next;
//}
//free(tail->next);
//tail->next = NULL;
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SListNode* prev = NULL;
SListNode* tail = *pplist;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
void SListPopFront(SListNode** pplist)
{
assert(*pplist);//链表为空时不能再删，暴力检查
SListNode* tail = *pplist;
*pplist = (tail)->next;
free(tail);
}
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
SListNode* cur = plist;
while (cur->next)
{
if (cur->data == x)
{
return cur;
//break;
}
cur = cur->next;
}
return NULL;
}
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SListEraseAfter(SListNode* pos)
{
assert(pos);
assert(pos->next);
//pos->next = pos->next->next;
SListNode* next = pos->next;
pos->next = next->next;
free(next);
}
void SListDestroy(SListNode** pplist)
{
SListNode* node = *pplist;
node = NULL;
free(node);
}