Array Basics5:40 with Pasan Premaratne
A common data structure built in to nearly every programming language is the array. In this video we explore some of the basics of arrays
Data Structure - A data structure is a collection of values and the format they are stored. Data structures model the relationships between the values in the collection as well as the operations applied on the data stored in the structure.
Contiguous Memory - Blocks of memory situated right beside each other with no gaps
For code and explanations in other programming languages, check the Instruction step following this video
A common data structure built into nearly every programming language is the array. 0:00 Arrays are a fundamental data structure, and 0:05 can be used to represent a collection of values. 0:07 But it is much more than that. 0:10 Arrays are also used as building blocks to create even more custom data types and 0:12 structures. 0:16 In fact in most programming languages, text is represented using the string type. 0:17 And under the hood, 0:22 strings are just a bunch of characters stored in a particular order in an array. 0:23 Before we go further and dig into arrays, what exactly is a data structure? 0:29 A data structure is a way of storing data when programming. 0:34 It's not just a collection of values and the format they are stored in, but 0:37 the relationship between the values in the collection, 0:42 as well as the operations applied on the data stored in the structure. 0:44 An array is one of very many data structures. 0:49 In general, an array is a data structure that stores a collection of values 0:52 where each value is referenced using an index or a key. 0:57 A common analogy for thinking about arrays is as a set of train cars. 1:01 Each car has a number, and these cars are ordered sequentially. 1:06 Inside each car, the array, or the train in this analogy stores some data. 1:10 While this is the general representation of an array, 1:14 it can differ slightly from one language to another. 1:18 But for the most part, all these fundamentals remain the same. 1:22 In a language like Swift or Java, arrays are homogeneous containers, 1:25 which means they can only contain values of the same type. 1:30 If you use an array to store integers in Java, it can only store integers. 1:34 In other languages, 1:39 arrays are heterogeneous structures that can store any kind of value. 1:40 In Python, for example, you can mix numbers and text with no issues. 1:45 Now regardless of this nuance, 1:49 the fundamental concept of an array is the index. 1:51 This index value is used for every operation on 1:55 the array from accessing values, to inserting, updating, and deleting. 1:58 In Python, the language we're going to be using for 2:03 this course is a tiny bit confusing. 2:05 The type that we generally refer to as an array in most languages is 2:09 best represented by the least type in Python. 2:13 Python does have a type called array as well, but it's something different. 2:17 So, we're not going to use it. 2:21 While Python calls it a list, when we use a list in this course, 2:22 we'll be talking about concepts that apply to arrays as well in other languages. 2:26 So definitely don't skip any of this. 2:31 There's one more thing. 2:33 In computer science, a list is actually a different data structure than an array and 2:34 in fact we're going to build a list later on in this course. 2:40 Generally though this structure is called a linked list as opposed to just list. 2:43 So hopefully the terminology isn't too confusing. 2:48 To properly understand how arrays work, 2:51 let's take a peek at how arrays are stored under the hood. 2:54 An array is a contiguous data structure. 2:58 This means that the array is stored in blocks of memory that are right beside 3:01 each other with no gaps. 3:05 The advantage of doing this is that retrieving values is very easy. 3:08 In a non-contiguous data structure, we're going to build one soon. 3:12 The structure stores a value, as well as a reference to where the next value is. 3:16 To retrieve that next value, the language has to follow that reference, 3:21 also called a pointer, to the next block of memory. 3:24 This adds some overhead, which as you will see, 3:28 increases the run time of common operations. 3:31 A second ago, I mentioned that depending on the language, 3:33 a race can either be homogeneous, containing the same type of value, or 3:37 heterogeneous, where any kind of value can be mixed. 3:41 This choice also affects the memory layout of the array. 3:44 For example, in a language like C, Swift, or Java, where arrays are homogeneous. 3:48 When an array is created, 3:53 since the kind of value is known to the language compiler, and 3:55 you can think of the compiler as the brains behind the language, it can choose 3:59 a contiguous block of memory that fits the arrays size and values created. 4:03 If the values were integers, assuming an integer took up space, 4:08 represented by one of these blocks, then for a five-item array, 4:12 the compiler can allocate five blocks of equally sized memory. 4:16 In Python, however, this not the case. 4:20 We can put any value in a Python list. 4:24 There's no restriction. 4:26 The way this works is a combination of contiguous memory, and the pointers or 4:28 references I mentioned earlier. 4:32 When we create a list in Python, 4:34 there is no information about what will go into that array, 4:36 which makes it hard to allocate contiguous memory of the same size. 4:40 There are several advantages to having contiguous memory. 4:45 Since the values are stored beside each other, 4:48 accessing the values happens in almost constant time. 4:51 So this is a characteristic we want to preserve. 4:54 The way Python gets around this is by allocating contiguous memory and 4:58 storing in it, not the value we want to store, but a reference or 5:02 a pointer to the value that's stored somewhere else in memory. 5:06 By doing this, it can allocate equally sized contiguous memory since regardless 5:10 of the value size, the size of the pointer to that value is always going to be equal. 5:15 This incurs an additional cost in that when a value is accessed, we need 5:20 to follow the pointer to the block of memory where the value is actually stored. 5:25 But Python has ways of dealing with these costs that are outside the scope of this 5:29 course. 5:33 Now that we know how an array stores its values, 5:34 let's look at common operations that we execute on an array. 5:37
You need to sign up for Treehouse in order to download course files.Sign up