Question

You are working on a program where you are going to be storing data in a sorted list, and every time you added a piece of data, you would need to put it into the correct location in the sorted list. Which of the two data structures is best for this and why?

Answer 1

First,
We can use Linked Lists because it allows to insert without reallocation of the entire structure.
The data items are need not to store on memory or disk contiguously and linked list are good for large data but it does not provide random access to its nodes.
Since we insert a data to sorted linked list, therefore, its time complexity will be O(n) where n is number of data pieces.
{ For searching its right place = O(n) + For inserting new node = O(1) }

Second,
We can use Array with Insertion Sort as it also works in linear time i.e. O(n).

I don't suggest Heap Data Structure although it works in O(log n) beacause it is patially ordered not completely sorted.