2.3.1 单链表的存储结构
所谓线性表的链式存储，是指采用一组任意的存储单元存放线性表中的元素。这组存储单元可以是连续的，也可以是不连续的。为了表示这些元素之间的逻辑关系，除了需要存储元素本身的信息外，还需要存储指示其后继元素的地址信息。这两部分组成的存储结构，称为结点。结点包括两个域：数据域和指针域。其中，数据域存放数据元素的信息，指针域存放元素的直接后继的存储地址。如图2.8所示。
图2.8 结点结构
通过指针域把n个结点根据线性表中元素的逻辑顺序链接在一起，就构成了链表。由于链表中的每个结点的指针域只有一个，这样的链表称为线性链表或者单链表。
例如，一个采用链式存储结构的线性表（Yang,Zheng, Feng,Xu,Wu,Wang,Geng）的存储结构如图2.9所示。
存取链表中的元素时，必须从头指针head出发，头指针head指向链表的第一个结点，从头指针head可以找到链表中的每一个元素。
图2.9 线性表的链式存储结构
单链表的每个结点的地址存放在其直接前驱结点的指针域中，而第一个结点没有直接前驱结点，因此需要一个头指针指向第一个结点。同时，由于表中的最后一个元素没有直接后继，需要将单链表的最后一个结点的指针域置为“空”（NULL）。
一般情况下，我们只关心链表的逻辑顺序，而不关心链表的实际存储位置。通常用箭头代替指针来连接结点序列。因此，图2.9所示的线性表可以形象化为如图2.10所示的序列。
图2.10 单链表的逻辑状态
有时为了操作上的方便，在单链表的第一个结点之前增加一个结点，称为头结点。头结点的数据域可以存放线性表的附加信息，如线性表的长度；头结点的指针域存放第一个结点的地址信息，即指向第一个结点。头指针指向头结点，不再指向链表的第一个结点。带头结点的单链表如图2.11所示。
若带头结点的链表为空链表，则头结点的指针域为“空”，如图2.12所示。
图2.11 带头结点的单链表
图2.12 带头结点的单链表
单链表的存储结构用C语言描述如下：
其中，ListNode为链表的结点类型，LinkList为指向链表结点的指针类型。如果有定义：
则定义了一个链表，L指向该链表的第一个结点。它和下面的定义含义相同：
对于不带头结点的链表，如果链表为空，则有L=NULL；对于带头结点的链表，如果链表为空，则L->next=NULL。