数据结构：单链表
一、单链表的概念
介绍
在之前我们学习了逻辑结构和物理结构都是线性的顺序表，但是我们会发现顺序表有以下 3 个比较明显的缺陷：
- 中间/头部的插入删除，时间复杂度为 O(N)。
- 增容需要申请新空间，拷贝数据，释放旧空间，有不小的消耗。
- 增容一般呈两倍的增长，会有一定的空间浪费。
而链表可以很好的解决该问题：
首先，先介绍一下链表的基础知识：
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，即：逻辑顺序通过指针链接的线性数据结构。它由多个节点组成，每个节点包含 数据域（存储具体值）和 指针域（存储下一个节点的地址），通过指针域建立节点间的逻辑关系，形成线性序列（如 A→B→C→NULL）。
例：
每个节点包含 数据域（存储具体值）和 指针域（存储下一个节点的地址）。形象化来看：数据域方面用数字来表示，指针域方面用 next，表示：
图中指针变量 list 保存的是第一个结点的地址，我们称 list 此时'指向'第一个结点，如果我们希望 list'指向'第二个结点时，只需要修改 plist 保存的内容为 next 即可，链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。
结构上非连续，非顺序，但它的逻辑结构还是线性的。我们可以把链表想象成火车的一节节车厢链接在一起，只不过不是通过下标来访问节点了，是通过每个节点的地址来访问下一个节点。
所以，回到上文，链表刚好可以使头部插入与删除的时间复杂度为 O(1)，不需要增容也不存在空间的浪费。提高使用的效率。
二、单链表的结构
介绍
简单来说：
单链表，链表是由一个一个节点组成的，它的节点由两个组成部分数据域：保存的数据。指针域：指针，存放的是下一个结点的地址。
根据前面的知识，我们可以得出链表的结构：
#include<stdio.h>
typedef int type;
typedef struct SListNode {
type data;
struct SListNode* next;
} SListNode;
当然，数据域的内容并不唯一，你也可以写其他或很多的成员的。当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个结点的地址（当下一个结点为空时保存的地址为空）。当我们想要从第一个结点走到最后一个结点时，只需要在当前结点拿上下一个结点的地址就可以了。
具体使用例子：
#include<stdio.h>
type;
type data;
} SListNode;
{
SListNode* node1 = (SListNode*)((SListNode));
SListNode* node2 = (SListNode*)((SListNode));
SListNode* node3 = (SListNode*)((SListNode));
SListNode* node4 = (SListNode*)((SListNode));
node1->data = ;
node1->next = node2;
node2->data = ;
node2->next = node3;
node3->data = ;
node3->next = node4;
node4->data = ;
node4->next = ;
}
