2.5.3循环链表
图2.17单循环链表循环链表（CircularLinkedList）是另一种形式的链式存储结构。其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点，图2.17所示为单链的循环链表。类似地，还可以有多重链的循环链表。
循环单链表的操作和单链表基本一致，差别仅在于：当链表遍历时，判别当前指针p是否指向表尾结点的终止条件不同。在单链表中，判别条件为p!=NULL或p-next!=NULL，而循环单链表的判别条件为p!=L或p-next!=L。
在某些情况下，若在循环链表中设立尾指针而不设头指针（见图2.18（a）），可使一些操作简化。例如，将两个线性表合并成一个表时，仅需将第一个表的尾指针指向第二个表的第一个结点，第二个表的尾指针指向第一个表的头结点，然后释放第二个表的头结点。当线性表以图2.18（a）的循环链表作存储结构时，这个操作仅需改变两个指针值即可，主要语句段如下：
p=B-next-next;
B-next=A-next;
A-next=p;
上述操作的时间复杂度为O(1)，合并后的表如图2.18（b）所示。
图2.18仅设尾指针的循环链表2.5.4双向链表
以上讨论的链式存储结构的结点中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针向后寻查其他结点。若要寻查结点的直接前驱，则必须从表头指针出发。换句话说，在单链表中，查找直接后继结点的执行时间为O(1)，而查找直接前驱的执行时间为O(n)。为克服单链表这种单向性的缺点，可利用双向链表（DoubleLinkedList）。
顾名思义，在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱，结点结构如图2.19（a）所示，在C语言中可描述如下：
和单链的循环表类似，双向链表也可以有循环表，如图2.19（c）所示，链表中存有两个环，图2.19（b）所示为只有一个表头结点的空表。
图2.19双向链表示例在双向链表中，若d为指向表中某一结点的指针（即d为DuLinkList型变量），则显然有
d-next-prior=d-prior-next=d
这个表示方式恰当地反映了这种结构的特性。
在双向链表中，有些操作（如ListLength、GetElem和LocateElem等）仅需涉及一个方向的指针，则它们的算法描述和线性链表的操作相同，但在插入、删除时有很大的不同，在双向链表中需同时修改两个方向上的指针，图2.20和图2.21分别显示了插入和删除结点时指针修改的情况。在插入结点时需要修改四个指针，在删除结点时需要修改两个指针。它们的实现分别如算法2.13和算法2.14所示，两者的时间复杂度均为O(n)。
图2.20在双向链表中插入结点时指针的图2.21在双向链表中删除结点时指针的算法2.13双向链表的插入
算法2.14双向链表的删除