1 00:00:00,490 --> 00:00:03,240 Regardless of the kind of data structure you work with, 2 00:00:03,240 --> 00:00:08,180 all data structures are expected to carry out four kinds of operations at minimum. 3 00:00:08,180 --> 00:00:12,020 We need to be able to access and read values stored in the structure. 4 00:00:12,020 --> 00:00:15,070 We need to be able to search for an arbitrary value. 5 00:00:15,070 --> 00:00:18,990 We also need to be able to inset a value at any point into the structure. 6 00:00:18,990 --> 00:00:22,255 And finally, we need to be able to delete structures. 7 00:00:22,255 --> 00:00:27,198 Let's look at how these operations are implemented on the array structure in some 8 00:00:27,198 --> 00:00:29,071 detail starting with Access. 9 00:00:29,071 --> 00:00:33,392 Elements in an array are identified using a value known as an Index. 10 00:00:33,392 --> 00:00:37,430 And we use this Index to access and read the value. 11 00:00:37,430 --> 00:00:41,350 Most programming languages follow a zero-based numbering system 12 00:00:41,350 --> 00:00:42,580 when it comes to arrays. 13 00:00:42,580 --> 00:00:47,290 And all this means is that the first index value is equal to zero, not 1. 14 00:00:47,290 --> 00:00:50,040 Generally speaking, when an array is declared, 15 00:00:50,040 --> 00:00:55,020 a base amount of contiguous memory is allocated as the array storage. 16 00:00:55,020 --> 00:00:58,370 Computers refer to memory through the use of an address. 17 00:00:58,370 --> 00:01:01,670 But instead of keeping a reference to all the memory allocated for 18 00:01:01,670 --> 00:01:06,540 an array, the array only has to store the address of the first location. 19 00:01:06,540 --> 00:01:11,779 Because the memory is contiguous, using the base address, the array can calculate 20 00:01:11,779 --> 00:01:16,671 the address of any value by using the index position of that value as an offset. 21 00:01:16,671 --> 00:01:18,989 If you want to be more specific, think of it this way. 22 00:01:18,989 --> 00:01:23,612 Let's say we want to create an array of integers, and then each integer takes up 23 00:01:23,612 --> 00:01:26,791 a certain amount of space in memory that we'll call M. 24 00:01:26,791 --> 00:01:30,664 Let's also assume that we know how many elements we're going to create. 25 00:01:30,664 --> 00:01:34,870 So the size of the array is some number of elements we'll call n. 26 00:01:34,870 --> 00:01:40,580 The total amount of space that we need to allocate is n times the space per item M. 27 00:01:40,580 --> 00:01:45,253 If the array keeps track of the location in memory where the first value is held, 28 00:01:45,253 --> 00:01:46,787 so let's label that M0, 29 00:01:46,787 --> 00:01:51,341 then it has all the information it needs to find any other element in the list. 30 00:01:51,341 --> 00:01:55,084 When accessing a value in an array, we use the index. 31 00:01:55,084 --> 00:01:58,952 So to get the first element in the list, we use the zero index. 32 00:01:58,952 --> 00:02:01,578 To get the second we use the index value 1, and so on. 33 00:02:01,578 --> 00:02:06,293 Given that the array knows how much storage is needed for each element, 34 00:02:06,293 --> 00:02:11,009 it can get the address of any element by starting off with the address for 35 00:02:11,009 --> 00:02:12,359 the first element. 36 00:02:12,359 --> 00:02:17,199 And adding to that,the index value times the amount of storage per element. 37 00:02:17,199 --> 00:02:21,474 For example, to access the second value, we can start with M0. 38 00:02:21,474 --> 00:02:24,523 And to that, add times M times the index value 1, 39 00:02:24,523 --> 00:02:28,390 giving us M1 as the location in memory for the second address. 40 00:02:28,390 --> 00:02:33,073 This is a very simplified model, but that's more or less how it works. 41 00:02:33,073 --> 00:02:39,775 This is only possible because we know that array memory is contiguous with no gaps. 42 00:02:39,775 --> 00:02:41,370 Let's switch over to some code. 43 00:02:41,370 --> 00:02:45,620 As I mentioned earlier, we're going to be using Python in this course. 44 00:02:45,620 --> 00:02:49,615 If you don't know how to code, or you're interested in this content but 45 00:02:49,615 --> 00:02:53,739 know a language other than Python, check the note section of this video for 46 00:02:53,739 --> 00:02:54,867 more information. 47 00:02:54,867 --> 00:02:58,653 While the code will be in Python, the concepts are universal. 48 00:02:58,653 --> 00:03:02,550 And more importantly, simple enough that you should have no issue following along 49 00:03:02,550 --> 00:03:05,105 in your favorite programming language. 50 00:03:05,105 --> 00:03:08,850 Now, to get started, click on the Launch Workspace button 51 00:03:08,850 --> 00:03:11,910 on the video page that you are watching right now. 52 00:03:11,910 --> 00:03:15,610 This should spin up an instance of a treehouse workspace, 53 00:03:15,610 --> 00:03:17,790 an in-browser coding environment. 54 00:03:17,790 --> 00:03:21,070 Right now, your workspace should be empty, and that's to be expected. 55 00:03:21,070 --> 00:03:22,757 So let's add a new file in here. 56 00:03:22,757 --> 00:03:25,026 Going to go to File > New File. 57 00:03:25,026 --> 00:03:30,228 And we'll call this arrays.py, py. 58 00:03:30,228 --> 00:03:33,112 Creating a list in Python is quite simple. 59 00:03:33,112 --> 00:03:35,137 So we'll call this new_list. 60 00:03:36,959 --> 00:03:40,486 We use a set of square brackets around a set of values to create a list. 61 00:03:40,486 --> 00:03:41,352 So 1. 62 00:03:41,352 --> 00:03:42,724 And we comma separate them. 63 00:03:42,724 --> 00:03:46,091 So space 2, and space 3. 64 00:03:46,091 --> 00:03:50,148 This allocates a base amount of memory for the array to use. 65 00:03:50,148 --> 00:03:53,468 Or when I say array in Python, know that I mean a list. 66 00:03:53,468 --> 00:03:57,699 Since this is Python, the values aren't stored in memory. 67 00:03:57,699 --> 00:04:02,772 Instead, the values 1, 2, and 3 are stored elsewhere in memory. 68 00:04:02,772 --> 00:04:07,240 And the array stores references to each of those objects. 69 00:04:07,240 --> 00:04:13,110 To access a value, we use a subscript along with an index value. 70 00:04:13,110 --> 00:04:16,070 So to get the first value, we use the index 0. 71 00:04:16,070 --> 00:04:18,720 And if we were to assign this to another variable, 72 00:04:18,720 --> 00:04:23,330 it would say result equal new_list. 73 00:04:23,330 --> 00:04:27,000 We write out new_list since this is the array that we're accessing the value from. 74 00:04:27,000 --> 00:04:30,540 And then, a subscript notation, which is a square bracket. 75 00:04:30,540 --> 00:04:32,370 And then the index value. 76 00:04:32,370 --> 00:04:37,850 As we saw, since the array has a reference to the base location in memory, 77 00:04:37,850 --> 00:04:42,200 the position of any element can be determined pretty easily. 78 00:04:42,200 --> 00:04:45,510 We don't have to iterate over the entire list. 79 00:04:45,510 --> 00:04:50,600 All we need to do is a simple calculation of an offset from the base memory 80 00:04:50,600 --> 00:04:54,300 since we're guaranteed that the memory is contiguous. 81 00:04:54,300 --> 00:05:00,890 For this reason, access is a constant time operation on an array or a Python list. 82 00:05:00,890 --> 00:05:05,140 This is also why an array crashes if you try to access a value 83 00:05:05,140 --> 00:05:09,440 using an index that is out of bounds of what the array stores. 84 00:05:09,440 --> 00:05:13,300 If you've used an array before, you've undoubtedly run into an error or 85 00:05:13,300 --> 00:05:17,870 a crash where you tried to access a value using an index that was larger than 86 00:05:17,870 --> 00:05:20,270 the number of elements in the array. 87 00:05:20,270 --> 00:05:23,689 Since the array calculates the memory address on the fly, 88 00:05:23,689 --> 00:05:27,733 when you access a value with an out of bounds index, as it's called, 89 00:05:27,733 --> 00:05:32,233 the memory address returned is not one that's part of the array structure. 90 00:05:32,233 --> 00:05:34,255 And therefore cannot be read by the array. 91 00:05:34,255 --> 00:05:37,980 In Python, this is represented by an index error. 92 00:05:37,980 --> 00:05:43,100 And we can make this happen by using an index we know our array won't contain. 93 00:05:43,100 --> 00:05:46,480 Now, I'm writing out my code here inside of a text editor, 94 00:05:46,480 --> 00:05:48,270 which obviously doesn't run the code. 95 00:05:48,270 --> 00:05:51,200 So let's drag up this console area here. 96 00:05:51,200 --> 00:05:55,710 And I'm going to write python to bring up the Python interpreter. 97 00:05:55,710 --> 00:05:58,270 And in here, we can do the same thing. 98 00:05:58,270 --> 00:06:00,950 So I can say new_list = (1, 2, 3). 99 00:06:00,950 --> 00:06:07,568 And now, this is an interpreter, so it's actually going to evaluate our code. 100 00:06:07,568 --> 00:06:09,389 All right, so now, we have a new list. 101 00:06:09,389 --> 00:06:13,390 If I type out new_list, it gets printed out into the console. 102 00:06:13,390 --> 00:06:18,444 Okay, I can also do new_list [0], and you'll see that I get the value 1, 103 00:06:18,444 --> 00:06:21,444 which is the value stored at the zeroth index. 104 00:06:21,444 --> 00:06:25,746 Now, to highlight that index error, we can do new_list. 105 00:06:25,746 --> 00:06:27,588 And inside the square brackets, 106 00:06:27,588 --> 00:06:31,380 we can provide an index that we know our array doesn't contain. 107 00:06:31,380 --> 00:06:33,310 So here I'll say index 10. 108 00:06:33,310 --> 00:06:39,230 And if I hit Enter, you'll see it say index error, list index out of range. 109 00:06:39,230 --> 00:06:42,800 And those are the basics of how we create and read values from an array. 110 00:06:42,800 --> 00:06:45,060 In the next video, let's take a look at searching.