How is List internally mapped?

问题:

Does it internally get treated as an Array or does it get treated as a totally different type by the CLR?

I am trying to implement integer values to the list.

List<int> lst = new List<int>();
lst.Add(3);
lst.Add(4);

vs.

I create an Array of integers

int[] arr = new int[2];
arr[0] = 3;
arr[1] = 4;

Array returns better time span results. So why do people prefer List<>.

回答1:

List<> is an implementation of a data structure, which takes care of allocating memory on a on-demand basis; it allows for insertion and deletion at any index etc. Therefore it is much more convenient than a simple array.

Under the hood, the current List<> implementation uses an array for storage, and the overhead when doing array-like operations is minimal. The added convenience is usually worth the little (if at all relevant) performance difference. Adding items is typically faster because the list allocates chunks of memory and doesn't require a new allocation and copy on every add (compared to the pure array, where the Length is always bound to the size in memory).

回答2:

A normal random access list typically has an internal array. The .NET List<T> implementation does this. Other implementations such as LinkedList<T> uses chains of elements with references instead of arrays. More exotic lists may use trees internally for ordering.

The internal array in List<T> is initialised with a short length (4 I believe), and if you try to add outside the max bounds of the array, it is expanded. Since this can be time consuming (the array needs to be copied), the array is doubled in size, i.e. when you add the 5th element the internal array is resized to length 8 and so on.