循环链表（循环单链表和循环双链表）和静态链表

循环单链表

循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环，如图2-11所示。 

图2-11  循环单链表

在循环单链表中，表尾结点的next域指向L，故表中没有指针域为NULL的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。

循环单链表的插入、删除算法与单链表的几乎一样，所不同的是如果操作是在表尾进行，则执行的操作不相同，以让单链表继续保持循环的性质。当然，正是因为循环单链表是一个 “环”，因此，在任何一个位置上的插入和删除操作都是等价的，无须判断是否是表尾。

在单链表中只能从表头结点开始往后顺序遍历整个链表，而循环单链表可以从表中的任一结点开始遍历整个链表。有时对单链表常做的操作是在表头和表尾进行的，此时可对循环单链表不设头指针而仅设尾指针，从而使得操作效率更高。

循环双链表

由循环单链表的定义不难推出循环双链表，不同的是在循环双链表中，头结点的prior 指针还要指向表尾结点，如图2-12所示。 

图2-12  循环双链表

在循环双链表L中，某结点*p为尾结点时，p->next=L;当循环双链表为空表时，其头结点的prior域和next域都等于L。

静态链表

静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域 next，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称为游标。和顺序表一样，静态链表也要预先分配一块连续的内存空间。

静态链表和单链表的对应关系如图2-13所示。 

图2-13  静态链表存储示意图

静态链表结构类型的描述如下：

#define MaxSize 50  //静态链表的最大长度
typedef struct{  //静态链表结构类型的定义
    ElemType data;  //存储数据元素
    int next;  //下一个元素的数组下标
}SLinkList[MaxSize];

静态链表以next==-1作为其结束的标志。静态链表的插入、删除操作与动态链表相同，只需要修改指针，而不需要移动元素。总体来说，静态链表没有单链表使用起来方便，但是在一些不支持指针的高级语言（如Basic）中，这又是一种非常巧妙的设计方法。