Transcript from the "Review: Linked Lists" Lesson
>> Bianca Gandolfo: What's a linked list?
>> Speaker 2: It's some objects that are linked together with a reference to the next one?
>> Bianca Gandolfo: Yeah, absolutely. So again, this is an ordered collection of nodes, not to be confused with a sorted. It's not necessarily sorted, it's just ordered, it has an order.
[00:00:16] Sequential access, which means you can only access it in a certain sequence. Great, usually starting from the head or the tail, if it's double linked list. And accessing the next one. Cool, and nodes contain the reference to the next node. That is a linked list. Cool, so here's our picture.
[00:00:42] We have a value here. And then, next to it, we have a pointer. So you can imagine this is an object.
>> Bianca Gandolfo: And this has a pointer to the next object. Here's another object pointer to the next object. Cool, deletion's pretty quick. We just re-direct our .next to the .next.next.
>> Bianca Gandolfo: Cool?
>> Bianca Gandolfo: All right, here we go. So we have our linked list, we give it a value. Note that this if statement is not really gonna cut it It's going to give us an error. You probably want to throw an error instead. So we're going to create a new node with the head value.
[00:01:30] When we create a new node it's going to have again the next and the value. The next is set to null. I recommend null instead of undefined. And then the head is also the tail. Also if we insert and delete with the reference to the node,
>> Bianca Gandolfo: It's constant time, the slide is wrong.
[00:01:51] If you don't have a reference to the node,
>> Bianca Gandolfo: You're gonna need to Search for it, right? Which at the worst case is linear time.
>> Bianca Gandolfo: Cool. Why is it linear time?
>> Speaker 2: Because you're not gonna loop across the whole thing, you're just gonna.
>> Speaker 2: Actually, I don't know.
[00:02:27] Because you just changing the reference, right? So it's just a.
>> Bianca Gandolfo: So if you have a reference then it will be constant time, right? Cuz your just changing the next. Or you need a reference to the parent if you're deleteing or inserting. But if we don't have a reference to the node, what do we have to do to find the node in question?
[00:02:57] Yes. So you would have to loop through our link list. Right, we loop through the link list for the while loop, we can't use the for loop in this case. And looping through any less is gonna be linear time, right? Because if we double that list it's gonna double our work.
[00:03:15] So we have to look at each one. In the worst case, right because there could be the case where the one that you're looking for is the head, right? In which case you're looking at one. Right, it's one operation. However we're not thinking about that. We're thinking about what's the worse case.
[00:03:29] The worse case is all the way at the end. So we would have to loop through the entire link list, cool.
>> Speaker 3: Question?
>> Bianca Gandolfo: Sure.
>> Speaker 3: What do you mean reference or result reference just picking up one. element from the middle, or just, it's not clear.
>> Bianca Gandolfo: Yeah, so your question is why can't you just pick one randomly in the middle and have a reference?
>> Speaker 3: With a reference and without reference just to be the example of some kind.
>> Bianca Gandolfo: Yeah, absolutely. So an insert or a delete with a reference means that you know what object you're going to be deleting, inserting after, right? So you have, you have that reference. Maybe it's saved in a variable somewhere.
[00:04:17] So if you're inserting for example after the tail, which is a very common operation for a linked list. Usually you're going to have a pointer to the tail. So you have a reference to that node. So if you wanted to add Something next to the tail. You would have to say this.tail.next equals the new value.
[00:04:39] And that's easy, right? Because that's just a constant time operation. We're good to go. For deletion we have to have a reference to the parent, right, or I'm sorry. So if we wanna delete somewhere after maybe the head. Like the one after the head, you can delete the second one.
[00:05:04] And that would be having a reference that just comes fo free. Otherwise you could somehow save references as you're building your linked list or whatever. You can have a reference however you wanna have them. Generally, it's just gonna be the head and tail. Otherwise, you're gonna have to search for the element in which you wanna insert after.
[00:05:26] So maybe you wanna insert the number 4 only after the number 5 and you have a linked list that's numbered 1 through 10. You have to go 1 and then 2 and then 3 and 4, I'm sorry. And then 5 and then you put 4 after which that doesn't make sense sequentially but you get what I mean, right?
[00:05:50] So you want to insert it after but you'd have to look through to get there. Because we don't, it's not an array where you can just do a quick look up with an index. Where you can say like link list, bracket 4, or something like that. That's not how it works.
[00:06:06] The only way you can access it is through the dot next unless you have it saved in a variable.
>> Bianca Gandolfo: Cool, good question. Awesome.
>> Bianca Gandolfo: Any more questions?
>> Bianca Gandolfo: No? How did linked lists land for you? What was confusing at first that Cleared up.
>> Speaker 2: But I mean, I didn't really know what a linked list was before.
>> Bianca Gandolfo: Mm-hm.
>> Speaker 2: Before this, so.
>> Bianca Gandolfo: What is your So just a concept of the linked list. Yeah.
>> Speaker 2: Yeah, for sure.
>> Bianca Gandolfo: Cool.
>> Speaker 2: And then at first, I though they would have references to the parent as well as the child. And I think you said that's actually that's a double link list.
>> Bianca Gandolfo: Yep. Yeah, and if you're interested in the solution for the double link list there's a solution that you can check out. Yeah, cool. So it can be singly linked or doubly linked. Cool. We are going to have multiple links. Length and it's called a skip list.
[00:07:33] You can look into that to see sort of a variation of a link list.
>> Speaker 2: I have sort of an insight question. So one thing, I mean, for the most part, this was pretty straightforward. But one thing I was confused about is what a node actually was. I wanted it to have a name and an identifier and so It seemed kind of complicated to me like overcomplicated.
[00:07:57] But then I was talking to a friend about it yesterday. And I'm interested in what you think about this is. But he said that the whole point is to be sort of agnostic about what a note is. And that's kind of the whole point of a link list.
[00:08:09] Would you agree with that or?
>> Bianca Gandolfo: Yeah.
>> Speaker 2: You don't really want to worry about exactly what each note is. It's just a matter of Connecting them.
>> Bianca Gandolfo: Yeah, yeah, exactly, yeah. The purpose of the linked list isn't necessarily, you want your data in any sort of list to be the same type, the same format.
[00:08:27] Ideally, right, if you're doing things the way you're supposed to do. But a linked, what is specifically in your linked list can vary. And your specific implementation is going to change. So the point is you should understand where the overall concept and then be able to fill in the blank for your use case.
[00:08:46] And a node can contain, as long as it has a dot next and some sort of value. The rest of it is kind of up to you, right? The value could be an object, right? That has a bunch of different values in it, right? That could be a possibility, yeah.
[00:09:03] And different variations of linked lists have different ways that they connect to their .next another dot next.
>> Speaker 2: The question I'm realizing may be off topic so you can just talk later. But I'm wondering at one point a linked list starts to become more of a database. I mean, if you start adding all of these links and references and things.
>> Bianca Gandolfo: Becomes a database?
>> Speaker 2: More like a- not a database, but you know what I mean?
>> Bianca Gandolfo: Well data structures underly databases, right? So.
>> Speaker 2: Okay, so it's just a simpler form of it.
>> Bianca Gandolfo: Yeah, yeah, yeah, cool.
>> Bianca Gandolfo: I like that. Yeah?
>> Speaker 3: The diagram that reads very clearly, and the diagram you show is very clear.
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: But putting the diagram to the code was some starting out, to start to code was hard for me.
>> Bianca Gandolfo: Yeah, so when you saw the diagram, it made sense. But then when you started to code, it was kinda difficult? Okay, yeah, but leap to code was tough, yeah.
[00:10:13] And with data structures, you'll find that once you did it once. Then you're familiar with the approach and it's easier, right? But getting from the concept to the actual implementation for the first time can be It could be hard on your brain. It's a good practice, right? Because you're not always gonna have some predefined data structure that I'm gonna tell you exactly how you should do it.
[00:10:38] You know what I mean? You're gonna need to be able to think like, okay, here's my use case. This is what I need to do. Here's some constraints. You know, what's the best way of doing this? And being able to reason through it on your own. But again, it is a leap and something that comes with practice, and that's why you're here, right?
[00:10:55] To get that practice. Because probably when you're thinking about your data, you're drawing it on a white board. You're not coding it out first, hopefully, you know? That would be kind of scary.