[RESOLVED] List(Of T) internal data representation?

[Atheist]

Hey.

I'm just curious here.. Does anyone know how the List(Of T), represents its collection internally?
Knowing the internal representation could be quite useful as, for example, if it is a linked-list, then we would know that insertion of elements is a fast operation when compared to, say, a dynamic array, while lookups would be slower.
I dont know how anyone, besides the one working on the .NET framework, could know the answer to this question but.. who knows

[RobDog888]

Sup,
The List(Of T) is basically an Array implementing the IList(T) interface as a collection.
For performance comparisons...

In deciding whether to use the List<(Of <(T>)>) or ArrayList class, both of which have similar functionality, remember that the List<(Of <(T>)>) class performs better in most cases and is type safe. If a reference type is used for type T of the List<(Of <(T>)>) class, the behavior of the two classes is identical. However, if a value type is used for type T, you need to consider implementation and boxing issues.

If a value type is used for type T, the compiler generates an implementation of the List<(Of <(T>)>) class specifically for that value type. That means a list element of a List<(Of <(T>)>) object does not have to be boxed before the element can be used, and after about 500 list elements are created the memory saved not boxing list elements is greater than the memory used to generate the class implementation.


It is to your advantage to use the type-specific implementation of the List<(Of <(T>)>) class instead of using the ArrayList class or writing a strongly typed wrapper collection yourself. The reason is your implementation must do what the .NET Framework does for you already, and the common language runtime can share Microsoft intermediate language code and metadata, which your implementation cannot.

Hope that is what you were wanting.

[Atheist]

Aaah I see, good info! Then the next thing that comes to mind is, what initial size would this array have and by how much does it expand when it needs to expand?

[mendhak]

List<> is an ArrayList, just fancier. They implement IList<> and that inherits from ICollection<>.

As for size, I'm not 100% sure what you mean because you can always look at the .length property of it when you want to. Initially, there's nothing, and for each element added it just expands by 1.

[RobDog888]

I think Atheist is more asking if when a new item is added, how does it expand the array. I would say it expands it by the amount needed and not in a block reservation. Although if your using something like .AddRange then it will redimension a block in an amount of what is being added.

[jmcilhinney]

Just like the ArrayList, the List<T> (or List(Of T) in VB) stores its items in an internal array. When you create the List object the array is created with a default length of 0. The current length of the internal array is returned by the List's Capacity property. If you want to create a List with a Capacity other than the default then you use the overloaded constructor that takes an Int32 value representing the initial capacity.

As items are added to the collection the List initially checks whether there is room in the array, i.e. that its Count property is less than its Capacity property. If it's not then it will resize the array. Now, we all know that arrays cannot actually be resized. Just like you or me, the List has to create a new, larger array and then copy the elements from the old array to it. In order to make this more efficient the array is not simply enlarged by one each time. Whenever the array needs to be enlarged its length is doubled, with the one exception that if the current Capacity is zero it will increase to 4. The assumption is that the more items you add, the more items you are likely to add, therefore the amount of space provided is increased geometrically.

Now, if you know that you're about to add a large number of items and the internal array may have to be resized multiple times you can avoid the inefficiency and explicitly set the Capacity property. This means that the array will only be resized once and the operation will therefore be faster.

Try running the following code and observe the output in the Output window:

Dim l As New List(Of String)

Console.WriteLine("Capacity = {0}; Count = {1}", l.Capacity, l.Count)

For i As Integer = 1 To 1000
    l.Add(String.Empty)
    Console.WriteLine("Capacity = {0}; Count = {1}", l.Capacity, l.Count)
Next i

Now change this:

Dim l As New List(Of String)

to this:

Dim l As New List(Of String)(5)

and run it again.

Finally, if you know that you don't want to add any more items you can call the TrimExcess method to resize the array down to the exact length required to fit all the current items. After doing so the Capacity property will return the same value as the Count property, which will be unchanged.

[Atheist]

Ah wonderful information. Just what i wanted to know.

[jmcilhinney]

If you want to see the inner working s of the List class, or any type for that matter, then get Reflector for .NET and take a look for yourself.