anybody remembered than linked list question...if it is implemented using queue? GATE 18

Question

anybody remembered than linked list question...if it is implemented using queue?

Comments

I only know ans theta 1 and n

---

It's about insertion at beginning and deletion at end if both pointer given

Answer 1

As i remember in question its given that it is NOT circular singly linked list..and two pointer head and tail are provided... and we can insert node at head...and delete node from tail ..and it works as queue ..

1) Insertion : O(1)

New_node->Link = Head;  // store the address of head in the link part of New node

Head= New_Node; //Save new node as head

2) Deletion : O(n)

As tail is given so we can delete it in constant time..but we have to find new tail pointer and it require link list traversal as it is singly linked list ...so its O(n)

Correct me, if i am wrong ..

Comments

I applied the same logic but still in doubt as others saying its O1 for both

---

see... as we know that deletion can be performed in O(1) time..but we using this singly linked list as Queue so we have to maintain the tail...so for updating the value of tail we need O(n) time...

Answer 2

I think 1 for both

Comments

Ya i Marked the same as head and tail pointer were given

---

how it can be 1 for dequeue....we have to traverse all the nodes and then we have to delete last node so it will be o(n)

---

Pointer to the last node was given, that's why

Answer 3

It is O(1) for insertion and O(n) for delete as we do not have last but one node to make it's next null. We need to traverse to get the last but one node. Make it's next null and make it as tail