1
00:00:07,110 --> 00:00:13,770
So in this video, we're going to find the answer to the question 24, what is AL East?

2
00:00:14,190 --> 00:00:19,290
This may seem like a three real question to you and maybe even roll your eyes a little.

3
00:00:19,470 --> 00:00:22,290
You've probably used least thousands of times.

4
00:00:22,560 --> 00:00:29,520
Nevertheless, I think it's worth taking a while to understand how this work exactly and what is going

5
00:00:29,520 --> 00:00:30,870
on under the hood.

6
00:00:31,350 --> 00:00:35,730
Wrist of T is a strongly type generic collection of objects.

7
00:00:36,150 --> 00:00:41,370
These are dynamic, which means we can add or remove the elements from them.

8
00:00:46,380 --> 00:00:52,020
We can access list elements using an index are just like we do with an array.

9
00:00:57,650 --> 00:01:03,880
This provoked a wide selection of built in methods which make them much more convenient than planned,

10
00:01:04,040 --> 00:01:04,340
right?

11
00:01:05,180 --> 00:01:08,600
Let me show you some, but certainly not all of them.

12
00:01:11,020 --> 00:01:17,110
Because of the dynamic nature of lists and their convenience, they are probably the most often used

13
00:01:17,110 --> 00:01:18,940
collection type in C-sharp.

14
00:01:19,360 --> 00:01:21,940
Let's take a look under the hood of the list.

15
00:01:23,920 --> 00:01:31,900
It turns out that the list is actually a fancy wrapper over an array, and all the list data is held

16
00:01:31,900 --> 00:01:33,100
in a private area.

17
00:01:33,430 --> 00:01:36,490
We can see it here in the least glass source code.

18
00:01:37,760 --> 00:01:40,730
Least exposed is a property called capacity.

19
00:01:41,090 --> 00:01:46,520
This property says what is the size of this private area held by the East?

20
00:01:46,790 --> 00:01:48,350
Let's see this in practice.

21
00:01:59,530 --> 00:02:02,080
Let's see what will be presented to the council.

22
00:02:04,200 --> 00:02:05,340
That's interesting.

23
00:02:05,760 --> 00:02:13,470
After a new list is created, its internal process is zero done after an element is added.

24
00:02:13,680 --> 00:02:16,020
The south is changed to four.

25
00:02:16,500 --> 00:02:22,620
I don't literally mean changing because as we learned in the previous lecture, the size of an array

26
00:02:22,620 --> 00:02:23,520
can change.

27
00:02:23,910 --> 00:02:30,660
I will explain what happens here in a minute, but first, let's add a couple more of elements to exceed

28
00:02:30,720 --> 00:02:32,160
the four elements limit.

29
00:02:40,950 --> 00:02:47,640
It seems the South grew twice, it was four, but now it is eight before explaining.

30
00:02:47,740 --> 00:02:49,830
Let me just clear the East.

31
00:02:57,510 --> 00:03:04,080
Even if the list has been emptied, the capacity remained as it was, so it still holds an array of

32
00:03:04,080 --> 00:03:07,110
size eight as its internal data structure.

33
00:03:08,520 --> 00:03:09,170
All right.

34
00:03:09,480 --> 00:03:16,080
Let's see what's going on when we insert the first element to the list, it cautiously assumes that

35
00:03:16,080 --> 00:03:19,860
maybe the underlying aura does not need to be very large.

36
00:03:20,340 --> 00:03:25,490
It creates an aura of size four and assigns it to the private items field.

37
00:03:25,660 --> 00:03:28,470
Would we have seen in the snippet from the source code?

38
00:03:28,800 --> 00:03:35,370
This area is used as long as the count of elements in the list is smaller or equal to four.

39
00:03:35,670 --> 00:03:42,000
But what this count is accident ghosts can no longer fit elements in the underlying aura.

40
00:03:42,060 --> 00:03:43,530
It's simply too small.

41
00:03:43,980 --> 00:03:46,620
So what it needs to do is this.

42
00:03:46,890 --> 00:03:51,060
First, it creates a new arrow, double the size of the old one.

43
00:03:51,360 --> 00:03:55,630
Then it copies all elements from the old arrow to the new arrow.

44
00:03:55,980 --> 00:04:01,860
After that, it can add the new element that previously didn't fit into the smaller arrow.

45
00:04:02,400 --> 00:04:07,230
So as you can see, it's not like the size of the underlying arrow tenders.

46
00:04:07,560 --> 00:04:12,000
It does not, as it's not possible to resize an arrow in C-sharp.

47
00:04:12,780 --> 00:04:18,840
Brand new arrow is created under the old arrow is replaced by it on one hand.

48
00:04:19,080 --> 00:04:25,650
This is pretty clever, as it allows us to use our fixed size underlying collection to actually represent

49
00:04:25,650 --> 00:04:28,230
dynamic data, on the other hand.

50
00:04:28,290 --> 00:04:31,170
It's not great from the performance point of view.

51
00:04:31,380 --> 00:04:38,220
Once you resizing is needed, the least must perform this quite complex operation of allocating a new

52
00:04:38,230 --> 00:04:40,920
era and copying the old one into it.

53
00:04:41,430 --> 00:04:47,490
That's why it's quite generous when allocating a new arrow, and it makes it double the size of the

54
00:04:47,490 --> 00:04:48,060
old one.

55
00:04:48,510 --> 00:04:52,980
If the new arrow would be too small, it would soon need to be precise again.

56
00:04:53,250 --> 00:04:54,600
And we want to avoid that.

57
00:04:55,080 --> 00:05:00,780
On the other hand, of course, happen that more memory than we need is allocated.

58
00:05:00,990 --> 00:05:08,430
For example, if we exceeded the count of 2024 announced, the list will create a new array of size

59
00:05:08,520 --> 00:05:10,020
2048.

60
00:05:10,290 --> 00:05:18,360
But it may be the case that in our business, case 1025 is the absolute limitation above which the list

61
00:05:18,360 --> 00:05:19,410
will never grow.

62
00:05:19,710 --> 00:05:26,460
In this case, we can help the list a little and tell it what kind of elements it should be ready for

63
00:05:26,520 --> 00:05:28,830
by using the constructor parameter.

64
00:05:36,790 --> 00:05:43,390
We should definitely consider doing that if we know upfront what is the expected size of the list.

65
00:05:43,630 --> 00:05:49,960
Remember that it's not set in stone and once it's exceeded released, we resize as normal.

66
00:05:50,140 --> 00:05:56,260
But what we're doing is avoiding all the resizing operations that would normally happen between zero

67
00:05:56,260 --> 00:05:58,720
and 1050 almonds.

68
00:06:08,400 --> 00:06:14,370
Here I am generating a collection of 2000's numbers and adding it to the existing list.

69
00:06:15,860 --> 00:06:23,120
2000's Element didn't fit in, the 1050 elements are so the list needed to be resized.

70
00:06:23,300 --> 00:06:30,530
But it happened only once instead of a couple of times because the operation of resizing is so heavy,

71
00:06:30,830 --> 00:06:34,730
the list doesn't reduce its size once elements are removed.

72
00:06:34,910 --> 00:06:39,830
It rather wants to assume that the allocated space will be needed sooner or later.

73
00:06:39,920 --> 00:06:42,290
Since it has already been in need at once.

74
00:06:42,650 --> 00:06:49,490
If we had good reasons to think that the larger space needed was a one time thing, we can either accept

75
00:06:49,490 --> 00:06:54,530
the capacity to a smaller number manually or call the trim access method.

76
00:06:54,710 --> 00:06:58,730
Would you say that the capacity to the actual count of elements nearest?

77
00:07:09,850 --> 00:07:14,350
Here, I removed all elements from the list and then added only one.

78
00:07:14,710 --> 00:07:20,170
Then I called the trim access method, which would trim the capacity to the actual count of elements.

79
00:07:21,640 --> 00:07:25,240
And this is exactly what happened, and the capacity is now one.

80
00:07:26,620 --> 00:07:32,650
Remember that when setting the capacity manually, we can't make it smaller than the actual count of

81
00:07:32,650 --> 00:07:33,970
elements in the list.

82
00:07:34,150 --> 00:07:36,460
Otherwise, an exception will be thrown.

83
00:07:42,040 --> 00:07:47,620
This line will throw an exception because I have two elements in the list, and I'm trying to set the

84
00:07:47,620 --> 00:07:49,030
capacity to one.

85
00:07:50,940 --> 00:07:53,910
And to reduce the exemption, we expect it.

86
00:07:55,110 --> 00:07:55,810
All right.

87
00:07:55,980 --> 00:08:02,730
We now know how things work under the hood of the list and that in the end, all data is held in an

88
00:08:02,730 --> 00:08:03,000
hour.

89
00:08:03,510 --> 00:08:10,350
We must be aware that this has more implications than only resizing the array once its capacity is exceeded.

90
00:08:10,800 --> 00:08:12,840
Let's consider the following code.

91
00:08:21,800 --> 00:08:29,300
The insert method takes two parameters the index at which the new value will be placed in the list and

92
00:08:29,300 --> 00:08:32,120
the value to be inserted in this case.

93
00:08:32,210 --> 00:08:39,050
Four will be inserted at Index three, which is between values three and five innocent.

94
00:08:39,050 --> 00:08:45,530
As this operation seems, we must consider what happens with the array that is used underneath before

95
00:08:45,530 --> 00:08:46,940
the insert operation.

96
00:08:47,000 --> 00:08:48,780
The arrow looks like this.

97
00:08:49,550 --> 00:08:54,320
The capacity of the list is eight, which means it is also the length of the array.

98
00:08:54,680 --> 00:09:01,460
Please be aware that the last three elements are actually zeros, so the default for the integer type

99
00:09:01,460 --> 00:09:07,580
that is stored in this list, the least knows they are not the part of the represented data because

100
00:09:07,580 --> 00:09:09,610
it remembers the count of elements.

101
00:09:09,620 --> 00:09:17,480
It starts and knows that anything after index count minus one is not the actual data, but the cyberspace

102
00:09:17,480 --> 00:09:20,420
that can be occupied by some new values later.

103
00:09:20,810 --> 00:09:23,210
All right back to the insert method.

104
00:09:23,570 --> 00:09:29,330
We can't simply set the month at index free to value for because we would overwrite the value.

105
00:09:29,330 --> 00:09:29,900
Five.

106
00:09:30,350 --> 00:09:37,160
We must move all the months after the given index one index forward to make room for the new volume.

107
00:09:37,580 --> 00:09:40,250
This is again impacting the performance.

108
00:09:40,580 --> 00:09:46,310
Worst case, we may need to move each element in the least if we insert at index zero.

109
00:09:46,700 --> 00:09:51,050
This means the performance of this operation is so often.

110
00:09:51,650 --> 00:09:58,370
The insert method is just an example to show you that an operation that does something that the underlying

111
00:09:58,390 --> 00:10:00,020
error does not support.

112
00:10:00,200 --> 00:10:06,190
Like in this case, inserting the element in the middle of the data will always impact the performance

113
00:10:06,200 --> 00:10:09,020
as the data in the array must be rearranged.

114
00:10:09,290 --> 00:10:15,290
This is something to be aware of when working with lists, especially loved ones, as the performance

115
00:10:15,290 --> 00:10:17,000
impact might be noticeable.

116
00:10:17,600 --> 00:10:23,510
To summarize, lists are great when it comes to representing collections that are dynamic.

117
00:10:23,690 --> 00:10:28,670
They give us a lot of useful methods, like working with them simple and efficient.

118
00:10:28,970 --> 00:10:35,930
But we must be aware that adding a feature of dynamic size to the fixed size collection like error comes

119
00:10:35,930 --> 00:10:39,050
with a cost and this cost is performance.

120
00:10:39,800 --> 00:10:46,160
During the interview, you can be asked Why is it a good idea to set the capacity of the list in the

121
00:10:46,160 --> 00:10:47,030
constructor?

122
00:10:47,090 --> 00:10:54,020
If we know the expected count of the elements upfront, because this way will avoid the performance

123
00:10:54,020 --> 00:11:00,830
costly operation of copying the underlying array into a new, larger one, which happens when we exceed

124
00:11:00,830 --> 00:11:05,030
the count of four, eight, 16 and so on elements.

125
00:11:05,810 --> 00:11:09,860
What is the complexity of the insert metric from lowest class?

126
00:11:10,580 --> 00:11:13,210
The insert method needs to move forward.

127
00:11:13,250 --> 00:11:17,930
Some of the elements of the underlying array to make room for the new element.

128
00:11:18,260 --> 00:11:23,930
In the worst case scenario, when we insert an element at the beginning of the list, we'll need to

129
00:11:23,930 --> 00:11:26,000
move all existing elements.

130
00:11:26,330 --> 00:11:31,570
This means the complexity of this operation is, oh, often alright.

131
00:11:32,030 --> 00:11:36,600
We learned about one of the most useful collections inside for the list.

132
00:11:36,920 --> 00:11:40,370
Thanks for watching this video and see you in the next one.