1.2 性表的实现

　　（2）不带头结点的双向链表插入算法
　　在不带头结点的双向链表中，插入首元素和插入非首元素的代码不能完全整合，因此，必须区分对待，分别编码，其插入算法如下：

　　6．双向链表的删除
　　双向链表的元素删除操作需要区分删除头元素和其他元素两种情况，其步骤也可分为三步，分别为：查找链表中第i-1个元素的地址或者头指针、修改指针、释放存储空间等操作。
　　（1）带头结点的双向链表删除算法
　　带头结点的双向链表删除算法如下：

　　（2）无头结点的双向链表删除算法
　　删除算法中必须为删除首元素和其他位置元素分别编码，代码如下：

　　7．双向链表的特点
　　与单链表相比，双向链表的最大优点是可以在两个方向上遍历链表，其访问直接前驱和直接后继的时间复杂度都是O(1)。但是，由于双向链表结点的指针域中具有两个指针，故必须设计更多的代码来实现，从而提高了程序的复杂度。同时，双向链表中每个结点都增加了一个指针的存储空间，降低了数据的存储密度。
　　8．循环链表
　　在单链表中，最后一个结点的指针域取值为空，如果将这个域赋值为指向头结点或第一个结点的指针，那么该单链表就成了循环单链表，如图1-11所示。
　　循环链表的操作和单链表基本一致，差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。循环链表是另一种形式的线性表链式存储表示，它的特点如下：

　　① 最后一个结点的指针域指向头结点，整个链表成为一个由指针相链接的环。
　　② 一般使用指向链表最后一个结点的指针来描述循环链表。
　　③ 判断链表结束的条件不再是有没有后继结点，而是后继结点是否为头结点。
　　9．静态链表存储结构
　　在某些高级语言中，没有指针的概念，因此，只能借用一维数组来描述链表，它使用数组元素来描述链表的结点，使用数组的下标来描述结点的地址。它的每个结点由数据域和指针域两部分组成，前者存储了线性表的元素取值，后者存储了一个整型，代表直接后继的下标。如下是一个定义数据元素类型为Elemtype的静态链表的例子：
　　
　　带头结点的静态链表使用SLinkList[0]为头结点，使用SLinkList[0].nCur记载线性表中首元素的下标；不带头结点的静态链表一般则需要增加一个变量存储线性表首元素的下标。当结点的nCur取值为0时，表示链表已经结束；当nCur取值为-1时，表示该结点未使用。图1-12描述了线性表（2004，2005，2006，2007，2009），其中：
　　① 元素地址为SLinkList[0].nCur的值，即2。
　　② 首元素为SLinkList[2].data(2004)，其直接后继为SLinkList[2].nCur，即3。
　　③ 第2个元素为SLinkList[3].data(2005)，直接后继为SLinkList[3].nCur，即4。
　　……（省略④、⑤）
　　⑥ 第5个元素为SLinkList[7].data(2009)，直接后继为SLinkList[7].nCur，等于0，即线性表结束。
　　静态链表使用数组来存储元素，使用数组下标来描述指针的链式链表，它的特点如下：
　　① 所有的数据元素均存储在一个连续的空间段，但是相邻两个元素不一定处于相邻的空间。
　　② 修改指针域即可完成插入和删除操作，不需要移动数据元素，但是也不能随机访问静态链表中的元素。
　　③ 一次性分配所有的存储空间，插入、删除时无须再向操作系统申请或释放空间，但也限制了最大表长。