Question

1a) If I'm writing a program which involves many insertion and deletion operations, and memory is not a concern, which of the following should I choose to hold my data?

A: linked list

B: fixed-size array

C: dynamic array

D: any of the above

1b) What about if I'm writing a program and I want the program to be flexible on the data with various sizes, and the program also needs to provide fast access to the data? Which of those should I choose to hold my data?

Answer 1

1.)
a)
A - Linked List

- We will use linked list in this case where insertion and deletion are frequent as time complexity for inserion and deletion for a Linked List is O(1).
- Whereas, in case of array, both static and dynamic, in case of deletion and insertion, we need to copy elements from one array to other to perform either deletion or insertion. It will cost us time complexity of O(N) where N is number of elements already present in the array. (As we need to traverse all elements to perform copy)


1.)
b)
I will use Dynamic Array in such a case,

- It is so because, in case of dynamic array, I am being flexible on the data. I can add new data also if the size is more.
- As stated, we need a fast access to data. It means searching operation is the priority. As we know that array elements are accessed via known indexes, so element with in a array list can be searched / accssed in O(1) time complexity.
- So, we will prefer dynamic array for this use case


* Here O() means the Big O notation to find the running time of an algorithm.


Kindly upvote if this helped