线性表（三）

3.13 循环链表

对于单链表，由于每个节点只存储了向后的指针，到了尾标志就停止了向后链的操作，这样，当中某一节点就无法找到它的前驱结点了。

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

为了使空链表与非空链表处理一致，我们通常设一个头结点。

循环链表带有头结点的空链表如图：

其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否为空，现在则是p->next不等于头结点，则循环为结束。

3.14 双向链表

我们在单链表中，有了next指针，这就使得我们要查找下一结点的时间复杂度为O(1),可是如果我们要查找的是上一结点的话，那最坏的时间复杂度就是O(n)了，因为我们每次都要从头开始遍历查找。

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。


简单总结一下，双向链表相对于单链表来说，要更复杂一些，毕竟他多了prior指针，对于插入和删除时，需要格外小心。

另外它由于每个节点都需要记录两份指针，所以在空间上是要占用略多一点，不过，由于它良好的对称性，使得对某个节点的前后节点的下操作，带来了方便，可以有效地提高算法的时间性能。说白了，就是用空间来换时间。