Arrays Data Structure

[00:00:00]
>> All right, so, shockingly we're gonna do our first data structure. We're gonna start off with the data structure first, not an algorithm. You've already seen this data structure many times in your life, is everyone excited? All right, we got lots of smiles. I think I saw one tear, it was just one tear.

[00:00:14]
All right, arrays, yes. I know we're gonna cover arrays first. You're probably saying well I know what arrays are well you also said that, that was an array which it's not an array so we're gonna do this. So I'm glad this joke worked out because it wouldn't have been funny if I didn't.

[00:00:29]
So if const array isn't an array well what is it? Well, hopefully by the end of this section, we will be able to derive what it is we will be able to empirically look at it and say, it's actually this data structure. JavaScript arrays are actually much more complicated in that they do a lot of cool tricks underneath the hood.

[00:00:45]
And I'm sure they morph algorithms depending on how you use them if you have an array that uses huge numbers. I am positive JavaScript's not like well, you did set one element at a billion. We're gonna create 999,999,999 positions before it and put that into memory. I'm very sure that they're very smart and so they're not quite the data structure we'll point out, they do a lot of things.

[00:01:09]
But I'm also positive they are this fundamental base if you use it as a array. All right, so let's jump with this I'm gonna go to the whiteboard. And then we're gonna go to node and we're gonna observe this. In the most fundamental kinda idea of an array here.

[00:01:21]
I'm gonna actually write this up here and then I'll save these and I'll put them on the website as well. An array. So, the most fundamental idea of an array, is that all it is a contiguous memory space. Contiguous meaning unbreaking memory space in which contains a certain amount of bytes.

[00:01:36]
Now, everything about a computer is just numbers. These are all zeros and they're all ones, right? That's all they are, is a bunch of these things. And how memory is interpreted is based on what you tell the compiler or whatever like how to interpret it. And so when it sees a chunk of memory.

[00:01:54]
And goes well, these four bytes I'm gonna treat them as a singular number, right. This is actually gonna be a 32 bit number that is what the compiler telling or that is gonna be your program just understanding this piece of memory in a very specific way. Just because it's contiguous, just because it's all one piece of memory doesn't mean that it has any specific meaning until you give it meaning.

[00:02:17]
So, an array is effectively is just a big, long version of this. Where you have zero or more pieces of memory that are understood as a single type in a row. So, imagine if you did so, in a more traditional language you could do something like this. I have an int array of three.

[00:02:33]
Meaning, I want three INTs in contiguous space, unbreakable like for me to be able to use. And so now you can walk that space by simply providing it's a we call this thing A. I think I went to the edge of my screen where I can't actually put anything in there.

[00:02:48]
Let's say we did that, there we go. And if you wanted to walk that, if you did A0. What you're really telling the computer to do is hey, go to the memory address of A. Then add in the offset of zero multiplied by how big my type is.

[00:03:03]
Cuz if your type is 32 bits or four bytes index one has to be four bytes into the array or into the memory space. And that's kind of what creates an actual array. And so for people to kinda see that and understand the fundamental operation, I think it's really good because it helps kinda put yourself into the mentality of a computer.

[00:03:23]
Cuz when you access these big long pieces of memory to you, it's very abstracted away. It's just like something that, it's like a slot. But underneath the hood, it's gonna be contiguous. It's gonna be just zeros and ones. And something has to understand that and make it into the type you think it is.

[00:03:39]
And so that's effectively all an array is a simple contiguous memory space. And so I wanted to just put that out there, just so it feels like we are talking about the exact same thing. And I can kind of actually show you that so I'm gonna jump into node for a second here.

[00:03:53]
And we're gonna create something called an array buffer. So no does have something like an array. So I can like this const a = new ArrayBuffer 6. So now when I type this out, you can see it's just a series of zeros. There we go. So I have this beautiful series of zeros and I wanna interpret those zeros in a specific way.

[00:04:15]
So I can go like this. a8 = a new Uint8Array. So I'm gonna take them as unsigned eight bit numbers. That means a number between 0 and 255. And I'm gonna pass in a. So now I have a view into this. And I can do something like this a8 0 = 45.

[00:04:37]
And so now when I print out A, you'll notice I've actually changed a piece of that data. When I do a simple. So let's go by 2, and I set 2. When I do it again, you'll notice that I set the first byte, skipped one, set the second byte.

[00:04:54]
It's kind of interesting, right. But now I can do something like this, const a16 = new UInt16Array. And now we'll print out the contents of the array. As you can see, nothing has changed if we use our new UN 16 array and set the second index, remember we use the width so this one should be further out.

[00:05:13]
This should be the last two bytes and set it to 4545 which is a pretty large number. So now when I print it out, you'll notice something. I specified the first one in decimal and we got a value of 2D, specified the second one in hexadecimal, got 4545.

[00:05:27]
But what you'll notice is that I said position two and look at where it set it. It set it on, what is it the fifth and sixth byte? Now that might be a bit confusing, but what I just did is I took a contiguous memory space and I interpreted it in two different ways.

[00:05:46]
I first said, look, I'm gonna look at this as eight bit units. And I can walk them in eight bit units. And I said, okay, let's look at them in 16 bit units and I can walk them 16 bits at a time. Very, very different and that's effectively what is going on underneath the hood.

[00:06:01]
This is fundamentally what an array is, I'm walking these positions. And I know this might be a bit confusing if you've never seen any of these things is very confusing. Most of the course isn't gonna deal with this. I just wanted to make sure that when I say array, this is more of what I'm referring to.

[00:06:16]
When I say list, I'm not referring to that. And I wanted to make it as abundantly clear as possible, so that way we have the same language together as we go forward. All right.
>> So you set a16 to 2, to that, and then now a got changed.

[00:06:38]
>> All right, so yeah, let me walk through for those that don't understand what happened. So an array buffer is a contiguous piece of memory you can create in JavaScript. Then you can create views into this data. So one view I created right here was an eight bit array.

[00:06:51]
That means every single time I increase the offset into it, it's gonna take the width of that type, which is eight bits, multiplied by the offset that I give it. And then edit or get that value. So when I say set position 0, it goes, okay, I'm array buffer A.

[00:07:08]
I'm gonna go offset times eight and grab that piece of memory. And then I do it again with two. Okay, I'm gonna do two, I'm gonna go over that amount 16 bits. And then I'm gonna grab from effectively the 17th through the 20 or the 16th through the 23rd bit.

[00:07:25]
I'm gonna grab that or a byte, prescribes the second byte, index that is, and grabs that out or sets that in. But then I create the exact same piece of memory A, but this time I set it as a 16 bit. So I completely change the value that I'm looking at, right.

[00:07:42]
Those are two very different values in fact if I were to store the same value due to my computer. What is something called endianness. When I store this value it will be a bit confusing when you look at it. Because of how computers interpret it look at where it put that 45.

[00:07:57]
It put it in the most significant position probably not where you thought it was gonna put it. But that's because I've now interpreted this memory space differently than eight bits I'm doing it as 16 bits endianness, we won't talk about endianness.
>> So when you set up that array, as that when you told us is this an array?

[00:08:19]
The reason it's not defined, because.
>> It's not that it's not defined, we will go over it. But there's operations that you can perform on an array that you cannot perform with the JavaScript capabilities and we'll see why. Well, mean, technically you can, but we'll go over that but effectively asking.

[00:08:35]
Is it because we didn't set anything on here when creating the array? No, that's not it, it's fundamentally not an array. In some sense it fundamentally down at the most basic unit is an array. But at the same time, it's not an array. And we can talk about why.

[00:08:50]
All right, so let's talk about some operations you can do. I've already pretty much covered everything about getting data at a specific index, right. It takes the width of the type multiplies it by the offset puts it at the memory addressing go in and grab that. Now that may not be exactly how things happen, but that's the simplest way to understand it when it comes to how arrays work.

[00:09:10]
So how does insertion at a specific index work with an array. Well, the thing is, is that with arrays there are no like magicalness. So when you insert something, it doesn't necessarily insert it, it overwrites it, right. So it's just gonna set that value. You do not get to grow your array into more memory.

[00:09:30]
Because what happened if right after that you have the user's name, right? So if you grow this what's gonna happen to poor Fred? Well, is that's F's in the chat for Fred, right? It is completely gone. And so we cannot grow an array just simply. That is why these data structures exist is because it makes life easier for you.

[00:09:52]
Because it would be really annoying if you constantly had to reallocate everything every time you wanted to grow it. That's why you'll notice things like capacity in a lot of other languages that aren't JavaScript. You'll see these kinda things because what they're doing is they're trying to make an optimized way for you to be able to use the memory without reallocations and all that.

[00:10:11]
Let's see, and so that's just an insertion, right. It just overwrites it and of course insertion again is you just go to A memory address if you will. You add in the width of the type which is usually specified in bytes. So it'd be like 32 bit integer would actually be four credit wouldn't be 32 bits multiplied by the offset.

[00:10:30]
And then we can write it in and deletion exact same thing. But deletion is kinda confusing. You don't delete something out of contiguous memory. I could set it to zero, right? That would be kinda deleting right there. It's how your program interprets it. And so if you're actually using raw arrays.

[00:10:49]
And you're actually doing something C and C. You have to be able to tell yourself when you've deleted this piece of memory. You can't just simply be like, it's not anything anymore. That's where null comes around, null, of course, being the zeroth value, just like hey, it's not something.

[00:11:05]
It's just a way a named way for us to understand that there's not something in this very something spot. And so deletion works the exact same way, get to the offset, set it to some sorta sentinel value zero usually being it. And there you go, you now have yourself deletion getting an inserting.

[00:11:21]
Now I did talk about this big O business. So let's talk about it. What is the big O, of being able to get a value out of an array? Now remember, this is our equation we run. So if our array is size three. Does getting at a specific index grow with respect to input?

[00:11:41]
If I give 7 as my index, if I give 100 as my index, does any of this change right here?
>> I'm seeing O of 1, O of 2 of n, constant time.
>> I love the fact that I just heard O of 2 of n. Thank you for the call back to the previous joke really appreciate that again pad may to event right.

[00:12:04]
No, what it is of course it's constant time. Because you'll notice that nothing in here goes over the entire array right. We don't have to walk to that position we know the width of our type, we know the offset, multiply them together, get to that position, read out the value.

[00:12:19]
That would be again same thing with insertions, same thing with deletion which deletions really we just did insertion, right? They're all O of 1 because they're all an instant operation in the sense that no matter how big the index is, we don't do anything extra. So that is a constant time.

[00:12:33]
I really wanted to highlight what constant time looks like. Because constant time can be a bit confusing the first time you see it. It doesn't mean we literally only do one thing. It just means we do a constant amount of things no matter what the input is it does not grow with input at all.

[00:12:51]
All right, there we go. Here we go just kinda just a bit of a summary right fixed size contiguous memory chunks. You cannot grow it, there is no insert at there's no push or pop. It doesn't mean you can't write all those things. And the data structures we're gonna create will actually use arrays underneath the hood often as ways to grow and all that they'll have to implement growing.

[00:13:17]
You'll have to implement pushing you'll have to implement popping inside of our algorithms, but for now that is an array.