Four Semesters of Computer Science in 5 Hours Exercise 7 Solution Part 1
This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Exercise 7 Solution Part 1" Lesson
>> Brian: Let's talk about linked lists now. So we had the no constructor done. We have the link list class kind of skeletoned out. Does anyone have any questions before we start delving in and writing the code for it? One of your unit tests is already passing. You're welcome.
[00:00:22] And we're just gonna go ahead and knock out the other ones. Now this is decidedly more code to get this to work correctly but it's complicated by the nature that we're creating and deleting a bunch of items on the fly. Okay, so let's go look at push first.
[00:00:40] So this is gonna help us be able to add things to the array. So first thing, if index,
>> Brian: Sorry index. Am I out of order again? I am out of order. That's why.
>> Brian: So let's get rid of this first of all.
>> Brian: Okay, so I'm gonna create a new node.
>> Brian: Value, okay, increment length, okay? And then the first thing going to ask is Is this the head, right? So if this dot head right? If I have nothing in here then this is the head and that's it. So you're gonna say this .head equals node and actually if you think about it, if it's the head, if it's going to be the new head it's also going to be the new tail, right?
[00:01:43] So you can just go ahead and say this.tail = this.head as well.
>> Brian: Else this.tail.next = node.
>> Brian: And, that's why I did this.tail = node, right? So you actually don't even need this up here, sorry. That's why. [COUGH] Because no matter what, whatever you're adding when you're doing push it's always gonna be the last, so that you're always gonna make sure that that goes down that code path.
>> Brian: Okay? Let's make sure I'm not telling lies. Okay so now we have two unit tests that are passing.
>> Brian: Any questions about push? Push is pretty simplified if you have, if you're keeping track a tao;. If not then you have to loop through to find that the tail and then push that on.
[00:02:41] Whatever works for you and you're gonna see what we do with pop here it's gonna be kind of ugly.
>> Brian: And,
>> Brian: So that's well yeah, we can do it this way. So to someone else's point earlier, you can implant delete first and then worry about pop.
>> Brian: Yeah let's just go ahead and do it that way.
[00:03:09] That's way better. So let's do find first because delete needs to use find.
>> Brian: So I'm gonnasay, let current = this.head, right? Yeah, just got to remember where I placed set, this.head, okay? That i = 0, then we're gonna do a while loop. So, while you have something in current.
[00:03:36] You're gonna say if (test), so, whatever function we passed in to be able to do test. So if (test(value, current.value, i, current)), I don't think I actually used current anywhere. We'll leave it in there.
>> Brian: So it's a bit of our function signature you choose to make up.
[00:04:06] I just happen to make up that we're going to pass in the value. We're gonna pass and so values one that we're looking for right? That's the one to get past and here current value is the value of whatever node I'm on looking at, right? I use the value of the iteration that we're on and current is just the node itself.
>> Brian: Okay, so, if test returns true that means I found whatever I'm looking for. So you just go ahead and return current.
>> Brian: Okay, otherwise current is assigned current.next. So if we arrive into this code path we short circuit return there and we found whatever we're looking for.
[00:04:53] Otherwise, we're gonna keep going until we find whatever we're looking for, right? Cuz current is going to be assigned current.next. And so when it goes around the loop again, then current is the next node, right? And so on and so forth until we find that we're looking for.
[00:05:07] Is that make sense? So we're just hopping from node to node until we find them we're looking for. So that's what's this is doing and then once current is undefined, right, well that's gonna be coerced into undefined it's going to break out of the loop. So, we're not gonna run into an infinite loop either,
>> Brian: Okay? And then, we also need I plus plus down here as well. And then, if we break out of this loop that means we didn't find what we're actually looking for, we're just gonna return null to signify that. I didn't get what I was looking for, right?
[00:05:40] There's nothing in this list that contains what you asked me for. Okay?
>> Brian: We already did test and test index so those are already done for us. So now that we have find, let's go ahead and do get first. So we're gonna do get(index). And we're gonna say const node = this,_find(index) and then we're gonna use the test indexed function, so testIndex, and then if we don't have a node, yeah, so if(!node) return null.
>> Brian: Yeah, but we have to do it that way. Otherwise return node.value.
>> Brian: Okay? So first of all, let me make sure that I'm not.
>> Brian: Or does it stop and not test the other ones? Get.
>> Brian: That's not good.
>> Brian: Index, this.testIndex. Test index search underscore underscore.
>> Brian: Okay, let's debug why this isn't working. So we're getting, this is not working. So we got undefined which is not good.
>> Brian: So get(index). So, here we can just say console.log. What is index? Make sure they were getting the right thing.
>> Brian: That seems like it's working.
>> Brian: I wonder if I'm, cuz I'm not seeing that console.log.
>> Brian: I wonder if it's expecting pop to work first.
>> Brian: Let's just go and try and see what happens if we move this. Come on.
>> Brian: So I'm just moving the unit test underneath the other one. See that makes any difference.
[00:08:27] No it's not. So something is definitely broken here.
>> Speaker 2: Get test to uses pop.
>> Brian: Does it?
>> Brian: Yep, that's what definitely would do it. Okay, so let's go ahead and implement pop first. This is what you get for making things up on the fly.
>> Brian: Well and then let's do delete first because we're gonna make
>> Brian: I have two gets. Why is that a thing?
>> Brian: See that'll still fail right? Okay, so now it's failing for the right reason which is because I'm using pop and it's not working correctly.