The Gateway to Computer Science Excellence
0 votes
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)
in Programming by Active (1.1k points)
edited by | 422 views
0
An efficient implementation will take O(1) time.
+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
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.

2 Answers

+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

@Nitesh Choudhary

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)?
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

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

Related questions

+1 vote
0 answers
2
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,429 answers
195,208 comments
99,922 users