链表的概念及分类
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。这种解释听起来有点抽象，我们可以把它想象成一列火车的车厢。如果没有连接装置，每个车厢都是独立的；而链表就像是用挂钩把车厢连起来，虽然它们在轨道上的物理位置可能不挨着，但通过挂钩（指针）实现了逻辑上的连续。
链表的常见分类
实际应用中链表的结构非常多样，组合起来主要有八种情况，比如单向与双向、带头或不带头、循环与非循环。尽管类型繁多，但使用率最高的主要是两种：
- 无头单向非循环链表：结构简单，通常不作为独立的数据存储结构，更多作为其他数据结构（如哈希桶、图的邻接表）的子结构存在。在笔试面试中考察频率很高。
- 带头双向循环链表：结构最复杂，但功能最强，常用于单独存储数据。虽然实现起来稍繁琐，但一旦写好，很多边界条件的处理反而变得简单了。
下面我们以无头单向非循环链表为例，详细拆解其实现过程。
链表的实现细节
1. 定义链表结构
在动手写接口之前，先定义好节点的结构。每个节点包含数据域和指向下一个节点的指针域。
typedef int SLTDateType;
typedef struct SListNode {
SLTDateType data;
struct SListNode* next;
} SListNode;
2. 动态申请节点
创建新节点需要动态分配内存，并检查分配是否成功。
SListNode* BuySListNode(SLTDateType x) {
SListNode* temp = (SListNode*)malloc(sizeof(SListNode));
if (temp == NULL) {
perror("malloc");
return NULL;
}
temp->data = x;
temp->next = NULL;
return temp;
}
3. 打印链表
遍历链表直到遇到空指针，直观地查看当前状态。
void SListPrint(SListNode* plist) {
SListNode* cur = plist;
while (cur != NULL) {
printf("%d->", cur->data);
cur = cur->next;
}
();
}
