319 views

2 Answers

Best answer
2 votes
2 votes

Here the keyword is "FIFO order" which means we are talking about queue data structure . And we know well that in queue :

Insertion is at one end and deletion at other end .  

Lets analyse each one of the given DS one by one : 

a) For double linked list with pointer to head node :

Say we insert from beginning and delete from end . Then as pointer to last node is not given we have to travserse and then delete the last node . Hence deletion  =  O(n)  , insertion  =  O(1)

b) Single linked list with pointer to head node and tail node : 

Here as pointer of last node is given as well , hence time taken to insert = time taken to delete = O(1)

c) Circular doubly linked list with pointer to head node :

Here no need of tail pointer to delete last node as it is circular doubly linked list . Hence both insertion and deletion can be done in O(1) in this case as well . 

There is no relevance is tree is here as we are not concerned with hierarchial data structure here.

Hence D) should be the correct option .

selected by
0 votes
0 votes

(D) II and III only

Now Let's take the constraints one by one: 

1) Items are retrieved and removed in FIFO order: Queue , so if first and last element locations are known, operations would take O(1).

2) There is no limit on number of elements: Array is not used.

3) Size of the item is relatively larger than the storage required for memory addressess: Tree data structure is not used.

Related questions

2 votes
2 votes
1 answer
1
papesh asked Aug 11, 2016
329 views
How can we implement doubly linked list using single next pointer??Explain in detail ...plus advantage of it..