C#中List<T>是怎么存放元素的

Jeffrey Zhao在"你的字典里有多少元素？"一文中，提到了他在面試時問過的一個問題：List<T>是怎么存放元素？不幸的是，自己也回答不出來，只知道怎么用，卻不知道為啥這樣用，很明顯的"知其然而不知其所以然"。于是，扒了一段List<T>的一段源碼來一窺究竟。

using System;using System.Diagnostic;using System.Collections.ObjectModel;using System.Security.Permissions;namespace System.Collections.Generic{    ...    [Serializable()]    public class List<t> : IList<t>, System.Collections.IList    {        PRivate const int _defaultCapacity = 4;        private T[] _items; //List<T>內部是依靠數組_items存放數據的        private int _size; //數組的長度        private int _version;        [NoSerialized]        private Object _syncRoot;        static T[] _emptyArray = new T[0];        //無參數構造函數 把_items設置成一個空的數組        public List()        {            _items = _emptyArray;        }        //此構造函數 給_items數組一個初始容量        public List(int capacity)        {            ...            items = new T[capaicty];        }        //此構造函數 把集合類型參數拷貝給_items數組        public List(IEnumerable<t> collection)        {            ...            ICollection<t> c = collection as ICollection<t>;            if(c != null)            {                int count = c.Count; //把構造函數集合類型參數的長度賦值給臨時變量count                _items = new T[count]; //List<T>內部維護的_items數組的長度和構造函數集合類型參數的長度一致                c.CopyTo(_items, 0); //把構造函數集合的所有元素拷貝到_items數組中去                _size = count; //_items數組的長度就是構造函數集合類型參數的長度            }            else            {                _size = 0;                _items = new T[_defaultCapacity];                ...            }        }        //通過設置這個屬性，改變List<t>內部維護的_items數組的長度        public int Capacity        {            get {return _items.Length; }            set {                if(value != _items.Length){ //如果當前賦值和List<t>維護的內部數組_items長度不一致                    if(value < _size){                        //TODO: 處理異常                    }                    if(value > 0){                        T[] newItems = new T[value]; //創建一個臨時的、新的數組，長度為新的賦值                        if(_size > 0){                            //把臨時的、新的數組拷貝給List<t>內部維護的數組_items，注意，這時_items的長度為新的賦值                            Array.Copy(_items, 0, newItems, 0, _size);                         }                    } else {                        _items = _emptyArray;                    }                }            }        }        public void Add(T item)        {            if(_size == _items.Length) EnsureCapacity(_size + 1);            _items[_size++] = item;            ...        }        //確保List<t>內部維護的_items數組的長度至少是給定的值        //如果_items數組原先的長度比給定的值小，就讓_items數組的長度設置為原先的長度的2倍        privat void EnsureCapacity(int min)        {            if(_items.Length < min){                 int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Legnth * 2;                 if(newCapacity < min) newCapacity = min;                 Capacity = newCapacity;            }        }    }}

由此可見，向List<T>中存放元素的大致過程是這樣的：

→List<T>內部維護著一個數組_items，用來存放T類型的元素。→當有新的T類型元素存放進來，即調用Add(T item)方法。→Add(T item)方法內部調用EnsureCapacity(int min)方法確保List<T>的Capaicty屬性值至少在原先長度上加1，最多是原先長度的2倍。→在給Capacity賦值的過程中，對_items的長度進行了擴容。→擴容后，再把新的T類型元素存放進來。

簡單地說：

當有新的元素存放到List<T>中時，List<T>先對其維護的內部數組進行擴容，然后再把新元素放進來。