单链表的定义
链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。因此，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系。除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这里把存储数据元素信息的域称为数据域，把存储直接后继存储位置的域称为指针域；指针域中存储的信息称为指针或链；这两部分信息组成数据元素ai的存储映像，称为节点（Node）。
具有n个结点（的存储映像）链接成一个链表，即为线性表的链式存储结构。由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。如图所示：
单链表有头有尾，整个链表的存储必须从头指针开始进行，头指针指示链表中的第一个结点（即第一个数据元素的存储映像，也称为首元结点）的存储位置。尾结点就是最后一个数据元素，没有直接后继，则单链表中最后一个结点的指针为空（NULL）。如图所示：
通常单链表在第一个结点前附设一个结点，称为头节点。头节点的数据域可以不存储任何信息，也可以存储如链表长度等附加信息；头节点的指针域存储指向第一个结点的指针。如图所示：
单链表可由头指针唯一确定，在C语言中可用“结构指针” 来描述：
typedef struct _LinkedListNode
{
ElemType data; //数据类型
struct _LinkedListNode* next; //指向直接后继元素的指针
}LinkedListNode, *LinkedList;
- 该结构体定义单链表中每个结点的存储结构，其中包括：存储结点的数据域data，其类型标识符ElemType可以表示int、char、float等，也可以表示自定义的数据类型；存储后继结点位置的指针域next，其类型为指针类型_LinkedListNode*。
- 结构体名称LinkedListNode和*LinkedList是等价的。通常习惯用LinkedList定义单链表，强调定义的是单链表的头指针；用LinkedListNode*定义单链表中任意结点的指针变量。
- 单链表是由表头指针唯一确定，因此单链表可以用头指针的名称命名。若头指针名是L，则简称链表为表L。
- 注意区分指针变量和结点变量是两个不同的概念。定义LinkedListNode *p和LinkedList p，则p为指向结点的指针变量，表示该结点的地址；而*p为对应的结点变量，表示该结点的名称。
- 假设p是指向单链表中第i个元素的指针，则结点ai的数据域用，p->data来表示；结点的指针域，用p->next来表示；p->next指向第i 1个元素，即指向的指针。可以用下图表示：
