什么是单链表？线性表的链式存储

线性表的链式存储是用通过指针链接起来的结点来存储数据元素，基本的结点结构如下图1所示：
图1：

其中，数据域用于存储数据元素的值，指针域则存储当前元素的直接前驱或直接后继的位置信息。指针域中的信息称为指针（或链）。

存储各数据元素的结点的地址并不要求是连续的，因此存储数据元素的同时必须存储元素之间的逻辑关系。另外，结点空间只有在需要的时候才申请，无须事先分配。

结点之间通过指针域构成一个链表，若结点中只有一个指针域，则称为线性链表（或单链表），如下图2所示为：线性表的单链表存储。
图2:
设线性表中的元素是整型，则单链表结点类型的定义为:

typedef struct node{
	int data;                 /*结点的数据域，此处假设为整型*/
	struct node *next;        /*结点的指针域*/
}NODE,*LinkList;

在链式存储结构中，只需要一个指针（称为头指针，如图2中的head）指向第一个结点，就可以顺序的访问到表中任意一个元素。

在链式存储结构下进行插入和删除，其实质都是对相关指针的修改。在单链表中若在p所指结点结点后插入新元素结点（s所指结点，已经生成），如图3-3（a）所示，其基本步骤如下。

（1）s —＞next = p —＞next;
（2） p —＞next = s;

即先将P所指结点的后继结点指针赋给S所指结点的指针域，然后将P所指结点的指针域修改为指向S所指结点

同理，在单链表中删除P所指结点的后继结点时（如图3-3（b）所示），步骤如下：

（1）q = p —＞next;
（2）p —＞next = p —＞next —＞next;
（3）free(q);

即先令临时指针 q 指向待删除的结点，然后修改 p 所指结点的指针域为指向 p 所指结点的后继的后继结点，从而将元素b 所在的结点从链表中删除，最后释放q所指结点的空间。

在实际应用中，为了简化对链表状态的判定和处理，特别引入一个不存储数据元素的结点称为头节点，将其作为链表的第一个结点并令头指针指向该结点。