Linked List Introduction

[00:00:00]
>> Bianca Gandolfo: So this is an interesting one, it's a little bit different than our contiguous block data structures. It doesn't really have a one-to-one mental model from this data structure to what we actually think about while we're coding in JavaScript. But it is important, because like I mentioned, it is an example of how pointers can be used creatively.

[00:00:32]
And this is very important in languages that don't have dynamic arrays. So JavaScript, all of our arrays are dynamic, which means that we don't need to set the size, it just changes. Linked list is pretty much how you implement a dynamic array. So if you were going to traverse or loop from 5 to 10 to 20, if this was a contiguous block of memory, this would be index 0, this would be index 1, this would be index 2, right?

[00:01:03]
That's how we would loop through it just with numbers, really. For a link list, the way we would loop is we would say the next one, the next one. So this is a property called next that points to another object. And so this is important because when we think about assigning values to an object, we are really just pointing to an object.

[00:01:35]
That object is not living in memory inside that variable, that variable has a pointer to that object. If you assign another variable, that pointer is now pointing to that same object, but there's only one object. And so that's what we say by reference, cuz we're referring to that object.

[00:01:56]
So you could have a bunch of different variable names, or you could pass it into a function, but it's all the same object. However, and that's not true for primitive types like strings or numbers, right? If you say x equals 1 and b equals 2, or x equals 1 and b equals 1, those are two different things, and it's actually stored differently in memory.

[00:02:26]
And so if I change x to 2, b is still 1, right, everyone would expect that? However, if x is pointing to an object and b is pointing to an object, and we changed that object, the internals of that object, both of them will be changed.
>> Bianca Gandolfo: Someone asked me a question about that, yeah.

[00:02:51]
>> Student: [COUGH] Is that because inheritance of that, or is that just?
>> Bianca Gandolfo: That's because of the way we store data in memory. So inheritance is different because, well so the interesting thing about your question is that inheritance, like prototypal inheritance works because of this concept of by reference.

[00:03:16]
So inheritance, we're all sharing objects, right, we're sharing the same object. If you're not careful you can change this object, and you could have consequences somewhere else. And that's something to think about when you're mutating your data, like in your life, right? If you're changing your object, it's gonna be changed everywhere.

[00:03:40]
And this is the classic problem of if this widget needs this object, and this widget needs this object, but this has this value, you don't want this one to change. But you update this one, and that one updates also, that can be a problem.
>> Student2: This is what people talk about when they talk about shallow copies and deep copies in JavaScript, right?

[00:04:00]
Where in order to, no?
>> Bianca Gandolfo: No.
>> Student2: This is not what, okay.
>> Bianca Gandolfo: No, so a shallow copy just means that, so if you have a nested data structure, a shallow copy will only copy the top level. It won't copy the children if it's nested, so that's a shallow copy.

[00:04:20]
A deep copy will loop through into all of the children recursively. And if you use a r flag in the terminal, that's a recursive, that means it will go through all of them. Similarly with copying, same idea, except-
>> Student3: And nested lists, right?
>> Bianca Gandolfo: What?
>> Student3: Nested lists, is that what you're talking about?

[00:04:44]
>> Bianca Gandolfo: Yes, exactly, exactly.
>> Bianca Gandolfo: Okay, so back to the linked list thing. So linked lists, another sequential data structure. It's important to note what's sequential and what's not. Because that will prepresent constraints for what you can use it for, what you can't use it for. So the size is dynamic, and that's really powerful in some environments.

[00:05:15]
In a JavaScript environment, we already have that for free, which is nice. But in other languages, you might have to think about that actively. We can do quick deletions from the middle. Just like that unshift example with the queue that I was talking about before. Where if you remove something from the front, you would then need to move all of the indices over.

[00:05:42]
The same thing could happen if you deleted a node in the middle of an array, everything on the back would need to be shifted over. And so with a linked list, we don't need to worry about that. Because we would just move the pointer to something else, and it doesn't affect it, mm-hm.

[00:05:58]
>> Student: [COUGH] Isn't it true you still have to traverse the list to get there?
>> Bianca Gandolfo: Yeah so that's-
>> Student: You know what I mean, so that takes time.
>> Bianca Gandolfo: So the find for a link list is much slower. But if you have a reference to the node that you wanna delete, or even just the node before it or something, then it's constant.

[00:06:20]
But yeah, the searching part is gonna be slower, and that's one of the cons. Is if you're looking for a particular value, that can take a while. Versus an array, we can go directly to an index, if you're looking up a key. If you're looking up a value, right, you still need to loop through everything.

[00:06:43]
Unless is sorted, in which case there are other ways we could go about it.