The Gateway to Computer Science Excellence
0 votes
184 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 by Boss (17.3k points) | 184 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.

our linked list will become-

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
Circular linked list
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.

@sushmita

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

1 Answer

0 votes
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).
by (151 points)
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.

our linked list will become-

A->B->C->D->E->F->A
0
Yes,we can also do like that.
0
@sushmita

What is the final answer?
0
I DON'T KNOW. THAT'S WHY I HAVE POSTED HERE.

Related questions

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,647 questions
56,492 answers
195,439 comments
100,708 users