List内部是用数组实现的,而不是链表,并且当没有给予指定容量时,初始的容量为0
// 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; } }
每次容量不够的时候,整个数组的容量都会扩充一倍,_defaultCapacity 是容量的默认值为4。因此整个扩充的路线为4,8,16,32,64,128,256,512,1024…依次类推。所以创建时预定好容量,写入 2的幂
// 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++; }
从源码中我们可以看到,元素删除的原理其实就是用 Array.Copy 对数组进行覆盖。IndexOf 启用的是 Array.IndexOf 接口来查找元素的索引位置,这个接口本身内部实现是就是按索引顺序从0到n对每个位置的比较,复杂度为O(n)
// 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++; }
与Add接口一样,先检查容量是否足够,不足则扩容。从源码中获悉,Insert插入元素时,使用的用拷贝数组的形式,将数组里的指定元素后面的元素向后移动一个位置。
Array.Clear(_items, 0, _size);
数组清0,不然list内元素的引用不会-1,导致元素不会被GC
快速排序
ToArray接口中,重新new了一个指定大小的数组,再将本身数组上的内容考别到新数组上,再返回出来。少用。
如果对顺序无要求,把要删除的元素与最后一个元素换位置,再删除最后一个元素
Array.Copy(_items, index + 1, _items, index, _size - index);
这样可以使删除时赋值最少。对于item是引用类型要通过深拷贝进行交换
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
但是在根据ListA批量ListB中元素删除时
分别设置4,8,16,32,64,128,256,512,1024…依次类推
List每次Contains遍历全部元素,使用Dictionary替代,Dictionary.ContainsKey(key),List.AddRange(Dictionary.Values)将值加到List里
https://github.com/luoyikun/UnityForTest
ListScene场景
ListOri.List<int> list = new ListOri.List<int>(64);//这里list.Count = 0,只是把内部数组预先分配了空间 for (int i = 0; i < 64; i++) { list.Add(i); } if (list.Contains(32)) { Debug.Log("Find"); }