链表头

图1为线性表（ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG）的逻辑状态。头指针 指示链表中第一个结点（即第一个数据元素的存储映像）的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”（NULL）。

图１ 线性链表的逻辑状态

由上述描述可见，单链表可由头指针来唯一确定，在C语言中可用“结构指针”来描述。

//-----线性表的单链表存储结构-----
typedef struct LNode{
    ElemType   data;
    struct LNode  *next;
}LNode, *LinkList;

有时在单链表的第一个结点之前附设一个结点，称之为头结点 。 头结点的数据域可以不存储任何信息，也可以存储如线性表长度等类的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。如图２(a)所示，此时，单链表的头指针指向头结点。若线性表为空，则头结点的指针域为“空”，如图２(b)所示。

图2 带头结点的单链表   (a)非空表；(b)空表