The inside of List is implemented by array instead of linked List, and when the specified capacity is not given, the initial capacity is 0

Add

// Adds the given object to the end of this list. The size of the list is
// increased by one. If required, the capacity of the list is doubled
// before adding the new element.
//
public void Add(T item) {
    if (_size == _items.Length) EnsureCapacity(_size + 1);
    _items[_size++] = item;
    _version++;
}

// 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;
        // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
        // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
        if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
        if (newCapacity < min) newCapacity = min;
        Capacity = newCapacity;
    }
}

Every time the capacity is insufficient, the capacity of the whole array will be doubled_ defaultCapacity is the capacity. The default value is 4. Therefore, the whole expanded route is 4, 8, 16, 32, 641282565121024... And so on. Therefore, when creating, reserve the capacity and write the power of 2

Remove

// Removes the element at the given index. The size of the list is
// decreased by one.
// 
public void RemoveAt(int index) {
    if ((uint)index >= (uint)_size) {
        ThrowHelper.ThrowArgumentOutOfRangeException();
    }
    Contract.EndContractBlock();
    _size--;
    if (index < _size) {
        Array.Copy(_items, index + 1, _items, index, _size - index);
    }
    _items[_size] = default(T);
    _version++;
}

From the source code, we can see that the principle of element deletion is actually using array Copy overwrites the Array.IndexOf enables array IndexOf interface to find the index position of elements. The internal implementation of this interface is to compare each position from 0 to N in index order, with a complexity of O(n)

Insert

// Inserts an element into this list at a given index. The size of the list
// is increased by one. If required, the capacity of the list is doubled
// before inserting the new element.
// 
public void Insert(int index, T item) {
    // Note that insertions at the end are legal.
    if ((uint) index > (uint)_size) {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_ListInsert);
    }
    Contract.EndContractBlock();
    if (_size == _items.Length) EnsureCapacity(_size + 1);
    if (index < _size) {
        Array.Copy(_items, index, _items, index + 1, _size - index);
    }
    _items[index] = item;
    _size++;            
    _version++;
}

Like the Add interface, first check whether the capacity is sufficient, and if not, expand the capacity. It is learned from the source code that when inserting elements, Insert uses the form of copying array to move the elements behind the specified elements in the array backward by one position.

Clear

Array.Clear(_items, 0, _size);

The array is cleared to 0, otherwise the reference of the element in the list will not be - 1, so the element will not be GC

Sort

Quick sort

ToArray

In the ToArray interface, a new array of the specified size is created, and then the contents of the array itself are tested on the new array, and then returned. Use less.

optimization

Delete optimization

If the order is not required, change the position of the element to be deleted with the last element, and then delete the last element
Array.Copy(_items, index + 1, _items, index, _size - index);
This minimizes the assignment when deleting. If item is a reference type, it should be exchanged through deep copy
https://blog.csdn.net/weixin_36464906/article/details/115670601?utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2aggregatepagefirst_rank_ecpm_v1~rank_v31_ecpm-1-115670601.pc_agg_new_rank&utm_term=c%23+list+%E6%93%8D%E4%BD%9C%E4%BC%98%E5%8C%96&spm=1000.2123.3001.4430
However, when the elements in ListB are deleted in batch according to ListA

Determine specific capacity when creating

Set 4, 8, 16, 32, 641282565121024... And so on

Contains optimization

List traverses all elements every time Contains, and uses Dictionary instead of Dictionary ContainsKey(key)，List.AddRange(Dictionary.Values) adds values to the list

List source code and debugging code

https://github.com/luoyikun/UnityForTest
ListScene scene

ListOri.List<int> list = new ListOri.List<int>(64);//Here is the list Count = 0, just pre allocated space for the internal array

        for (int i = 0; i < 64; i++)
        {
            list.Add(i);
        }
        if (list.Contains(32))
        {
            Debug.Log("Find");
        }