数据结构

List

作者：陈广 日期：2019-3-15

---

准备给小分队的同学讲数据结构。之前讲的集合类基本是非泛型类，现在已经跟不上时代了。《数据结构 C#语言描述》这本书需要以 .NET Core 为蓝本，全部更新为讲解泛型类。为给学生先有个参考，首先将所要讲解的集合代码放到文章上来。以后有时间了再更改书的内容。

庆幸的是现在 .NET Core 是开源的，看源码方便很多，至少会有详细注释。这篇文章先讲线性表中的List<T>，源码藏得很深，花了我一点时间才找到在哪个位置：

https://github.com/dotnet/corefx/blob/master/src/Common/src/CoreLib/System/Collections/Generic/List.cs

我这里只把关键代码抽出来讲解。

清单 10-3：List<T>部分源码

using System;

namespace aa
{
    public class List<T>
    {
        private const int DefaultCapacity = 4;

        private T[] _items; // 存放元素的数组
        private int _size; // 指示当前元素个数
        //元素个数为0时的数组状态
        private static readonly T[] s_emptyArray = new T[0];

        //默认构造方法
        public List()
        {
            //这样做可以避免元素个数为0时访问出错
            _items = s_emptyArray;
        }

        // 指定初始容量的构造方法
        public List(int capacity)
        {
            if (capacity < 0)
                throw new ArgumentOutOfRangeException("capacity", "为 ArrayList指定的初始容量不能为负数");
            if (capacity == 0)
                _items = s_emptyArray;
            else
                _items = new T[capacity];
        }

        // 指示List所能容纳的元素个数的属性
        public int Capacity
        {
            get
            {
                return _items.Length;
            }
            set
            {
                if (value < _size)
                {
                    throw new ArgumentOutOfRangeException("value", "容量太小");
                }

                if (value != _items.Length)
                {
                    if (value > 0)
                    {
                        T[] newItems = new T[value];
                        if (_size > 0)
                        {
                            Array.Copy(_items, 0, newItems, 0, _size);
                        }
                        _items = newItems;
                    }
                    else
                    {
                        _items = s_emptyArray;
                    }
                }
            }
        }

        // 指示List所存储的元素个数的属性
        public int Count => _size;

        // Sets or Gets the element at the given index.
        public T this[int index]
        {
            get
            {
                // Following trick can reduce the range check by one
                if ((uint)index >= (uint)_size)
                {
                    throw new ArgumentOutOfRangeException("index", "索引超出范围");
                }
                return _items[index];
            }

            set
            {
                if ((uint)index >= (uint)_size)
                {
                    throw new ArgumentOutOfRangeException("index", "索引超出范围");
                }
                _items[index] = value;
            }
        }

        //添加一个元素
        public void Add(T item)
        {
            T[] array = _items;
            int size = _size;
            if ((uint)size < (uint)array.Length)
            {
                _size = size + 1;
                array[size] = item;
            }
            else
            {
                AddWithResize(item);
            }
        }
        //更改List容量后添加一个元素
        private void AddWithResize(T item)
        {
            int size = _size;
            EnsureCapacity(size + 1);
            _size = size + 1;
            _items[size] = item;
        }

        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;
            }
        }

        // 在指定索引处插入元素
        public void Insert(int index, T item)
        {
            // Note that insertions at the end are legal.
            if ((uint)index > (uint)_size)
            {
                throw new ArgumentOutOfRangeException("index", "索引超出范围");
            }
            if (_size == _items.Length) EnsureCapacity(_size + 1);
            if (index < _size)
            {
                Array.Copy(_items, index, _items, index + 1, _size - index);
            }
            _items[index] = item;
            _size++;
        }

        // 删除指定索引的元素
        public void RemoveAt(int index)
        {
            if ((uint)index >= (uint)_size)
            {
                throw new ArgumentOutOfRangeException("index", "索引超出范围");
            }
            _size--;
            if (index < _size)
            {
                Array.Copy(_items, index + 1, _items, index, _size - index);
            }
        }
    }
}

栈源码（Stack.cs）： https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/Stack.cs

队列源码（Queue.cs） https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/Queue.cs

;