1.2 性表的实现

　　带头结点的线性链表的插入算法如下：

　　对比带头结点的线性链表插入首元素的代码和插入非首元素的代码，可以发现：两者的代码第III行和第IV行在形式上略有不同，前者使用了变量L，后者使用了变量p，事实上，当p取值等于L时，后者完全可以实现插入前者的功能。
　　4）不带头结点的线性链表插入算法。
　　在不带头结点的线性链表中，插入首元素和插入非首元素的代码不能完全整合，因此，必须区别对待，分别编码，其插入算法代码如下：

　　（6）删除元素算法
　　删除元素是插入元素的逆过程，可分为三个步骤，分别是查找线性链表第i-1个元素的地址或者头指针、修改指针和释放存储空间。在算法中也必须区分删除首元素和删除非首元素两种情况。
　　1）带头结点的线性链表删除算法。
　　由于头结点的存在，线性链表的任意元素都存在直接前驱结点（线性表首元素的前驱结点就是头结点）。因此，在带头结点的线性链表中删除元素时，无须考虑删除位置。
　　带头结点的线性链表的删除算法代码如下：

　　函数参数i取值的合法范围在1≤i≤n之间，其中n是线性表的长度，否则将返回错误。代码行I的功能是确保i值不小于1，代码行II的功能则是确保i值不大于n。
　　当i大于n+1时，p将遍历到最后一个结点的指针域，此时取值为空。当i等于n+1时，p将遍历到最后一个结点，此时表达式“p->next”代表最后一个结点的指针域，取值也为空。故代码行II可确保i值不大于n。
　　2）不带头结点的线性链表删除算法。
　　删除无头结点的线性表中的元素时，必须区分删除表头元素和非表头元素，并分别编码，代码如下：


　　（7）置空、销毁线性链表算法
　　置空不带头结点的线性链表的算法代码如下：
　　
　　如果是带头结点的线性表，则将上述代码中的Ⅰ、Ⅱ行更换为：
　　
　　置空算法需要遍历线性表的全部元素，因此，时间复杂度为O(n)，其中，n为线性表的长度。
　　3．线性表链式存储结构的特点
　　① 链式存储结构的线性表的最大优点是：只需更改指针就可以完成插入、删除，不再需要移动数据；其最大的缺点是：不支持随机查找，只能从链表头逐个遍历以获取元素的存储地址。
　　② 链式存储结构的线性表不需要一次性分配所需的存储空间，而是在插入时以结点为单位逐个申请，这样只要操作系统存储空间足够，就没有最大元素数量的限制。但是所有动态分配的空间，在删除时必须以结点为单位逐个释放，如果忘记释放，这部分空间将不能再使用，从而造成存储空间“丢失”的假象。而且不断申请和释放空间，势必多占用系统资源，降低运行效率。
　　③ 链式存储结构的线性表引入了指针的概念，程序员必须自行分配和释放空间，必须采用指针来引用和查询空间，避免引用空指针指示地址等。否则，即使是一个不起眼的小指针错误，也可能导致系统崩溃。
　　④ 链式存储结构的线性表引入了指针和动态内存，其功能性和灵活性都比顺序表好，但程序员必须设计更多的代码来实现，这样就提高了程序的复杂度，相比之下，设计顺序表就要容易得多。
　　⑤ 链式存储结构的线性表中每一个已分配空间的结点都对应了一个元素，无论线性表长如何，都没有以元素结点为单位浪费存储空间。但是，它在每个结点中增加了与元素数据无关的指针域，从而降低了存储密度。
　　⑥ 链式存储结构的线性表适用于数据元素总数不固定，插入、删除操作频繁的应用。
　　4．双向链表的定义
　　下面是一个定义数据元素类型为Elemtype的双向链表的例子：
　　
　　与单链表一样，双向链表也可以分为带头结点的双向链表和不带头结点的双向链表两种，如图1-9所示。
　　双向链表对前驱的访问相当灵活，如图1-9（b）中，假设p指向结点A1，q指向结点A2，则关于结点A2地址的表达至少有：
　　

　　同理，关于结点A1地址的表达至少有：
　　
　　5．双向链表的插入算法
　　与线性链表相似，双向链表的插入算法也要区分插入位置，其过程也分为三个步骤，分别是查找第i-1个元素的地址、分配存储空间并赋值、修改指针。
　　【例1-5】请写出在不带头结点的双向链表中插入表头元素A1的算法，并考虑本算法在双向链表为空时是否可行。
　　【解析】在双向链表的表头插入元素的步骤如下：
　　① 申请一个结点的存储空间，设地址为s，并赋值结点数据域为A1，赋值指针域值为空，如图1-10（a）所示。
　　② 将结点s的next指针赋值为头指针的取值，即设置原线性表第一个元素为s的直接后继，即s->next = L，如图1-10（b）所示。
　　③ 将原线性表第一个元素的prev指针赋值为s，即L->prev = s，如图1-10（c）所示。
　　④ 将头指针L指向新插入的结点地址，即L = s，如图1-10（d）所示。
　　（1）带头结点的双向链表插入算法
　　由于头结点的存在，双向链表的任意元素都存在直接前驱结点（首元素的前驱结点是头结点），因此，插入元素时不必区分元素位置。带头结点的双向链表插入算法如下：