System.Generic.Collections.List–internal structure

Ever wondered how List<T> is implemented? Do you know what is the default capacity for List<T> when you call it’s constructor? If not, read on – after this post you should be able to answer such kind of questions. This is not the post for ordinary developers 🙂

Capacity vs. Count

These two can be sometimes troublesome and one can mistake one from another. But most of us get it correct – the count is the actual number of elements on the List<T>. Where the capacity is the total number of elements the internal data structure can hold without resizing.

As you can expect – behind the curtain there is a data structure like this:

private T[] _items;

In such table the List stores it’s elements – all the methods base on this.

So in other words:

  • count – the number of elements actually in the table,
  • capacity – the length of the table.

Default capacity

Ok, so there is a table behind the List<T> object – but actually what is the default capacity when you call default ctor of list? We do not provide any elements at all, we also do not tell how many elements we do expect.

Here, I have to mention that this is not DEFINED and can be changed in the future. I have checked it on the .NET Framework v4.0 (and before) – it is still the same value.

private const int _defaultCapacity = 4;

This is not a big number you say. So the other question is – what happen when you would like to add 5 elements.

Going further, let’s check the Add(T item) method where the first two lines are like that:

if (this._size == this._items.Length)
        this.EnsureCapacity(this._size + 1);

So going further, analyze of EnsureCapacity(int) method leaves us such operation in case if there is no more space to add new element to the table:

int num = this._items.Length == 0 ? _defaultCapacity  : this._items.Length * 2;

As you can see – this line is responsible not only for extending the capacity (binary growth!) but also for setting the default storage capacity.

This gives us quite important info – when you call List() ctor actually the internal table used for storing data object is EMPTY! That’s quite a surprise, you have to admit..

Summary

So in other words List<T> is a simple implementation of the table data objects where extending the data structure is always a nightmare. Thankfully folks at Microsoft created BCL with a great implementation of the List<T> generic collection which gives us all the speed known from table data structure and the nice execution and usage options at the same time.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s