Given the unordered linked list as a queue, what operations would take O(1) time?

Question

My doubt is that the single list queue is the form : 1->2->3->4->5->6->7->8->9->NULL with 1 as the rear node and 9 as the front node. Also, in a queue, addition takes from the rear and the deletion from the front, so a structure like above should be there. Then deletion of front item should take O(n) time and rear item O(1) time, right? I just want to confirm whether my answer was right or the answer given.

Source : testbook.com live test on 3rd January, 2016

Answer 1

delete rear item from list takes O(n)

suppose list is 1-2-3-4

u delete 4

sow now u need to make pointer of node 3 null

so u will have to traverse list from starting to reach 3 and make pointer null

Comments

you have taken the list as : NULL<-1<-2<-3<-4 with front at node 1 and rear at node 4?

Also, insertion in queue will take place at node 4 and removal from the queue at node 1?

---

Item can be inserted at front as well as rear using the given front and rear pointers ,only deletion from rear end requires traversal of O(n) time

---

if front will point to first and rear will point to last pointers of the node

then

insertion at rear is insert at the end which can be done in O(1) as last pointer is given

insertion at the front is insert at the start which can also be done in O(1) with first pointer

deletion : we know that for deletion of any node in linked list we need its previous node

delete at end: (delete at rear) for this we have to traverse the last to get previous node of the victim node which will take O(n) time.

delete at front: it is like deletion of first node so no need of traversal we can simply delete it using first pointer and make the head to point to 2nd node so O(1)