为什么使用数组而不是链表来实现 IEnumerable（或 IList）？

Question

我正在阅读有关实现 IENumerable 接口方法的基础教程，发现所有示例都使用数组。我的印象是 IENumerable 本质上与链表非常相似。而且我相当有信心数组和链表是两种完全不同的数据结构。

那么为什么一个（链表）使用另一个（数组）来实现，而我们实际上认为它们完全不同？

MSDN 页面上的代码如下所示：

// Collection of Person objects. This class 
// implements IEnumerable so that it can be used 
// with ForEach syntax. 
public class People : IEnumerable
{
    private Person[] _people;
    public People(Person[] pArray)
    {
        _people = new Person[pArray.Length];

        for (int i = 0; i < pArray.Length; i++)
        {
            _people[i] = pArray[i];
        }
    }

// Implementation for the GetEnumerator method.
    IEnumerator IEnumerable.GetEnumerator()
    {
       return (IEnumerator) GetEnumerator();
    }

    public PeopleEnum GetEnumerator()
    {
        return new PeopleEnum(_people);
    }
}

是否有我错过的 IENumerable 实现？

编辑：我现在明白 IENumerable 不一定类似于链表。但是，MSDN 中的这段代码使用数组实现了一个 IList：

class SimpleList : IList
{
    private object[] _contents = new object[8];
    private int _count;

    public SimpleList()
    {
        _count = 0;
    }

    // IList Members 
    public int Add(object value)
    {
        if (_count < _contents.Length)
        {
            _contents[_count] = value;
            _count++;

            return (_count - 1);
        }
        else
        {
            return -1;
        }
    }
//etc...
}

Answer 1

I was under the impression that an IENumerable is essentially very similar to a linked list.

我不太确定你是从哪里得到这种印象的。实现IEnumerable或IEnumerable<T>的对象意味着"this object exposes an enumerator, which makes it iteratable"，它与链表或数组的实现没有直接关系。它们 do 都具有可迭代的共同特征。它是对调用者具有约束力的合同。

So then why is one (a linked list) being implemented using the other (an array) when we actually argue that they are quite different?

链表可以有一个数组，因为它作为实现细节存储，尽管这绝对是一个糟糕的设计选择。

您可能会注意到 List<T> 还使用数组作为其内部存储，一旦达到内部数组的最大大小，它就会重新调整大小。

Answer 2

IEnumerable 和 IEnumerable<T> 不是链表。它们是提供枚举访问的接口。

这样想：IEnumerable 承诺在枚举上提供 0-n 值（例如通过使用 foreach）。

很多真实的类都能兑现这个诺言。列表可以，数组可以，各种集合可以，您自己的类如果您对它们进行编程，则可以这样做。你如何将东西放入或出你的容器是特定于容器的，IEnumerable 只说明了如何获取数据从你的容器中用它做一些事情。

这是一个非常简单的解释，当你理解了这个概念后，你可能想阅读有关延迟执行的内容。

Answer 3

简短的回答：IEnumerable 是 "similar to" 一个链表，只是因为它定义了一个值序列。但是也可以用任何其他方式定义值序列，包括作为数组。

IEnumerable 类型是 interface。它只规定了必须公开的东西；它没有以任何特定方式规定实现应该是什么。

以IEnumerable, the only thing something that implements that interface must do is implement a method named GetEnumerator(), which must return an instance of another interface, IEnumerator为例。该接口必须依次实现一个名为 Current 的属性，其中 returns 是 object 的一个实例，以及一个名为 MoveNext() 的方法，该方法通知 IEnumerator 反对 select 枚举中的下一项。

（该接口还需要实现一个 Reset() 方法，但是该接口的许多实现只为该方法抛出 NotSupportedException ...... Current 和 MoveNext() 成员是对接口进行有用实现的最低要求。

枚举可以以适合实现它的对象的任何方式实现。 System.Linq.Enumerable 类型甚至包括简单地重复相同值多次或发出整数序列的实现。 None 该类型的成员存储枚举本身；他们要么从头开始创建一个，要么改造一些现有的。

同样，您可以枚举文件中的文本行，或随机选择数字，或反转数组的元素。唯一重要的是你有一些机制来选择一系列值。

您发布的示例实际上并没有向我们展示 IEnumerator 的实现…有一些未知的 class 名为 PeopleEnum 来处理枚举。据推测，这个 class 只是将索引存储到传递给它的对象的数组中，按顺序返回每个元素（它也可以使用 "iterator method" 来实现，但它不需要整个其他类型来完成它，所以我猜它不是）。

我希望以上内容对您有所帮助，而不是造成混淆。 :)

为什么使用数组而不是链表来实现 IEnumerable（或 IList）？

Why is an IEnumerable(or IList) implemented using arrays instead of Linked Lists?

c#

arrays

ienumerable

data-structures