So in this video, we're going to find the answer to the question 24, what is AL East?
This may seem like a three real question to you and maybe even roll your eyes a little.
You've probably used least thousands of times.
Nevertheless, I think it's worth taking a while to understand how this work exactly and what is going
on under the hood.
Wrist of T is a strongly type generic collection of objects.
These are dynamic, which means we can add or remove the elements from them.
We can access list elements using an index are just like we do with an array.
This provoked a wide selection of built in methods which make them much more convenient than planned,
right?
Let me show you some, but certainly not all of them.
Because of the dynamic nature of lists and their convenience, they are probably the most often used
collection type in C-sharp.
Let's take a look under the hood of the list.
It turns out that the list is actually a fancy wrapper over an array, and all the list data is held
in a private area.
We can see it here in the least glass source code.
Least exposed is a property called capacity.
This property says what is the size of this private area held by the East?
Let's see this in practice.
Let's see what will be presented to the council.
That's interesting.
After a new list is created, its internal process is zero done after an element is added.
The south is changed to four.
I don't literally mean changing because as we learned in the previous lecture, the size of an array
can change.
I will explain what happens here in a minute, but first, let's add a couple more of elements to exceed
the four elements limit.
It seems the South grew twice, it was four, but now it is eight before explaining.
Let me just clear the East.
Even if the list has been emptied, the capacity remained as it was, so it still holds an array of
size eight as its internal data structure.
All right.
Let's see what's going on when we insert the first element to the list, it cautiously assumes that
maybe the underlying aura does not need to be very large.
It creates an aura of size four and assigns it to the private items field.
Would we have seen in the snippet from the source code?
This area is used as long as the count of elements in the list is smaller or equal to four.
But what this count is accident ghosts can no longer fit elements in the underlying aura.
It's simply too small.
So what it needs to do is this.
First, it creates a new arrow, double the size of the old one.
Then it copies all elements from the old arrow to the new arrow.
After that, it can add the new element that previously didn't fit into the smaller arrow.
So as you can see, it's not like the size of the underlying arrow tenders.
It does not, as it's not possible to resize an arrow in C-sharp.
Brand new arrow is created under the old arrow is replaced by it on one hand.
This is pretty clever, as it allows us to use our fixed size underlying collection to actually represent
dynamic data, on the other hand.
It's not great from the performance point of view.
Once you resizing is needed, the least must perform this quite complex operation of allocating a new
era and copying the old one into it.
That's why it's quite generous when allocating a new arrow, and it makes it double the size of the
old one.
If the new arrow would be too small, it would soon need to be precise again.
And we want to avoid that.
On the other hand, of course, happen that more memory than we need is allocated.
For example, if we exceeded the count of 2024 announced, the list will create a new array of size
2048.
But it may be the case that in our business, case 1025 is the absolute limitation above which the list
will never grow.
In this case, we can help the list a little and tell it what kind of elements it should be ready for
by using the constructor parameter.
We should definitely consider doing that if we know upfront what is the expected size of the list.
Remember that it's not set in stone and once it's exceeded released, we resize as normal.
But what we're doing is avoiding all the resizing operations that would normally happen between zero
and 1050 almonds.
Here I am generating a collection of 2000's numbers and adding it to the existing list.
2000's Element didn't fit in, the 1050 elements are so the list needed to be resized.
But it happened only once instead of a couple of times because the operation of resizing is so heavy,
the list doesn't reduce its size once elements are removed.
It rather wants to assume that the allocated space will be needed sooner or later.
Since it has already been in need at once.
If we had good reasons to think that the larger space needed was a one time thing, we can either accept
the capacity to a smaller number manually or call the trim access method.
Would you say that the capacity to the actual count of elements nearest?
Here, I removed all elements from the list and then added only one.
Then I called the trim access method, which would trim the capacity to the actual count of elements.
And this is exactly what happened, and the capacity is now one.
Remember that when setting the capacity manually, we can't make it smaller than the actual count of
elements in the list.
Otherwise, an exception will be thrown.
This line will throw an exception because I have two elements in the list, and I'm trying to set the
capacity to one.
And to reduce the exemption, we expect it.
All right.
We now know how things work under the hood of the list and that in the end, all data is held in an
hour.
We must be aware that this has more implications than only resizing the array once its capacity is exceeded.
Let's consider the following code.
The insert method takes two parameters the index at which the new value will be placed in the list and
the value to be inserted in this case.
Four will be inserted at Index three, which is between values three and five innocent.
As this operation seems, we must consider what happens with the array that is used underneath before
the insert operation.
The arrow looks like this.
The capacity of the list is eight, which means it is also the length of the array.
Please be aware that the last three elements are actually zeros, so the default for the integer type
that is stored in this list, the least knows they are not the part of the represented data because
it remembers the count of elements.
It starts and knows that anything after index count minus one is not the actual data, but the cyberspace
that can be occupied by some new values later.
All right back to the insert method.
We can't simply set the month at index free to value for because we would overwrite the value.
Five.
We must move all the months after the given index one index forward to make room for the new volume.
This is again impacting the performance.
Worst case, we may need to move each element in the least if we insert at index zero.
This means the performance of this operation is so often.
The insert method is just an example to show you that an operation that does something that the underlying
error does not support.
Like in this case, inserting the element in the middle of the data will always impact the performance
as the data in the array must be rearranged.
This is something to be aware of when working with lists, especially loved ones, as the performance
impact might be noticeable.
To summarize, lists are great when it comes to representing collections that are dynamic.
They give us a lot of useful methods, like working with them simple and efficient.
But we must be aware that adding a feature of dynamic size to the fixed size collection like error comes
with a cost and this cost is performance.
During the interview, you can be asked Why is it a good idea to set the capacity of the list in the
constructor?
If we know the expected count of the elements upfront, because this way will avoid the performance
costly operation of copying the underlying array into a new, larger one, which happens when we exceed
the count of four, eight, 16 and so on elements.
What is the complexity of the insert metric from lowest class?
The insert method needs to move forward.
Some of the elements of the underlying array to make room for the new element.
In the worst case scenario, when we insert an element at the beginning of the list, we'll need to
move all existing elements.
This means the complexity of this operation is, oh, often alright.
We learned about one of the most useful collections inside for the list.
Thanks for watching this video and see you in the next one.