Data Structure

Question

Which data structure can be used to implement a collection of elements with following constraints in most efficient manner?

Constraints:

Items are retrieved and removed in FIFO order.

There is no limits in number of elements

Size of an item is relatively larger than storage required for memory address

I) Doubly linked list with pointer to 1st node

II) Singly linked list with pointer to head and tail

III) Circular doubly linked list with pointer to 1st node

IV) Binary tree

a) I and II

b) IV and III

c)II and IV

d) II and III

Comments

" Size of an item is relatively larger than storage required for memory address"

what i think from it is that, there is no problem in taking two or more pointers in one node..

not sure. 

---

what i think from it is that, there is no problem in taking two or more pointers in one node..

yes this is correct ! given that "Size of an item is relatively larger than storage required for memory address" we can say storage required for memory addresses is less as compared to data elements which gives us the liberty to use two or more pointers without considering any memory overhead

---

Can somebody explain why circular doubly linked list? It's mentioned "There is no limits in number of elements".

I know the elements can be entered indefinitely given the element in the first position clears away. But what if it doesn't suppose we have 10 elements to put but our max size is only 7, say. Of course we can clear off the first three elements but won't it have to wait? (Not trying to get OS concepts here...just curious)

Answer 1

Circular Double Linked list It can be done as follows while inserting always insert at first

x= create new node

x->next=1st;

x->prev=1st->prev;

1st->prev->next=x;

1st->prev=x;

for deletion it will be

1st>prev->prev->next=1st;

1st->prev=1st->prev->prev

With single linked list we can do insertion at rear and deletion at front

Managing Fifo order in Binary tree is near impossible

And Double Linked list with single pointer is also impossible

option D

Comments

" Size of an item is relatively larger than storage required for memory address"

means?