Question

循环单链表问题。数据结构学得好的解释一下

只有尾指针（rear）的循环链表插入。删除时的时间复杂度为O(1),O(1)
只有头指针(front）的循环链表插入。删除时的时间复杂度O(n),O（1）
谁给解释一下！！

Answer 1

对于只有尾指针的链表(第一类),要定位一个单元只能从之前的单元向下扫描.
对于只有头指针的链表(第二类),要定位一个单元只能从之后的单元向上扫描.

插入时,第一类链表首先根据要插入的位置n找到n+1,这里只需要常熟级的操作,然后把w的尾指针指向n+1,n的尾指针指向w,这两个指向操作也是常数级的,所以整个插入过程是O(1)的.
第二类链表则麻烦一点,因为知道n不能直接找出n+1,要从尾部往回扫描至n+1,这个过程是线性级的.然后把n+1的头指针指向w,w的头指针指向n.这个过程常数级.合起来就是线性级O(n)

删除时,一般是定位n删除n+1,这时候先找出n+2,然后将n的尾指针指向n+2即可.这样只用常数级操作O(1).
对于第二类我有疑问..如果是定位n删除n+1,那么应该也是O(n)的.可能你的意思是知道n+2,删除n+1,那么原理和第一类一样,只是反过来而已.