数组与链表
数组（Array）
数组在计算机中使用非常广泛，是由相同类型的元素的集合所组成的数据结构，当然现在的高级语言对类型的限定也比较多样化，有一个标准的叫法，叫做“泛型”。数组的底层实现是有一个叫做内存管理器的东西，每当你向计算机申请数组的时候，计算机会在内存中开辟一段连续的地址，每一个地址可以直接通过内存管理器去访问，所以访问数组中的第一个元素和数组中的任何一个元素时间复杂度都是一样的，都是O(1)
特性：
随机访问操作速度非常快，O(1)
插入一个元素，得把后续的元素往后挪移一个位置，O(n)；
删除一个元素，和插入类似，也得把后续的元素往前挪一个位置，O(n)。所以如果对一个数组频繁
源码分析：
C# 的 List 源码实现，List 的实际容器即为泛型数组 T[]，当执行插入和删除操作时，为了挪动其余元素，使用了大量的复制操作，不是很高效
List.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++;
}功能：在 List 的指定 index 位置插入元素 item
检查insert的位置是否合法，如果有必要，需要调用 EnsureCapacity 方法进行扩容
满足插入条件后，调用 Array.Copy 方法，将index位置以及往后的元素都向后挪1位，然后将要插入的元素插入到index位置上
List.EnsureCapacity 方法
// 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;
}
}
// Gets and sets the capacity of this list. The capacity is the size of
// the internal array used to hold items. When set, the internal
// array of the list is reallocated to the given capacity.
//
public int Capacity {
get {
Contract.Ensures(Contract.Result<int>() >= 0);
return _items.Length;
}
set {
if (value < _size) {
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
}
Contract.EndContractBlock();
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 = _emptyArray;
}
}
}
}功能：确保 List 的长度大于给定的 min 值
若当前容量不足需要扩容，首先容量变为当前容量的 2 倍，如果还不够，就按给定的 min 为数组容量
计算完扩容的值后，是通过修改 List.Capacity 属性来实现的，具体实现很暴力，就是 new 了一个新的数组，然后通过 Array.Copy 把当前数组里的内容复制了过去
RemoveAt 方法
// 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++;
}功能：移除位于 index 位置的元素
通过 Array.Copy 方法将 index 位置之后的所有元素向前挪1位，当然也就覆盖了 index 位置，然后将 List 的最后一位置为默认值
链表（Linked List）
在频繁需要添加和删除操作的时候，数组效率低下，而链表这个数据结构就是为了弥补数组的这个缺点。链表是由一串节点组成的链形结构，节点一般由一个 class 来定义，这个 class 由 Value 和 Next 指针组成，Next 用来指向下一个节点。只有 Next 的节点叫做“单向链表”，当然也可以定义一个 Previous 指针用来指向这个节点的前一个节点，这样的链表就变成了 “双向链表”。如果 Tail 节点的 Next 不是 null 而是 Head 节点，那么就形成了 “循环链表”
代码实现：
public class LinkedList<T>
{
public Node<T> Head { get; set; }
public class Node<T>
{
public T Value { get; set; }
public Node<T> Next { get; set; }
public Node(T value) { Value = value; }
}
}