一、顺序表的问题及思考
在顺序表的实现中，可以发现以下问题：
- 中间/头部插入删除：时间复杂度为 O(N)，效率低下。
- 增容消耗：需要申请新空间，拷贝数据，释放旧空间（realloc），导致运行速度下降。
- 空间浪费：增容一般是呈 2 倍的增长，势必会有一定的空间浪费。
为了应对以上问题，引入了链表的概念。
二、链表的概念及结构
1. 概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表是线性表的一种。
类比：火车由一节节车厢连接而成，物理上不连续，但逻辑上可通过前一节找到后一节。链表同理。
2. 结构
链表由一个个节点组成，每个节点包含数据 data 和指向下一个节点的指针。
定义如下：
底层为结构体。S 代表 Single（单个），node 是节点的意思。typedef 用于重定义链表的名字。
三、链表的实现
1. 头文件声明及定义
创建 .h 文件完成函数声明，.c 文件完成实现及测试。链表支持'增删查改'功能。
参数说明：pos 表示指向指定位置的指针，phead 表示链表头节点的指针，pphead 表示头节点指针的地址（二级指针）。
2. 函数实现及测试
打印函数
传链表头节点的地址（传址调用）。创建 pcur 指针遍历链表，当 pcur 为空时结束，打印 NULL。
节点申请函数
封装函数申请新节点，返回 SLTNode*。使用 malloc 开辟空间，若失败则 perror 并 exit。成功则置入值 x，next 置空，返回 newnode。
尾插函数
思想：遍历链表找到尾节点，将新节点与尾节点相连。
- assert 断言 pphead，申请新节点。
- 判断链表是否为空，为空则插入头节点处。
- 不为空则遍历，将 newnode 赋给尾节点的 next 指针。
测试显示成功尾插 1、2 两个数据。
头插函数
- assert 断言 pphead。
- 申请新节点，让新节点的 next 指针指向头节点。
- 让头节点地址变成 newnode（需二级指针）。
测试显示在原链表基础上头插了 3、4 这两个值。
尾删功能
- assert pphead 不能为空且 *pphead 不能为空。
- 判断节点数目：
- 只有一个节点：free 释放头节点并置为空。
- 多个节点：遍历找到尾节点 ptail 和前一个节点 prev，free 释放尾节点，prev->next 置为空。
测试显示尾部 1、2 被删除。
头删功能
- 断言。
- 将头节点的 next 指针存入新创建的 next 指针中，让新的头节点指向 next。
测试成功头删 4。
查找功能
- 创建指针 pcur 指向头节点（不修改原头节点）。
- 遍历，找到与 x 相等 data 并返回该指针，未找到返回 NULL。
测试成功。
指定位置之前插入
- 断言。
- 若 pos 等于头节点位置，直接调用头插函数。
- 否则遍历找到 pos 之前的节点 prev，让 prev->next 指向 newnode，newnode->next 指向 pos。
测试通过。
指定位置之后插入
- 创建新节点 pos，让 pos->next 赋给 newnode->next。
- 再将 newnode 赋给 pos->next。
测试通过。
删除 pos 处节点
- 断言 pphead、*pphead、pos 不为空。
- 若 pos 等于 *pphead，调用头删函数。
- 否则创建 prev 找到 pos 前一个节点，将 pos->next 赋值给 prev->next，free 释放 pos，并将 pos 置为空防止野指针。
测试通过。
删除 pos 之后的节点
- 断言 pos 和 pos->next 不为空。
- 创建 del 指针保存 pos->next。
- 将 pos->next 指向 del->next，free 释放 del 并置空。
测试通过。
链表销毁
- 函数 SListDestroy，断言 pphead 和 *phead 不为空。
- 创建 pcur 指向头节点，循环遍历，将 pcur->next 存入 next，free pcur，pcur=next。
- 直到 pcur 为空，将头节点地址置为 NULL。
测试显示销毁成功，打印 NULL。
以上就是链表基本功能的实现。
