Ace Test Series Data Structure Q9

Question

Which data structure would be most appropriate to implement a collection of values with the following 3 characteristics

1. Singly link list with head and tail pointer
2. Doubly link list with only head pointer
3. Binary tree
4. Array

- Items are retrieved and removed from the collection in FIFO order.
- There is no a priori limit on the number of items in the collection.
- The size of an item is large relative to the storage required for a memory address.

Comments

you know about the head pointer and tail pointer ?

explain?

we can not delete and  insert an element   in link list without  additional  pointer(left head pointer)  named as tail pointer

Answer 1

 

Ans – (A) {Given in Key} but (B) is more accurate

• The third point indicates a spill of data in memory
• So if there is a spill in last data element, we will have our data in last two memory bytes
• But we have a tail that points to the last byte only
• So, in singly link list, to access the last data we would need an extra linear traversal to second last byte ie O(n)
• Which we could overcome by using a doubly link list

So I think Doubly should be the answer

But provided key says Singly Linked list is better, without any explanation

Comments

Singly with head and tail is better as everytime you can insert at last using tail and you can delete from head.

In doubly since tail pointer is not there so for insertion everytime whole LL should be accessed

---

I somehow mistakenly assumed DLL as a circulat linked  list and tried to solve 🤦🥲

Since it's a DLL, obvioudly SLL would be better here!

Thanks!