2.3.2　单链表

每个结点只含有一个指针的链表称为单链表（simple linked list）。为叙述方便，下面所说的链表均指普通单链表。单链表是最简单的一种链表。

例如，设有一个包含5个元素（A，B，C，D，E）的线性表，其顺序结构和链式结构的存储状态如图2－10所示。

图2－10 线性表的两种存储状态比较

图2－10（a）中b为顺序表中第一个元素的首地址，图2－10（b）中head为链表的头指针，头指针指示着线性表中第一个元素A的存储首址。假设这5个结点的存储首址分别为2000、2020、2004、2024和2012。由图可见，在顺序表中元素的物理顺序与线性表中的逻辑顺序是一致的，而在链表中，这两种顺序一般是不一致的。在链表中，结点在内存中的存储位置可以随意设置，但结点间由指针所体现的逻辑顺序必须和线性表完全一致。换句话说，指针指出了线性表中“下一个元素”即后继元素的存储首地址。图中的符号“∧”（NULL）为空指针，表示该结点代表的元素是线性表中的最后一个元素。

通常把链表画成用箭头相连接的结点序列，结点之间的箭头表示指针域中的指针。例如图2－10（b）所示的链表可画成如图2－11所示的形式。图中没有标出指针的具体值，只是用箭头表示它的存在，这是因为进行程序设计时，我们所关心的只是结点间的逻辑顺序，而结点的实际存储地址是无关紧要的。

图2－11 链表的逻辑状态

根据问题的需要，有时在单链表的第1个结点之前，还可附设一个称为“表头结点”的结点HEADER。表头结点的信息域可以不存储任何信息，也可以存储标题、建表日期、建表人、表长等信息。表头结点的结构和链表中结点的结构通常是一致的，其指针域存储第一个结点的首地址。若线性表为空表，则该域的值也为空“∧”，图2－12所示为带表头结点的单链表。注意，此时单链表的头指针head指向表头结点HEADER。

图2－12 带头结点的单链表

下面介绍单链表的初始化、读取元素、插入、删除和生成有n个结点的运算。

1.读取元素

取单链表中任意元素，若该元素存在，则查找成功，返回其值及成功标志；否则，或者为空表，或者表中没有该结点。与顺序表不同的是，链表中结点的地址不能通过公式直接计算，必须从表头开始顺着链逐个结点查找。

算法2.4 读取元素

从单链表中删除一个结点或往单链表中插入一个新结点都非常容易，因为此时只要修改结点的指针，而无须移动其他任何结点。

在下面给出的算法中，引用了C语句中的两个标准函数malloc（sizeof（nodetype））和free（q）。执行malloc（sizeof（nodetype））的作用是使系统生成一个nodetype型的结点，同时将该结点的起始位置（内存中的首址）赋给一个指向nodetype类型结点的指针类型变量；执行free（q）；的作用是使系统回收一个由指针变量q所指的nodetype型的结点，回收后的空间备作再次生成结点时使用。

2.插入元素

在已知结点后面插入新的结点的操作如图2－13所示，设指针p指向结点A，指针f指向将要插入的新结点x，x插在线性表两个数据元素A和B之间，这时只要修改两个指针即可。上述指针的修改用语句描述为：

图2－13 插入一个结点到链表中

根据图示可以总结出插入算法实现思想：

①寻找第i个结点，找到用p指向；

②生成新结点s；

③将数据写入新结点s－data；

④修改指针s－next＝p－next；p－next＝s；。

算法2.5 结点i后插入算法

思考：若在已知结点的前面插入元素，算法如何写？时间复杂度又是多少？

3.删除操作

删除已知结点后面的数据元素操作如图2－14所示，若要删除线性表中元素y，则仅修改一个指针。图中p为指向结点x的指针，此时指针的修改用语句描述为：

图2－14 从链表中删除一个结点

根据图示可以总结出插入算法实现思想：

①寻找第i个结点，找到后用p指针指向；

②判断链表是否空，若空则不能作删除操作；

③将要删除结点q指针指向，p－next＝q；；

④修改指针p－next＝q－next；；

⑤释放内存空间free（q）。

算法2.6 结点的删除算法

思考：若删除i结点本身，算法如何实现？

4.创建单链表

设单链表的初始状态为空，利用标准函数malloc（sizeof（elementype））依次建立线性表中各元素结点，并将它们逐个插入到链表中，插入方法有两种，一种是头插法，即依次将新结点都插到表头结点之前；另一种是尾插法，即每次都将新元素插到表尾。

头插法算法思想（如图2－15所示）：

①建立一个带头结点的单链表，即申请新结点用L指向，指针域为空；

②申请新结点s，给s数据域赋值；

③实现插入操作s－next＝L－next；L－next＝s；；

④循环②、③直到所有结点插入完成。

图2－15 单链表头插法过程

算法2.7 建立带头结点的单链表（头插法）

由头插法产生的单链表是逆序的，每次都让新来的结点在第一的位置上。下面介绍另一种建立方法尾插法，就是新来的结点都插在终端结点的后面，该方法是将新结点插到当前链表的表尾上。为此需增加一个尾指针r，使之始终指向当前链表的表尾，如图2－16所示。

图2－16 单链表尾插法过程

算法2.8 建立带头结点的单链表（尾插法）

以上算法的时间复杂度都是O（n），因为在插入删除时都需要查找，找到被删除或插入的位置。如果只针对插入和删除的这部分算法来看，其时间复杂度都是O（1）。