conceptual doubt

Question

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

Comments

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 ?

---

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.

---

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?

---

is it circular queue or circular linked list?

---

Queue using circular linked list implementation

---

ok

and is it singly linked list?

---

Circular linked list

---

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

---

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

---

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?

---

my view is the answer provided by rahul sharma 5

---

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

Answer 1

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

Comments

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

---

Yes,we can also do like that.

---

@sushmita

What is the final answer?

---

I DON'T KNOW. THAT'S WHY I HAVE POSTED HERE.