【数据结构笔记】单链表
链表是线性表的一种存储结构。关于线性表的概念，可以查看上一篇笔记【数据结构笔记】顺序表——静态分配
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。其在物理地址上的存储示意图如下：
链表分为：单链表、循环单链表、双链表、循环双链表、静态链表。
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
结点可分为：头结点、开始结点（首元结点）、其他结点。
（1）头结点：其值域不包含任何信息。不是必须的，根据实际情况建立。
（2）开始结点：开始结点也称做首元结点，代表链表中第一个存有数据的结点。
（3）其他结点：除了头结点与开始结点之外的结点。
链表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个链表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。
当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱。
（ps：顺序表前驱和后继的概念也是如此）
头指针head永远指向链表第一个节点的位置，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据。
链表中有头结点时，头指针指向头结点；反之，若链表中没有头结点，则头指针指向开始结点。链表完整示意图如下：
（1）带头结点的单链表：头指针head指向头结点。头指针head始终不等于NULL，head->next等于NULL的时候链表为空。
（2）不带头结点的单链表：头结点head指向开始结点，当head等于NULL时链表为空。
/* 数据元素类型 */
typedef int ListType;
/* 单链表结点定义 */
typedef struct LNode
{
ListType data; //数据域
struct LNode *next; //指针域，指向直接后继元素
}LNode;
使用头插法创建一个链表：（5，2，0，13，14），代码如下
因为链表不支持随机访问，即链表的存取方式是顺序存取的（注意“存储”与“存取”是两个不一样的概念），所以要查找某结点，必须通过遍历的方式查找。
例如：如果想查找第5个结点，必须先遍历走过第1~4个结点，才能得到第5个结点。代码如下：
要修改某结点的数据域，首先通过遍历的方法找到该结点，然后直接修改该结点的数据域的值。代码如下：
插入结点的位置有三种：
（1）插入到链表的首部，也就是头结点和开始结点之间；
（2）插入到链表中间的某个位置；
（3）插入到链表的末端。
虽然插入的位置有区别，都使用相同的插入手法。分为两步，如上图所示：
（1）将新结点的next指针指向插入位置的后一个结点；
（2）将插入位置的前一个结点的next指针指向插入结点。
代码如下：
当需要从链表中删除某结点时，需要进行两部操作：
（1）将结点从链表中摘下来，即修改指针指向为：被删除结点的前一个结点的next指针指向被删除结点之后的结点。
（2）手动释放掉被删除结点所占用的内存。
代码如下：
程序运行结果为：