线性表（三）
3.13 循环链表
对于单链表，由于每个节点只存储了向后的指针，到了尾标志就停止了向后链的操作，这样，当中某一节点就无法找到它的前驱结点了。
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。
为了使空链表与非空链表处理一致，我们通常设一个头结点。
循环链表带有头结点的空链表如图：
其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否为空，现在则是p->next不等于头结点，则循环为结束。
3.14 双向链表
我们在单链表中，有了next指针，这就使得我们要查找下一结点的时间复杂度为O(1),可是如果我们要查找的是上一结点的话，那最坏的时间复杂度就是O(n)了，因为我们每次都要从头开始遍历查找。
双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。
简单总结一下，双向链表相对于单链表来说，要更复杂一些，毕竟他多了prior指针，对于插入和删除时，需要格外小心。
另外它由于每个节点都需要记录两份指针，所以在空间上是要占用略多一点，不过，由于它良好的对称性，使得对某个节点的前后节点的下操作，带来了方便，可以有效地提高算法的时间性能。说白了，就是用空间来换时间。
