目录
介绍
背景
编码此混乱
本文是关于编写集合和列表类的。它将引导您了解在自定义数据结构上实现IEnumerable、IEnumerator、ICollection和IList的详细信息。
本文的原因是该主题未得到很好的介绍，并且使用这些接口时，Microsoft还没有明确记录这些陷阱。因此，我们将把此类的开发分解为可管理的步骤。
背景.NET中的列表类为任意可变项计数提供foreach枚举、索引寻址和常规存储。它们的工作方式与.NET中的array非常相似，只是它们本质上是可调整大小的。在.NET中，arrays本身实现了IList。
使用列表的主要.NET类是List。它在内部数组上提供了完整的功能列表，并根据需要调整大小。
通常，这是有效且适当的，但在某些情况下可能并非如此。Microsoft在其LinkedList类中提供了一个替代方法，该方法将值存储为链接列表而不是数组。
我们将实现自己的链表。而使用Microsoft高度优化的类是最好的，该类将像说明的一样很好地帮助我们。在此过程中，我们将介绍实现列表的所有主要组成部分和陷阱，以便您的实际列表在实践中可以良好且高效地工作。
编码此混乱为了使内容清晰，我将主要接口分为几个子类。
让我们从LinkedList.cs中的数据结构本身开始。
// the basic LinkedList core
public partial class LinkedList
{
// a node class holds the actual entries.
private class _Node
{
// holds the value of the current entry
public T Value = default(T);
// holds the next instance in the list
public _Node Next = null;
}
// we must always point to the root, or null
// if empty
_Node _root=null;
}就其本身而言，这根本不是列表！它没有实现任何相关接口，但确实包含一个嵌套类，该类保留了我们的节点结构。该节点是链表中的单个节点。它保存一个类型T的值，且下一个节点作为字段。外部类还包含一个字段，用于保存列表中的第一个节点，或者如果列表为空则为null。
我喜欢通过实现使foreach可用的IEnumerable/IEnumerator 来开始对列表接口进行编码，因为它是一种基本操作，除了数据结构本身之外，它通常没有任何代码依赖性。让我们访问LinkedList.Enumerable.cs：
partial class LinkedList : IEnumerable
{
// versioning is used so that if the collection is changed
// during a foreach/enumeration, the enumerator will know to
// throw an exception. Every time we add, remove, insert,
// set, or clear, we increment the version. This is used in
// turn by the enumeration class, which checks it before
// performing any significant operation.
int _version = 0;
// all this does is return a new instance of our Enumeration
// struct
public IEnumerator GetEnumerator()
{
return new Enumerator(this);
}
// legacy collection support (required)
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
=> GetEnumerator();
// this is the meat of our enumeration capabilities
struct Enumerator : IEnumerator
{
// we need a link to our outer class for finding the
// root node and for versioning.
// see the _version field comments in LinkedList
LinkedList _outer;
// hold the value of _outer._version we got when the
// enumerator was created. This is compared to the
// _outer._version field to see if it has changed.
int _version;
// this is our state so we know where we are while
// enumerating. -1 = Initial, -2 = Past end,
// -3 = Disposed, and 0 means enumerating
int _state;
// the current node we're on.
_Node _current;
public Enumerator(LinkedList outer)
{
_outer = outer;
_version = outer._version;
_current = null;
_state = -1;
}
// reset the enumeration to the initial state
// if not disposed.
public void Reset()
{
_CheckDisposed();
_current = null;
_state = -1;
}
// just set the state to inform the class
void IDisposable.Dispose()
{
_state = -3;
}
// performs the meat of our _Node
// traversal
public bool MoveNext()
{
// can't enum if disposed
_CheckDisposed();
switch (_state)
{
case -1: // initial
_CheckVersion();
// just set the current to the root
_current = _outer._root;
if (null == _current)
{
// our enumeration is empty
_state = -2;
return false;
}
// we're enumerating
_state = 0;
break;
case -2: // past the end
return false;
case 0: // enumerating
_CheckVersion();
// just move to the next
// _Node instance
// if it's null, stop enumerating
_current = _current.Next;
if (null == _current)
{
_state = -2;
return false;
}
break;
}
return true;
}
public T Current {
get {
switch (_state)
{
// throw the appropriate
// error if necessary
case -1:
throw new InvalidOperationException
("The enumeration is before the start position.");
case -2:
throw new InvalidOperationException
("The enumeration is past the end position.");
case -3:
// always throws
_CheckDisposed();
break;
}
_CheckVersion();
return _current.Value;
}
}
// legacy support (required)
object System.Collections.IEnumerator.Current => Current;
// throws if disposed
void _CheckDisposed()
{
if (-3 == _state)
throw new ObjectDisposedException(GetType().FullName);
}
// throws if versions don't match
void _CheckVersion()
{
if (_version != _outer._version)
throw new InvalidOperationException("The enumeration has changed.");
}
}
}这有很多需要注意的地方，您可能想知道为什么我们不仅仅通过yield语法使用C＃迭代器，但是有一个很好的理由，那就是版本控制和重置。
为了提供IEnumerator对集合的正确实现，必须跟踪集合以确保在枚举项时它没有发生变化。这是使用_version字段完成的。每次更改集合时，版本都会增加。将该字段与枚举器的副本进行比较，以查看它们是否相同。如果不是，则枚举器将抛出。C＃迭代器不提供此功能，但是对于完整、正确且健壮的列表实现而言，这是必需的。
此外，迭代器不支持Reset()。虽然尚未使用foreach，但其他使用者也可以使用它，并且通常可以使用。
如果您真的不想实现所有这些功能，则可以使用C＃迭代器支持，但请记住，这不是列表枚举器的规范或完整实现。
注意_state字段的使用。它的主要目的是用于错误处理，因此我们可以区分是在开始，结束还是释放。另请注意，我们始终会检查版本并检查几乎所有操作的释放情况。这对于使枚举器变得强大很重要。
与所有枚举器实现一样，MoveNext()是枚举器的核心，其工作是将光标前移一个。它返回true如果有更多的项进行读取，或返回false表明没有更多的项目。在此例中，我们只是简单地遍历链表，并适当地更新状态。同时，Current，Reset()和Dispose()都是简单的。
接下来，我们有了ICollection，它实质上提供了一个用于存储和检索类中项的基本接口。
// linked list collection interface implementation
partial class LinkedList : ICollection
{
// we keep a cached _count field so that
// we don't need to enumerate the entire
// list to find the count. it is altered
// whenever items are added, removed, or
// inserted.
int _count=0;
public int Count {
get {
return _count;
}
}
// returns true if one of the nodes has
// the specified value
public bool Contains(T value)
{
// start at the root
var current = _root;
while(null!=current)
{
// enumerate and check each value
if (Equals(value, current.Value))
return true;
current = current.Next;
}
return false;
}
public void CopyTo(T[] array,int index)
{
var i = _count;
// check our parameters for validity
if (null == array)
throw new ArgumentNullException(nameof(array));
if (1 != array.Rank || 0 != array.GetLowerBound(0))
throw new ArgumentException("The array is not an SZArray", nameof(array));
if (0 > index)
throw new ArgumentOutOfRangeException(nameof(index),
"The index cannot be less than zero.");
if (array.Length array.Length + index)
throw new ArgumentException
("The array is not big enough to hold the collection entries.", nameof(array));
i = 0;
var current = _root;
while (null != current)
{
// enumerate the values and set
// each array element
array[i + index] = current.Value;
++i;
current = current.Next;
}
}
// required for ICollection but we don't really need it
bool ICollection.IsReadOnly => false;
// adds an item to the linked list
public void Add(T value)
{
_Node prev = null;
// start at the root
var current = _root;
// find the final element
while (null != current)
{
prev = current;
current = current.Next;
}
if (null == prev)
{
// is the root
_root = new _Node();
_root.Value = value;
}
else
{
// add to the end
var n = new _Node();
n.Value = value;
prev.Next = n;
}
// increment count and version
++_count;
++_version;
}
// simply clears the list
public void Clear()
{
_root = null;
_count = 0;
++_version;
}
// removes the first item with the
// specified value
public bool Remove(T value)
{
_Node prev = null;
var current = _root;
while (null != current)
{
// find the value.
if(Equals(value,current.Value))
{
if(null!=prev) // not the root
// set the previous next pointer
// to the current's next pointer
// effectively eliminating
// current
prev.Next = current.Next;
else // set the root
// we just want the next value
// it will eliminate current
_root = current.Next;
// decrement the count
--_count;
// increment the version
++_version;
return true;
}
// iterate
prev = current;
current = current.Next;
}
// couldn't find the value
return false;
}
}请注意该_count字段的添加。集合消费者将期望Count属性非常快。但是，为了检索链接列表中的项目数，通常必须遍历列表中的每个项才能找到它。在这种情况下，这是不希望的，因此，每次我们从列表中添加和删除项目时，我们都会相应地更新该_count字段。这样，我们避免了不必要的性能下降。在实现自定义集合时，这是一种非常常见的模式。
其余成员在表面上或通过上面的评论都是不言自明的。请注意，应谨慎使用错误处理，并在更新集合时仔细记录_count和_version字段。这很关键。这里要注意是CopyTo()方法，索引引用array中的index开始复制-而不是集合的索引。也就是说，index是目标索引。
现在开始在LinkedList.List.cs中实现IList：
// gets or sets the value at the specified index
public T this[int index] {
get {
// check the index for validity
if (0 > index || index >= _count)
throw new IndexOutOfRangeException();
// start at the root
var current = _root;
// enumerate up to the index
for (var i = 0;i index || index >= _count)
throw new IndexOutOfRangeException();
// start at the root
var current = _root;
// enumerate up to the index
for (var i = 0; i < index; ++i)
current = current.Next;
// set the value at the current index
current.Value=value;
// increment the version
++_version;
}
}
// returns the index of the specified value
public int IndexOf(T value)
{
// track the index
var i = 0;
// start at the root
var current = _root;
while (null!=current)
{
// enumerate checking the value
if (Equals(current.Value, value))
return i; // found
// increment the current index
++i;
// iterate
current = current.Next;
}
// not found
return -1;
}
// inserts an item *before* the specified position
public void Insert(int index,T value)
{
// check index for validity
// the index can be the count in order to insert
// as the last item.
if (0 > index || index > _count)
throw new ArgumentOutOfRangeException(nameof(index));
if (0 == index) // insert at the beginning
{
_Node n = new _Node();
n.Next = _root;
n.Value = value;
_root = n;
}
else if (_count == index) // insert at the end
{
Add(value);
return;
}
else // insert in the middle somewhere
{
// start at the root
var current = _root;
_Node prev = null;
// iterate up to the index
for (var i = 0; i < index; ++i)
{
prev = current;
current = current.Next;
}
// insert a new node at the position
var n = new _Node();
n.Value = value;
n.Next = current;
prev.Next = n;
}
// update the version and increment the count
++_version;
++_count;
}
// removes the item at the specified index
public void RemoveAt(int index)
{
// check the index for validity
if (0 > index || index >= _count)
throw new ArgumentOutOfRangeException(nameof(index));
// start at the root
var current = _root;
_Node prev = null;
if (1 == _count) // special case for single item
_root = null;
else
{
// iterate through the nodes up to index
for (var i = 0; i < index; ++i)
{
prev = current;
current = current.Next;
}
// replace the previous next node with
// current next node, effectively removing
// current
if (null == prev)
_root = _root.Next;
else
prev.Next = current.Next;
}
// decrement the count
--_count;
// increment the version
++_version;
}
}这里的许多代码是不言自明的。请注意要更新this[int index].set属性上的_version！ Insert()只是因为链接列表的工作方式而变得如此复杂。Insert()的唯一注意事项是，index引用新项之后的index，并且可以高达_count而不是_count-1。因此，插入在概念上应被视为“在索引之前插入”。
IList需要注意是：实现并不总是合适的。实际上，由于链表的工作方式，它不像数组那样真正不支持直接索引。当然我们已经模拟了它，但是它并不是真正有效的，因为我们必须进行迭代。因此，不一定要在链表顶部实现此接口。我们在此只是出于演示目的。在现实世界中，您将选择最适合您的数据结构的集合接口。在这里，如果不实现IList，ICollection可能是合适的。
最后，进入我们的构造器，可以在LinkedList.Constructors.cs中找到：
partial class LinkedList
{
// optimized constructor for adding a collection
public LinkedList(IEnumerable collection)
{
// check for collection validity
if (null == collection)
throw new ArgumentNullException(nameof(collection));
// track the count
int c = 0;
// track the current node
_Node current = null;
// enumerate the collection
foreach(var item in collection)
{
// if this is the first item
if(null==current)
{
// set the root
_root = new _Node();
_root.Value = item;
current = _root;
} else
{
// set the next item
var n = new _Node();
n.Value = item;
current.Next = n;
current = n;
}
++c;
}
// set the count
_count = c;
}
// default constructor
public LinkedList() {
}
}在这里，我们提供了一个默认构造函数和一个从现有collection或array复制的构造函数。这些确实是您要提供的最少构造函数。其他类型可能更合适，具体取决于您的内部数据结构。例如，如果它是基于数组的，则可能有一个capacity，而B树可能有一个order。在这种情况下，采用集合的构造函数已经过优化，但是通常您希望提供它，即使它所做的只是在循环中对其自身进行调用Add()。
就是这样！现在，您有了一个健壮的列表实现，可以正确地处理错误，高效并正确处理列表的各种陷阱。话虽如此，请不要在生产中使用此链接列表。Microsoft的实现可能会更优化，并且肯定会经过更多测试。但是，这应该为您提供实现自己的数据结构的前进的道路。
