疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

循环链表——Java算法之线性表


 

 循环链表是一种首尾相接的链表。将单链表的尾节点next指针改为引用单链表header节点,这个单链表就成了循环链表。

循环链表具有一个显著特征:从链表的任一节点出发均可找到表中其他所有节点,因此循环链表可以被视为“无头无尾”,如图9.8所示。
                              
9.8 循环链表
循环链表中第一个节点之前就是最后一个节点,反之亦然。循环链表的无边界使得它实现许多方法时会更容易,在这样的链表上设计算法会比普通链表更加容易。
新加入的节点应该是在第一个节点之前(采用头插法插入),还是最后一个节点之后(采用尾插法插入),可以根据实际要求灵活处理,具体实现区别不大。
就程序实现来说,循环链表与普通单链表差别并不大,保证链表中tail.next = header即可,因此此处不再给出循环链表的代码。

除此之外,还有一种伪循环链表,就是在访问到最后一个节点之后的时候,手工地跳转到第一个节点,访问到第一个节点之前的时候也一样。这样也可以实现循环链表的功能,当直接用循环链表比较麻烦或者可能有问题时,可以考虑使用这种伪循环链表。