2.5.1单链表的定义和表示
线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素
与其直接后继数据元素
之间的逻辑关系，对数据元素
来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素
的存储映像，称为结点（node）。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。n个结点（
（1≤i≤n）的存储映像）链结成一个链表，即为线性表
的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。
根据链表结点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等。其中单链表、循环链表和双向链表用于实现线性表的链式存储结构，其他形式多用于实现树和图等非线性结构。
本节先讨论单链表，例如，图2.7所示为线性表的单链表存储结构，整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映像，也称首元结点）的存储位置。同时，由于最后一个数据元素没有直接后继，则单链表中最后一个结点的指针为空（NULL）。
图2.7单链表示例用单链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，由此，这种存储结构为非顺序映像或链式映像。
通常将链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针。图2.7所示的单链表可画成如图2.8所示的形式，这是因为在使用链表时，关心的只是它所表示的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置。
图2.8单链表的逻辑状态由上述可见，单链表可由头指针唯一确定，在C语言中可用“结构指针”来描述：
说明
（1）这里定义的是单链表中每个结点的存储结构，它包括两部分：存储结点的数据域data，其类型用通用类型标识符ElemType表示（例如，用链表表示案例2.1中的图书信息时，只需将ElemType替换为2.4.1定义的Book数据类型即可）；存储后继结点位置的指针域next，其类型为指向结点的指针类型LNode*。
（2）为了提高程序的可读性，在此对同一结构体指针类型起了两个名称，LinkList与LNode*，两者本质上是等价的。通常习惯上用LinkList定义单链表，强调定义的是某个单链表的头指针；用LNode*定义指向单链表中任意结点的指针变量。例如，若定义LinkListL，则L为单链表的头指针，若定义LNode*p，则p为指向单链表中某个结点的指针，用*p代表该结点。当然也可以使用定义LinkListp，这种定义形式完全等价于LNode*p。
（3）单链表是由表头指针唯一确定的，因此单链表可以用头指针的名字来命名。若头指针名是L，则简称该链表为表L。
（4）注意区分指针变量和结点变量两个不同的概念，若定义LinkListp或LNode*p，则p为指向某结点的指针变量，表示该结点的地址；而*p为对应的结点变量，表示该结点的名称。
一般情况下，为了处理方便，在单链表的第一个结点之前附设一个结点，称之为头结点。图2.8所示的单链表增加头结点后如图2.9所示。
图2.9增加头结点的单链表的逻辑状态下面对首元结点、头结点、头指针三个容易混淆的概念加以说明。
说明
（1）首元结点是指链表中存储第一个数据元素a1的结点。如图2.8或图2.9所示的结点“ZHAO”。
（2）头结点是在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可存储与数据元素类型相同的其他附加信息。例如，当数据元素为整数型时，头结点的数据域中可存放该线性表的长度。
（3）头指针是指向链表中第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头结点；若链表不设头结点，则头指针所指结点为该线性表的首元结点。
链表增加头结点的作用如下。
（1）便于首元结点的处理增加了头结点后，首元结点的地址保存在头结点(即其“前驱”结点)的指针域中，则对链表的第一个数据元素的操作与其他数据元素相同，无需进行特殊处理。
（2）便于空表和非空表的统一处理当链表不设头结点时，假设L为单链表的头指针，它应该指向首元结点，则当单链表为长度n为0的空表时，L指针为空（判定空表的条件可记为：L==NULL）。增加头结点后，无论链表是否为空，头指针都是指向头结点的非空指针。如图2.10（a）所示的非空单链表，头指针指向头结点。若为空表，则头结点的指针域为空（判定空表的条件可记为：Lnext==NULL），如图2.10（b）所示。
图2.10带头结点的单链表在顺序表中，由于逻辑上相邻的两个元素在物理位置上紧邻，则每个元素的存储位置都可从线性表的起始位置计算得到。而在单链表中，各个元素的存储位置都是随意的。然而，每个元素的存储位置都包含在其直接前驱结点的信息之中。假设p是指向单链表中第i个数据元素（结点
，即数据域为
的结点）的指针，则pnext是指向第i+1个数据元素（结点
）的指针。换句话说，若pdata=
，则pnextdata=
。由此，单链表是非随机存取的存储结构，要取得第i个数据元素必须从头指针出发顺链进行寻找，也称为顺序存取的存取结构。因此，其基本操作的实现不同于顺序表。
2.5.2单链表基本操作的实现
1．初始化
单链表的初始化操作就是构造一个如图2.10（b）所示的空表。
算法2.6单链表的初始化
①生成新结点作为头结点，用头指针L指向头结点。
②头结点的指针域置空。
2．取值
和顺序表不同，链表中逻辑相邻的结点并没有存储在物理相邻的单元中，这样，根据给定的结点位置序号i，在链表中获取该结点的值不能像顺序表那样随机访问，而只能从链表的首元结点出发，顺着链域next逐个结点向下访问。
算法2.7单链表的取值
①用指针p指向首元结点，用j做计数器初值赋为1。
②从首元结点开始依次顺着链域next向下访问，只要指向当前结点的指针p不为空（NULL），并且没有到达序号为i的结点，则循环执行以下操作：
·p指向下一个结点；
·计数器j相应加1。
③退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法（i大于表长n或i小于等于0），取值失败返回ERROR；否则取值成功，此时j=i时，p所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域，返回OK。
该算法的基本操作是比较j和i并后移指针p，while循环体中的语句频度与位置i有关。若1≤i≤n，则频度为i1，一定能取值成功；若in，则频度为n，取值失败。因此算法2.7的最坏时间复杂度为O(n)。
假设每个位置上元素的取值概率相等，即
=1/n，即
由此可见，单链表取值算法的平均时间复杂度为O(n)。