0 votes 0 votes 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?? DS data-structures linked-list time-complexity queue + – sushmita asked Sep 20, 2018 sushmita 1.2k views answer comment Share Follow See all 12 Comments See all 12 12 Comments reply sushmita commented Sep 20, 2018 reply Follow Share 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 votes 0 votes Shaik Masthan commented Sep 20, 2018 reply Follow Share 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 votes 0 votes sushmita commented Sep 20, 2018 reply Follow Share 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 votes 0 votes srestha commented Sep 20, 2018 reply Follow Share is it circular queue or circular linked list? 0 votes 0 votes sushmita commented Sep 20, 2018 reply Follow Share Queue using circular linked list implementation 0 votes 0 votes srestha commented Sep 20, 2018 reply Follow Share ok and is it singly linked list? 0 votes 0 votes sushmita commented Sep 20, 2018 reply Follow Share Circular linked list 0 votes 0 votes srestha commented Sep 20, 2018 reply Follow Share 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 0 votes 0 votes Shaik Masthan commented Sep 21, 2018 reply Follow Share @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). 1 votes 1 votes MiNiPanda commented Oct 22, 2018 reply Follow Share 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 votes 0 votes Shaik Masthan commented Oct 22, 2018 reply Follow Share my view is the answer provided by rahul sharma 5 0 votes 0 votes MiNiPanda commented Oct 22, 2018 i edited by MiNiPanda Oct 22, 2018 reply Follow Share 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 votes 1 votes Please log in or register to add a comment.
0 votes 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). phaneendrababu answered Sep 20, 2018 phaneendrababu comment Share Follow See all 4 Comments See all 4 4 Comments reply sushmita commented Sep 20, 2018 reply Follow Share 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 votes 0 votes phaneendrababu commented Sep 20, 2018 reply Follow Share Yes,we can also do like that. 0 votes 0 votes Mayankprakash commented Sep 20, 2018 reply Follow Share @sushmita What is the final answer? 0 votes 0 votes sushmita commented Sep 21, 2018 reply Follow Share I DON'T KNOW. THAT'S WHY I HAVE POSTED HERE. 0 votes 0 votes Please log in or register to add a comment.