Introduction to Data Structures for Interviews Linked List Introduction
Transcript from the "Linked List Introduction" Lesson
[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.
>> 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.
[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?
>> 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: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.
>> 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.