2.4 线性表的内容精要（2）——线性表的链式表示
2.4.1 单链表的存储结构
线性表的链式存储是采用一组任意的存储单元存放线性表的元素。这组存储单元可以是连续的，也可以是不连续的。因此，为了表示每个元素ai与其直接后继元素ai+1的逻辑关系，除了存储元素本身的信息外，还需要存储一个指示其直接后继元素的信息（即直接后继元素的地址）。这两部分构成的存储结构称为结点（node）。结点包括数据域和指针域两个域，数据域存放数据元素的信息，指针域存放元素的直接后继元素的存储地址。指针域中存储的信息称为指针。结点结构如图2-8所示。
通过指针域将线性表中n个结点元素按照逻辑顺序链在一起就构成了链表。例如，链表（Hou，Geng，Zhou，Hao，Chen，Liu，Yang）在计算机中的存储情况如图2-9所示。由于链表中每个结点只有一个指针域，所以这样的链表被称为线性链表或者单链表。
图2-8 结点结构
图2-9 一个单链表的存储结构
单链表的每个结点的地址存放在其直接前驱结点的指针域中，第一个结点没有直接前驱结点，因此需要一个头指针指向第一个结点。由于表中的最后一个元素没有直接后继元素，需要将单链表的最后一个结点的指针域置为“空”（用^表示空）。
为了存取链表中的元素，需要令头指针head指向链表中的第一个结点，从head依次访问每个结点，从而找到每个元素。实际上，我们只关心链表中结点的逻辑顺序，而不关心它的实际存储位置。通常用箭头表示指针，链表可表示成通过箭头链接起来的序列。图2-9所示的线性表可以形象地表示成如图2-10所示的序列。
图2-10 单链表的逻辑状态
为了操作方便，在单链表的第一个结点之前增加一个结点，称为头结点。头结点的数据域可以存放如线性表的长度等信息，头结点的指针域存放第一个元素结点的地址信息，使其指向第一个元素结点。带头结点的单链表如图2-11所示。
若带头结点的链表为空链表，则头结点的指针域为“空”（用^表示空），如图2-12所示。
图2-11 带头结点的单链表
图2-12 带头结点的单链表
注 意
初学者需要区分头指针和头结点的区别。头指针是指向链表第一个结点的指针，若链表有头结点，则是指向头结点的指针。头指针链表的必要元素具有标识作用，所以常用头指针冠以链表的名字。头结点是为了操作的统一和方便而设立的，放在第一个元素结点之前，不是链表的必要元素。有了头结点，对在第一个元素结点前插入结点和删除第一个结点，其操作与其他结点的操作就统一了。
单链表的存储结构用C语言描述如下：
其中，ListNode是链表的结点类型，LinkList是指向链表结点的指针类型。假设有如下定义。
则L被定义为指向单链表的指针类型，相当于如下定义。
