List 底层原理剖析

实质:List是C#提供的最常见的可伸缩 数组 组件,是通过数组这种数据结构来实现的,而并非链表。使用时无须手动分配内存空间大小,全由List内部类来进行自动扩容分配。

构造部分源码:

public class List<T> : IList<T>, System.Collection.IList, iReadOnlyList<T> {
    private const int _defaultCapacity = 4;    //默认容器大小
    
    private T[] _items;    //核心存储数据结构(一个数组)
    private int _size;    //容器大小
    private int _version;    //容器版本
    private Object _syncRoot;

    static readonly T[] _emptyArray = new T[0];    //创建容器时,创建了一个为空的数组

    //不指定大小的默认构造函数,赋值了一个空的容器
    public List() {
        _items = _emptyArray;
    }

    //指定容器大小的构造函数
    public List(int capacity) {
        //如果指定容器值小于0,抛错。
        if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(
        ExceptionArgument.capacity,
        ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
        Contract.EndContractBlock();

        if (capacity == 0)
            _items = _emptyArray;
        else
            _items = new T[capacity];  
    }
    ......
}

Add方法源码:

public void Add(T item) {
    //检测容量,并扩容
    if (_size == _items.Length) EnsureCapacity(_size + 1);
    _items[_size++] = _items; //将元素添加到数组末尾
    _version++; //版本更新
}

private void EnsureCapacity(int min) {
    if (_items.Length < min) {
        //如果超出了容量,则直接将容量扩充至2倍大小,如果容量本身为0,则扩充为默认大小。
        int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2;
        //如果容量扩充超过了最大数组容量,则将容量变为最大数组容量
        if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
        //如果扩充的容量还是小于当前元素大小,则扩充至当前元素大小
        if (newCapacity < min) newCapacity = min;
        Capacity = newCapacity; //容量赋值
    }
}

Remove方法源码:

//删除给定索引处的元素,列表的大小减1
public bool Remove(T item) {
    int index = IndexOf(item); //查找元素索引
    if (index >= 0) {
        RemoveAt(index); //有索引则删除指定索引
        return true;
    }
    return false;
}

//返回此列表范围内给定值首次出现的索引
//实质是从头到尾向前遍历搜索
//使用Object.Equals方法将列表中的元素与给定值进行比较
public int IndexOf(T item) {
    Contract.Ensure(Contract.Result<int>() >= -1);
    Contract.Ensure(Contract.Result<int>() < count);
    return Array.IndexOf(_items, item, 0, _size); //实质是使用数组内置的IndexOf方法进行查询
}

//删除指定索引处的元素。列表大小减1
public void RemoveAt(int index) {
    //索引范围检测
    if ((uint)index >= (uint)_size) {
        ThrowHelper.ThorwArgumentOutOfRangeException();
    }
    Contract.EndContractBlock();
    _size--; //列表大小减1
    if (index < _size) {
        //实质是使用数组内置的Copy方法进行数组覆盖
        Array.Copy(_items, index + 1, _items, index, _size - index);  //重点:(_size已经提前减1,所以能直接用于计算长度)
    }
    _items[_size] = default[T];
    _version++;
}

Insert方法源码:

private void Insert(int index, T item) {
    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++; //容量+1
    _version++;
}

Contains方法:遍历数组(线性),通过item.Equals方法来比较查找元素是否在数组中。
ToArray方法:利用数组Array.Copy方法创建并复制了一个新的数组返回。
Find方法:遍历数组(线性),通过match方法来比较查找元素,并返回。
ForEach方法:创建新的枚举器实例,通过枚举器来进行遍历操作。(在实际项目中尽量避免使用ForEach函数,因为每次使用ForEach函数都会创建一个新的枚举器实例,最终通过GC单元垃圾回收,大量使用会造成性能问题。)
Sort方法:使用快速排序算法进行排序。

总结:List的实质是对数据用数组进行保存,并拥有一系列维护方法的特殊类,代码是线程不安全的。在效率方面比数组还要差,只是兼容性比较强罢了。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容