244 views
WHAT IS THE TIME COMPLEXITY TO ENQUEUE AN ELEMENT IF THE QUEUE IS IMPLEMENTED AS A CIRCULAR QUEUE AND WE HAVE GOT ONLY ONE POINTER TO FRONT ELEMENT??
in DS | 244 views
0
A->B->C->D->E->A is our circular linked list and front points to A.

Now if we want to add F, copy F to A and now insert A between F and B.

A->B->C->D->E->F->A

THIS METHOD IS CORRECT BUT INVOLVES ONE COPY OPERATION. CAN WE ANSWER O(1) IN GATE ?
0
appearance is looking same, But it is very dangerous to change like that,

As a good programmer, we can't use this tricks.

Why? what is the problem with it?

let assume you have the linked list (let linked list starting address =1165), but somewhere else you use this via pointers ( you hold the value of head of the pointer ==> you have 1165 in your hand ), By this trick your starting address is changed ( value of it ="A" only, but the address now present the value "A" is different. )

As per my knowledge, we can't answer O(1), ( Don't say, in the question it is not mention that , we use the values of this list is somewhere else. )

if still you are thinking it is O(1), it's upto you.
0
I KNOW THIS METHOD IS RISKY N CAN CAUSE DANGLING POINTERS BUT IF ITS NOT REFERRED ANYWHERE AND THEY ASKED WHETHER ITS POSSIBLE OR NOT IN O(1)THEN?
0
is it circular queue or circular linked list?
0
Queue using circular linked list implementation
0
ok

and is it singly linked list?
0
0
then it will be O(1) time

newnode->next=front->next;

front->next=newnode->data;

As pointer is at last node of circular linked list, so, O(1) time will be enough. Just front pointer will be updated
+1

@srestha

check the question clearly, questioner requires insertion at front position.

I KNOW THIS METHOD IS RISKY N CAN CAUSE DANGLING POINTERS BUT IF ITS NOT REFERRED ANYWHERE AND THEY ASKED WHETHER ITS POSSIBLE OR NOT IN O(1)THEN?

then it is O(1).

0

As per my knowledge, we can't answer O(1)

@Shaik then what is your view on this https://gateoverflow.in/3654/gate2004-it-13?

0

my view is the answer provided by rahul sharma 5

+1
Okay.. O(n) is when we are taking care of all practical issues. Here nothing of that sort is mentioned so I think theoritically O(1) should be considered otherwise O(n) would be very trivial. But then I respect your opinion :)

As we have only one pointer which points to FRONT the time complexity is O(n). If we have a REAR pointer the time complexity is O(1).
0
no we can also do with front with O(1).

A->B->C->D->E->A is our circular linked list and front points to A.

Now if we want to add F, copy F to A and now insert A between F and B.