Which algorithm is used in List<T> to dynamically allocate memory?

Question

Now I have an algorithm for dynamically allocating memory on an array:

• If array is full I create a new array of twice the size, and copy items.
• If array is one-quarter full I create a new array of half the size, and copy items.

This is fairly fast algorithm for dynamic memory allocation despite the extra over-head of copying the elements to the newly allocated array.

1. What is the faster, List<T> or such an algorithm based on an array? What would you recommend to use?

2. does List<T> use simple array as internal data structure?

Answer 1

TO answer your question:

It is true, C#'s List<T> implementation uses an internal array that is

1. Serializable
2. Thread-safe
3. Implements IEnumerable<T> (which means it can be LINQ Queried, foreached etc)
4. Binary Searched

and so on

Hence, I would ask you to use List<T> instead of your own List.

Oh and btw, if you want the source code of List<T> from Microsoft, then here it is

List.cs

EDIT

The source code of EnsureCapacity in List<T> is:

    // Ensures that the capacity of this list is at least the given minimum
    // value. If the currect capacity of the list is less than min, the
    // capacity is increased to twice the current capacity or to min,
    // whichever is larger.
    private void EnsureCapacity(int min) {
        if (_items.Length < min) {
            int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
            if (newCapacity < min) newCapacity = min;
            Capacity = newCapacity;
        }
    }

Answer 2

Unless you have a specific reason to believe otherwise, it's almost universally a good idea to use the provided libraries that come with C#. Those implementations are well-implemented, well-debugged, and well-tested.

The data structure you're describing is a standard implementation of a dynamic array data structure, and most languages use this as their default list implementation. Looking over the documentation for List<T>, it seems like List<T> uses this implementation, since its documentation has references to an internal capacity and guarantees O(1) append as long as the size is less than the capacity.

In short, avoid reinventing the wheel unless you have to.

Hope this helps!