873 views
0 votes
0 votes
anybody remembered than linked list question...if it is implemented using queue?

3 Answers

4 votes
4 votes
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 ..
2 votes
2 votes
I think 1 for both
0 votes
0 votes
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

Related questions

2 votes
2 votes
1 answer
1
rahul sharma 5 asked Sep 28, 2017
7,761 views
if we implement queue using singly linked list then how juch time enqueue enqueue and dequeue will take ?