Append in IEnumerable<T> - C#

Question

Hello,

I wrote the following code:

IEnumerable<int> list = Enumerable.Empty<int>();  
list = list.Append(1);  
list = list.Append(2);  
  
Console.WriteLine(string.Join(' ', list));  

When we append a number to the list, What data structure is used? an array of int? List of int?
I am confused because IEnumerable<int> doesn't data sturucture.

Answer 1

Enumberable.Empty<int> return an array of int with zero elements. see the Empty() method implementation in the Enumerable class.

public static IEnumerable<TResult> Empty<TResult>() {  
            return EmptyEnumerable<TResult>.Instance;  
}  

Refer: https://github.com/Microsoft/referencesource/blob/master/System.Core/System/Linq/Enumerable.cs

and see the EmptyEnumerable<T> method below

internal class EmptyEnumerable<TElement>  
    {  
        public static readonly TElement[] Instance = new TElement[0];  
    }  

Basically when you call Enumberable.Empty<int>, it return an Array of int with size 0. An interesting read for the topic is given below.

https://agirlamonggeeks.com/2019/03/22/enumerable-empty-vs-new-ienumerable-whats-better/

Hope this helps

Answer 2

Enumerable.Empty<T> returns an EmptyPartition<T>:
https://github.com/dotnet/runtime/blob/57bfe474518ab5b7cfe6bf7424a79ce3af9d6657/src/libraries/System.Linq/src/System/Linq/Enumerable.SpeedOpt.cs#L10

This is just a special-case empty "no-op" class that implements an Iterator<T> but is implemented to not move to the first element when iterated:
https://github.com/dotnet/runtime/blob/57bfe474518ab5b7cfe6bf7424a79ce3af9d6657/src/libraries/System.Linq/src/System/Linq/Partition.SpeedOpt.cs#L35

The first time you call .Append() you get back an AppendPrepend1Iterator saved back to you list variable. The second time you get an AppendPrependN:
https://github.com/dotnet/runtime/blob/57bfe474518ab5b7cfe6bf7424a79ce3af9d6657/src/libraries/System.Linq/src/System/Linq/AppendPrepend.cs#L18
https://github.com/dotnet/runtime/blob/57bfe474518ab5b7cfe6bf7424a79ce3af9d6657/src/libraries/System.Linq/src/System/Linq/AppendPrepend.cs#L141

Both of these types represent iterators, which hold a reference to the source data structure (EmptyPartition<T> in the first instance, or one of these iterator types on subsequent instances) and also the new element you're adding.

After all new items are appended you'll have a nested sequence of iterators, where you can think of each iterator as "the operation of appending an single item to a source sequence", which when iterated through (as string.Join will be doing internally) will step through the elements of the last iterator (the AppendPrependN in this case), which will invoke each of the nested iterators in turn, resulting in all items across all nested iterators being printed.

Apologies if this is a confusing explanation - there's a lot of engineering that goes into Linq to make it lightweight in terms of memory & speed (while also keeping operations lazy), so the implementation is quite abstract.