数据结构之单链表基本运算的实现[10]

循环链表

对于单链表而言最后一个结点的指针域是空指针如果将该链表头指针置入该指针域则使得链表头尾结点相连就构成了循环单链表(也称单循环链表)如图所示

图带头结点的单循环链表

对循环单链表的操作与单链表基本相同只是将原来判断指针是否为NULL变为是否是头指针而已其它没有较大的变化

对于单链表只能从头结点开始遍历整个链表而对于循环单链表则可以从表中任意结点开始遍历整个链表不仅如此对链表的操作可以在表尾表头进行此时可以改变一下链表的标识方法不用头指针而用一个指向尾结点的指针R来标识既可以找到尾结点又可以找到头结点(R>next)可以使得操作效率得以提高

例如对两个循环单链表H H的连接操作是将H的第一个元素结点接到H的尾结点如用头指针标识则需要找到第一个链表的尾结点其时间复杂性为O(n)而链表若用尾指针R R来标识则时间性能为O()操作如下

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []