CODEWITHSUNDEEP
c#arraysdata-structuresienumerable
ritratt
ritratt

Reputation: 1858

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

I was reading basic tutorials on implementing the methods of the interface IENumerable and found out that all examples use arrays. I was under the impression that an IENumerable is essentially very similar to a linked list. And I am fairly confident that an array and a linked list are two completely different data structures.

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

This is how the code looks like on MSDN page:

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

Is there an implementation of IENumerable that I have missed?

Edit: I now understand that IENumerable doesn't necessarily resemble a linked list. However, this code from MSDN implements an IList using an array:

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

Upvotes: 2

Views: 701

Answers (3)

Peter Duniho
Peter Duniho

Reputation: 70671

The short answer: IEnumerable is "similar to" a linked list only in that it defines a sequence of values. But a sequence of values can be defined in any number of other ways as well, including as an array.

The IEnumerable type is an interface. It dictates only what something must expose publicly; it doesn't in any specific way dictate what the implementation should be.

In the case of 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. That interface must in turn implement a property named Current, which returns an instance of object, and a method named MoveNext() which informs the IEnumerator object to select the next item in the enumeration.

(The interface also requires implementation of a Reset() method, but many implementations of the interface just throw NotSupportedException for that method…the Current and MoveNext() members are the minimum to make a useful implementation of the interface).

The enumeration can be implemented in whatever manner is suitable for the object implementing it. The System.Linq.Enumerable type even includes implementations that simply repeat the same value some number of times, or which emits a sequence of integers. None of the members of that type store an enumeration per se; they either create one from scratch, or transform some existing one.

Likewise, you could enumerate lines of text in a file, or pick numbers at random, or reverse the elements of an array. The only thing that matters is that you have some mechanism to choose a sequence of values.

The example you posted doesn't actually show us the implementation of IEnumerator…there's some unknown class named PeopleEnum that handles the enumeration. Presumably, this class simply stores an index into the array of the object passed to it, returning each element in sequence (it could also be implemented using an "iterator method", but it wouldn't need a whole other type to accomplish that, so I'm guessing it wasn't).

I hope the above helps more than confuses. :)

Upvotes: 0

nvoigt
nvoigt

Reputation: 77304

IEnumerable and IEnumerable<T> are not linked lists. They are interfaces that provide access to enumeration.

Think of it this way: IEnumerable is a promise to deliver 0-n values on enumeration (for example by using foreach).

Many real classes can fulfill this promise. Lists do, arrays do, collections of all kinds do, your own classes may if you program them to do so. How you get stuff into or out of your container is container specific, IEnumerable only says something about how to get data from your container to do something with it.

That's a very easy explanation, you may want to read about deferred execution later when you got this concept down.

Upvotes: 0

Yuval Itzchakov
Yuval Itzchakov

Reputation: 149538

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

I'm not really sure where you got that impression. An object implementing IEnumerable or IEnumerable<T> means "this object exposes an enumerator, which makes it iteratable", it has nothing to do directly to an implementation of a linked list, or an array. They do both share the common feature of being iteratable. It is a binding contract to the caller.

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

A linked list can have an array as it's storage as an implementation detail, though that would definitely be a poor design choice.

You may note that List<T> also uses an array as it's internal storage, which it re-sizes once it hits the maximum size of the internal array.

Upvotes: 4

Related Questions