The Gateway to Computer Science Excellence

0 votes

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)

A. O(1)

B. O(N)

+2

This will take O(1) time.

add node to next of head.

copy head data to new node

add new data to old head

add node to next of head.

copy head data to new node

add new data to old head

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)

+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

+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

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 votes

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

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..

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..

52,315 questions

60,433 answers

201,778 comments

95,257 users