首页 > 试题广场 >

用单循环链表表示长度为n的链表队列,如只存在尾指针,则完成入

[单选题]
用单循环链表表示长度为n的链表队列,如只存在尾指针,则完成入队和出队的时间复杂度是()
  • O(n-1), O(n-1)
  • O(n), O (1)
  • O(n2-1), O(n)
  • O(1), O(1)
1楼能说人话吗?单循环链表就是一个【单向环】而已,入队表示从头进,出队表示从尾出。。。。
若只有头指针,瞬间入队,入队复杂度就是O(1),但是出队的话要从头走到尾走n个结点,指针才能到尾部,出队复杂度就是O(n)!
若只有尾指针,瞬间出队,出队复杂度就是O(1),由于单向环首位相连,从尾指针下一位就是头指针 了!故而入队复杂度也是O(1)
发表于 2021-11-09 13:32:29 回复(1)
用单循环链表表示长度为n的链表队列,若只设置头指针,则出队和入队的时间复杂度分别是O(1)、O(n);若只设置头指针,则出队和入队的时间复杂度分别是O(1)、O(1);
发表于 2020-08-10 16:08:09 回复(1)