前言
即顺序表之后，今天给大家带来另外一个线性结构——链表。
1.链表的概念及结构
链表是一种 物理存储结构上非连续 、非顺序的存储结构，数据元素的 逻辑顺序 是通过链表
中的 指针链接 次序实现的 。
虽然链表在存储未位置上是不连续的，但在逻辑上其又是连续的，具体结构如下：
2.链表的实现
2.1 准备工作
和顺序表一样，这里我们准备三个文件
Slist.c——对链表相关功能的实现
Slist.h——进行有关函数的声明
Text.c——对有关功能的实现
2.2 链表结构声明
typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode;
这里我们用data存储相关内存，用结构体指针next存储下一个节点的位置。
2.3 动态节点的申请
由于链表是通过一个一个节点在逻辑上连续实现的，所以创建节点是我们必须需要的操作，这里我们就将其封装成一个函数，以便每次的使用
SListNode* BuySListNode(SLTDateType x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->data = x; newnode->next = NULL; return newnode; }
2.4 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x) { assert(pplist); SListNode*newnode= BuySListNode(x); if (*pplist == NULL) { *pplist = newnode; } else { SListNode* tail=*pplist; while (tail->next) { tail = tail->next; } tail->next = newnode; } }
这里我们采用的是无哨兵位的单链表，所以头指针为空时我们直接将头指针指向新节点，如果头指针后有节点我们就用tail指针找到尾节点，然后让尾节点的next指向新节点实现插入，还有一点是这里我们要传二级指针，由于形参是对实参的复制，所以我们要改变头节点时，只传一级指针时，并不可以改变头节点的指向，比如
此时头指针s还是指向NULL，我们只是把形参这个指针指向了新节点而已，并没有改变链表结构。
对于具体的尾插操作这里我给大家实际演示一下：
2.5 打印函数的实现
实现打印函数，以便我们更好的测试我们所实现的函数
void SListPrint(SListNode* plist) { SListNode* cur = plist; while (cur) { printf("%d-> ", cur->data); cur = cur->next; } printf("NULL\n"); }
这里解释一下为什么传的是一级指针，由于我们这里只是打印链表，对链表的头节点不进行改变，所以这里我们直接传一级指针即可。
接下来我们就对我们的后插进行测试：
void text3()
{ SListNode* s = NULL; SListPushBack(&s, 1); SListPushBack(&s, 2); SListPushBack(&s, 3); SListPushBack(&s, 4); SListPrint(s); } int main() { text3(); return 0; }
结果展示：
2.6 单链表尾删
void SListPopBack(SListNode** pplist) { assert(pplist); assert(*pplist); if ((*pplist)->next==NULL) { free(*pplist); *pplist = NULL; } else { SListNode* tail = *pplist; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
这里我给大家解释一下上面的两个断言，首先我们二级指针存储的是单链表头节点的地址，所以该不可能为空，其次由于是进行删除操作，所以单链表不可能为空，所以解引用后，该是不可能为空指针的，所以我们要对该进行断言操作。
其次这里的删除一共有两种情况：
第一是头指针后只有一个节点：
这里我们只需要把头指针给释放掉就行。
第二种情况就是头指针后不止一个节点，这里我们如果只使用一个指针对其进行删除操作，那么我们只需要找到尾节点的头一个节点，然后通过next释放掉尾节点，将尾节next置空，具体如下
还有一种我们可以使用两个指针，一个保存尾节点，一个保存尾节点的头一个节点 ，然后释放尾节点，对尾节点头一个节点的next进行置空，具体如下：
这里代码就不给大家演示，大家可以自己写一写看。
测试如下：
void text3() { SListNode* s = NULL; SListPushBack(&s, 1); SListPushBack(&s, 2); SListPushBack(&s, 3); SListPushBack(&s, 4); SListPrint(s); SListPopBack(&s); SListPopBack(&s); SListPrint(s); } int main() { text3(); return 0; }
结果演示：
