Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,081 --> 00:00:01,081 (bright, uptempo music) 2 2 00:00:01,081 --> 00:00:02,521 (whooshing) 3 3 00:00:02,521 --> 00:00:03,524 (keyboard clacking) 4 4 00:00:03,524 --> 00:00:05,200 (mouse clicking) 5 5 00:00:05,200 --> 00:00:06,080 So, in this video, 6 6 00:00:06,080 --> 00:00:09,370 we're going to look at arrays as a data structure. 7 7 00:00:09,370 --> 00:00:11,730 So, the most important thing to understand 8 8 00:00:11,730 --> 00:00:14,430 about arrays is how they're stored in memory. 9 9 00:00:14,430 --> 00:00:16,260 And, essentially, they're stored 10 10 00:00:16,260 --> 00:00:19,340 as one contiguous block in memory. 11 11 00:00:19,340 --> 00:00:24,030 And what I mean by that is you don't have the items 12 12 00:00:24,030 --> 00:00:27,910 or elements in an array scattered throughout memory. 13 13 00:00:27,910 --> 00:00:31,110 All of the elements, items, whatever you want to call them, 14 14 00:00:31,110 --> 00:00:35,440 in an array, they're all stored as one contiguous block. 15 15 00:00:35,440 --> 00:00:40,230 So, let's say an array starts at memory address 100. 16 16 00:00:40,230 --> 00:00:42,780 That's a bogus memory address. 17 17 00:00:42,780 --> 00:00:44,640 You wouldn't have a memory address like that, 18 18 00:00:44,640 --> 00:00:46,480 but to keep things simple, let's pretend 19 19 00:00:46,480 --> 00:00:49,710 that we have an array that starts at memory address 100. 20 20 00:00:49,710 --> 00:00:53,710 And let's say that array is 200 bytes long. 21 21 00:00:53,710 --> 00:00:58,660 Well, then, what happens is, starting at memory address 100, 22 22 00:00:58,660 --> 00:01:03,270 the following 200 bytes are the contents of the array. 23 23 00:01:03,270 --> 00:01:06,680 So, the array is just one huge block 24 24 00:01:06,680 --> 00:01:08,620 and that's why we have to specify 25 25 00:01:08,620 --> 00:01:12,150 the length of the array when we create the array 26 26 00:01:12,150 --> 00:01:16,130 because that tells the JVM how much memory 27 27 00:01:16,130 --> 00:01:18,760 it has to allocate for that array. 28 28 00:01:18,760 --> 00:01:22,120 And it's one reason why arrays can't be resized, 29 29 00:01:22,120 --> 00:01:24,080 because, if they could be resized, 30 30 00:01:24,080 --> 00:01:26,220 then there'd be no guarantee after that 31 31 00:01:26,220 --> 00:01:28,990 that whatever, when we added extra space on, 32 32 00:01:28,990 --> 00:01:30,990 that that extra space would be in 33 33 00:01:30,990 --> 00:01:33,240 that same contiguous block of memory. 34 34 00:01:33,240 --> 00:01:35,790 So, arrays have a static length 35 35 00:01:35,790 --> 00:01:39,140 and when you create an array, 36 36 00:01:39,140 --> 00:01:42,470 there's one huge block of memory allocated for that array. 37 37 00:01:42,470 --> 00:01:44,130 So, the elements of an array are not 38 38 00:01:44,130 --> 00:01:46,260 scattered all over the place in memory. 39 39 00:01:46,260 --> 00:01:49,140 Now, the second important thing about arrays 40 40 00:01:49,140 --> 00:01:52,410 is every element in the array occupies 41 41 00:01:52,410 --> 00:01:54,770 the same amount of space in memory. 42 42 00:01:54,770 --> 00:01:57,680 For example, when we created our int array, 43 43 00:01:57,680 --> 00:02:01,420 every item that we put into that array will an integer, 44 44 00:02:01,420 --> 00:02:04,290 and in Java, an integer is four bytes, 45 45 00:02:04,290 --> 00:02:08,130 so every value in our int array 46 46 00:02:08,130 --> 00:02:10,640 was occupying four bytes in memory. 47 47 00:02:10,640 --> 00:02:14,470 You can't have an array element that occupies four bytes 48 48 00:02:14,470 --> 00:02:17,380 and then the second array element occupies 12 bytes 49 49 00:02:17,380 --> 00:02:20,640 and the third array element occupies 300 bytes. 50 50 00:02:20,640 --> 00:02:22,010 That doesn't work. 51 51 00:02:22,010 --> 00:02:24,900 Now, at this point, you might be thinking about objects 52 52 00:02:24,900 --> 00:02:26,260 and thinking, well, wait a minute, 53 53 00:02:26,260 --> 00:02:28,600 what if I create an array of strings? 54 54 00:02:28,600 --> 00:02:30,450 I mean the strings in the array 55 55 00:02:30,450 --> 00:02:32,830 could be of different lengths, so, you know, they're gonna 56 56 00:02:32,830 --> 00:02:34,740 be taking up different amounts of memory. 57 57 00:02:34,740 --> 00:02:36,410 What's important to understand when 58 58 00:02:36,410 --> 00:02:38,230 you're working with objects, 59 59 00:02:38,230 --> 00:02:40,610 not primitives like when you're working with ints, 60 60 00:02:40,610 --> 00:02:42,600 but when you're working with objects, 61 61 00:02:42,600 --> 00:02:47,180 what's stored in the variables is an object reference. 62 62 00:02:47,180 --> 00:02:50,240 So, when you create an array of objects, 63 63 00:02:50,240 --> 00:02:52,610 what's stored in the array elements 64 64 00:02:52,610 --> 00:02:55,280 is a reference to those objects. 65 65 00:02:55,280 --> 00:02:58,110 And object references are always the same size, 66 66 00:02:58,110 --> 00:03:01,640 regardless of the type of object they're referring to. 67 67 00:03:01,640 --> 00:03:04,070 So if you create an array of string 68 68 00:03:04,070 --> 00:03:06,530 what you're actually storing in the array 69 69 00:03:06,530 --> 00:03:10,800 is a bunch of object references to the string instances. 70 70 00:03:10,800 --> 00:03:13,860 And those object references are all gonna be the same size. 71 71 00:03:13,860 --> 00:03:16,450 And that's why you can have an object array 72 72 00:03:16,450 --> 00:03:18,830 and store any type of object in there. 73 73 00:03:18,830 --> 00:03:21,070 It's because the object references 74 74 00:03:21,070 --> 00:03:24,830 to the different instances are always the same size. 75 75 00:03:24,830 --> 00:03:28,930 So arrays occupy one contiguous block in memory 76 76 00:03:28,930 --> 00:03:31,270 and every element in the array 77 77 00:03:31,270 --> 00:03:34,090 occupies the same amount of space in memory. 78 78 00:03:34,090 --> 00:03:37,570 So, because of that, we can easily calculate 79 79 00:03:37,570 --> 00:03:41,740 the memory address of an array element based on its index. 80 80 00:03:41,740 --> 00:03:45,170 So, if an array starts at memory address x 81 81 00:03:45,170 --> 00:03:48,660 and the size of each element in the array is y, 82 82 00:03:48,660 --> 00:03:53,280 then we can calculate the memory address of the ith element, 83 83 00:03:53,280 --> 00:03:56,800 so array i, by using the following expression, 84 84 00:03:56,800 --> 00:03:59,840 x plus i times y, and we're gonna look 85 85 00:03:59,840 --> 00:04:01,860 at an example of this in couple of slides. 86 86 00:04:01,860 --> 00:04:04,870 So you'll see an illustration of this. 87 87 00:04:04,870 --> 00:04:06,930 So, basically, what that means is 88 88 00:04:06,930 --> 00:04:10,630 if we know the index of an element in the array, 89 89 00:04:10,630 --> 00:04:13,710 then the time or the number of steps 90 90 00:04:13,710 --> 00:04:16,510 we have to do to retrieve the element will be the same, 91 91 00:04:16,510 --> 00:04:18,710 no matter where it is in the array, 92 92 00:04:18,710 --> 00:04:20,220 because all we have to do to get 93 93 00:04:20,220 --> 00:04:25,020 the memory address of that element is x plus i times y, 94 94 00:04:25,020 --> 00:04:26,500 and that works whether we want 95 95 00:04:26,500 --> 00:04:28,490 the first element in the array 96 96 00:04:28,490 --> 00:04:31,140 or the 5,000th element in the array 97 97 00:04:31,140 --> 00:04:33,530 or the one millionth element in the array. 98 98 00:04:33,530 --> 00:04:37,220 All we ever have to do to get really quickly to that element 99 99 00:04:37,220 --> 00:04:41,590 is do that simple calculation to get the memory address. 100 100 00:04:41,590 --> 00:04:45,160 And this is made possible because of the first two points, 101 101 00:04:45,160 --> 00:04:49,060 because arrays are one large contiguous block in memory 102 102 00:04:49,060 --> 00:04:51,670 and because every element in the array 103 103 00:04:51,670 --> 00:04:54,340 occupies the same amount of space in memory. 104 104 00:04:54,340 --> 00:04:58,250 So, let's have a look at this for the array we just created. 105 105 00:04:58,250 --> 00:05:00,770 So, we created an array of length seven, 106 106 00:05:00,770 --> 00:05:04,530 so the value indices are zero to six 107 107 00:05:04,530 --> 00:05:08,228 and the values are 20, 35, minus 15, 108 108 00:05:08,228 --> 00:05:10,700 seven, 55, one and minus 22. 109 109 00:05:10,700 --> 00:05:12,730 Now, for this example, we're gonna pretend 110 110 00:05:12,730 --> 00:05:14,840 the start address of the array is 12. 111 111 00:05:14,840 --> 00:05:17,400 As I said, that's a bogus memory address. 112 112 00:05:17,400 --> 00:05:19,640 You know, it doesn't matter what the number is. 113 113 00:05:19,640 --> 00:05:21,560 And because these are integers, 114 114 00:05:21,560 --> 00:05:23,970 the element size is four bytes. 115 115 00:05:23,970 --> 00:05:28,630 So, if we wanted to get the element at array zero, 116 116 00:05:28,630 --> 00:05:31,450 well that's equal to the start address of the array, right, 117 117 00:05:31,450 --> 00:05:35,430 because the array starts here at 12 118 118 00:05:35,430 --> 00:05:37,940 and so the first element of the array 119 119 00:05:37,940 --> 00:05:40,380 is actually going to have the same address 120 120 00:05:40,380 --> 00:05:42,090 as the beginning of the array. 121 121 00:05:42,090 --> 00:05:46,910 So if we want the address of array zero, we get 12. 122 122 00:05:46,910 --> 00:05:51,290 If we want the 35, we need to jump past the 20 123 123 00:05:51,290 --> 00:05:55,440 and so, if we want array one, we're gonna start at 12 124 124 00:05:55,440 --> 00:05:58,410 and then we're gonna add four bytes 125 125 00:05:58,410 --> 00:06:00,650 because we know that the size 126 126 00:06:00,650 --> 00:06:03,310 of each of these elements is four bytes, 127 127 00:06:03,310 --> 00:06:06,040 and, so, if we want the second element in the array, 128 128 00:06:06,040 --> 00:06:08,830 we start at the memory address, which is 12, 129 129 00:06:08,830 --> 00:06:11,470 and we add four bytes, and now we're at 130 130 00:06:11,470 --> 00:06:13,610 the start address for the 35. 131 131 00:06:13,610 --> 00:06:17,750 So, that's 12 plus one times four equals 16 132 132 00:06:17,750 --> 00:06:21,170 and if we go back to our calculation here, 133 133 00:06:21,170 --> 00:06:24,300 that's the x plus i times y. 134 134 00:06:24,300 --> 00:06:27,540 So, x is the 12, i is the index, 135 135 00:06:27,540 --> 00:06:29,220 which in this case is one, 136 136 00:06:29,220 --> 00:06:31,030 and y is the size of each element 137 137 00:06:31,030 --> 00:06:32,420 in the array, which is four. 138 138 00:06:32,420 --> 00:06:34,640 So that's how we're doing this calculation. 139 139 00:06:34,640 --> 00:06:39,350 So, if we want minus 15, we've gotta jump over two elements, 140 140 00:06:39,350 --> 00:06:41,570 so we're gonna start at 12 141 141 00:06:41,570 --> 00:06:42,970 and this time we're gonna add 142 142 00:06:42,970 --> 00:06:45,660 two times four to it to get 20. 143 143 00:06:45,660 --> 00:06:47,490 So the 15 will start at 20. 144 144 00:06:47,490 --> 00:06:48,900 If we want to get to the seven, 145 145 00:06:48,900 --> 00:06:51,660 we've gotta jump over three elements to get to the seven, 146 146 00:06:51,660 --> 00:06:55,000 so that's gonna be 12 plus three times four 147 147 00:06:55,000 --> 00:06:57,550 and that'll give us 24 and so on. 148 148 00:06:57,550 --> 00:07:01,630 And this is possible because the array 149 149 00:07:01,630 --> 00:07:03,830 is one contiguous block in memory, 150 150 00:07:03,830 --> 00:07:08,200 so all the elements are stored in one block in order 151 151 00:07:08,200 --> 00:07:10,050 and also because every element 152 152 00:07:10,050 --> 00:07:11,840 occupies the same space in memory. 153 153 00:07:11,840 --> 00:07:15,540 If that wasn't true, if either of those two requirements 154 154 00:07:15,540 --> 00:07:17,730 weren't true, we would not be able to use 155 155 00:07:17,730 --> 00:07:20,070 this simple formula to quickly go 156 156 00:07:20,070 --> 00:07:21,700 to an element in the array. 157 157 00:07:21,700 --> 00:07:23,950 So, what this means is that, if we know 158 158 00:07:23,950 --> 00:07:27,520 the index of an element in the array, 159 159 00:07:27,520 --> 00:07:29,180 we can get to it really quickly, 160 160 00:07:29,180 --> 00:07:31,190 and it doesn't matter where it is in the array. 161 161 00:07:31,190 --> 00:07:34,850 I mean, if you look at array one versus array six, 162 162 00:07:34,850 --> 00:07:36,900 we're doing the same calculation 163 163 00:07:36,900 --> 00:07:39,510 and we're actually doing the calculation here as well. 164 164 00:07:39,510 --> 00:07:41,200 I didn't show it, but this is actually 165 165 00:07:41,200 --> 00:07:43,130 12 plus zero times four, 166 166 00:07:43,130 --> 00:07:45,550 which is 12 plus zero, which is 12. 167 167 00:07:45,550 --> 00:07:48,240 And now, maybe you can understand why 168 168 00:07:48,240 --> 00:07:50,760 array indices are zero based, 169 169 00:07:50,760 --> 00:07:52,450 because if they weren't zero based, 170 170 00:07:52,450 --> 00:07:56,240 if they started at one, we'd have to subtract one here 171 171 00:07:56,240 --> 00:08:00,350 because then we'd have 12 plus one times four, 172 172 00:08:00,350 --> 00:08:01,550 that would be wrong 'cause then 173 173 00:08:01,550 --> 00:08:03,330 we'd get 16 for the first one, 174 174 00:08:03,330 --> 00:08:05,350 so we'd have to always subtract one 175 175 00:08:05,350 --> 00:08:07,370 before we did the multiplication. 176 176 00:08:07,370 --> 00:08:11,070 Starting the indices at zero means we don't have to do that. 177 177 00:08:11,070 --> 00:08:14,150 So we can just substitute the array index in here. 178 178 00:08:14,150 --> 00:08:16,130 'Cause, remember, this is zero times four. 179 179 00:08:16,130 --> 00:08:18,490 I probably should have written that out, but I didn't. 180 180 00:08:18,490 --> 00:08:23,190 So, one of the things that arrays are really good at doing 181 181 00:08:23,190 --> 00:08:27,560 is retrieving elements if you know the index. 182 182 00:08:27,560 --> 00:08:31,330 So, if we know the index of the element we want, 183 183 00:08:31,330 --> 00:08:33,990 we can get to that element very quickly 184 184 00:08:33,990 --> 00:08:36,990 regardless of where the element is in the array. 185 185 00:08:36,990 --> 00:08:39,740 Okay, so and we understand how arrays 186 186 00:08:39,740 --> 00:08:41,140 are stored under the covers 187 187 00:08:41,140 --> 00:08:44,800 and we understand why, when we have an index of an array, 188 188 00:08:44,800 --> 00:08:47,680 we can get to the element really, really quickly. 189 189 00:08:47,680 --> 00:08:50,570 Doesn't matter where the element is in the array. 190 190 00:08:50,570 --> 00:08:52,550 We do the same calculation. 191 191 00:08:52,550 --> 00:08:54,700 So with that in mind, let's move on 192 192 00:08:54,700 --> 00:08:59,700 and look the Big O values for array operations. 193 193 00:09:00,160 --> 00:09:01,710 I'll see you in the next video. 17134