422 views
What is the time complexity to insert a new Node in a singly circular linked list at Starting ? (Number of nodes in list = N)

A. O(1)

B. O(N)

edited | 422 views
0
An efficient implementation will take O(1) time.
+2
This will take O(1) time.

copy head data to new node

0
Yes, I have also selected O(1) but ACE test says ans is O(N).
+1
Nop they have given it wrong. you are correct.
+1

O(1) is correct...bcoz pointer for initial node is already known ....no need to traverse.....

0

Answer-O(n)  bcz in question only say about insert at starting of list (http://vle.du.ac.in/mod/book/view.php?id=5704&chapterid=2629)

0
if the head pointer is known we can add a node after that head pointer but not before it.So we need to traverse it till the tail...keep a pointer to it and and it after tail and make the new node as head :)

Hope this helps.

+1 vote
O(N) is the answer because it is single circular linked list so adding a node at star will take constant time but last node point to new node which is inserted so for this linked we should go to last node which take N time
by Active (2.4k points)
+1
No, we will insert the node at 2nd position and then swap data with the first node, so no need of updating value of the last node.
0
in question we want to insert a specific node
0

Mr_22B  If the node we want to insert contains the array of n elements then?

0

as last node will hold the address of first node means point to the head pointer....

now during the insertion of new node we will change head pointer to the new one ...as a result head will point to the new node as well as last node will also point to head node.......

i think her no need to...traverse cahnge the last node->next address.....?????

0
@saxena what if it contains $2^{N}$ elements.
0
@Nitesh Chaudhary

Is the answer is 0(n) or thetha(n)? because i had marked ans as 0(n) but in the key its wrong and the actual answer is thetha(n).

if the anwer is thetha(n) then how we will come to know this we have to mark thetha(n) not the 0(n)?

If you have pointer to the first node

Insertion at beginning: O(n)

Insertion at the end: O(n) // As you have to traverse till the end.

If you have pointer to the last node

Insertion at beginning: O(1)

Insertion at end: O(1)

Check this: https://gateoverflow.in/1033/gate2004-36

by Loyal (9.6k points)
edited by
0
I think complexity depends on the position of pointers given. But here no specification about any front or rear pointer so we will consider the worst case i.e pointer is pointing to first node.Then T.C -

1) For insertion at beginning O(n)

2) insertion at the end O(n).

And if you will consider the pointer which is pointing to last node .Then T.C -

1) For insertion at beginning O(1)

2) insertion at the end O(1).

I Hope you got my point..