Complete Intro to Computer Science

LinkedList Practice

Brian Holt

Brian Holt

SQLite Cloud
Complete Intro to Computer Science

Check out a free preview of the full Complete Intro to Computer Science course

The "LinkedList Practice" Lesson is part of the full, Complete Intro to Computer Science course featured in this preview video. Here's what you'd learn in this lesson:

Brian provides a short exercise to practice implementing an object with LinkedList and then live codes the solution. A student's question regarding the index -1 in _find(index) is also covered in this segment.


Transcript from the "LinkedList Practice" Lesson

>> All right, so the first thing on push that we're gonna do, we're gonna say const node equals new node with a value, right? We're gonna say this length plus plus. We're gonna say, if I don't have a head, this dot head, then we say this dot head equals node.

Otherwise, simply we'll just say this dot tail dot next equals node and this dot tail. Equals node, right? So, the idea here is no matter what. Whatever you're pushing on a list is definitely going to be the last item in the array, right. So this dot tale is always going to be assigned node, the the new node, no matter what.

If you're pushing in a new head, or sorry if you're pushing into an empty list. It's also going to be the head, otherwise. The tail dot next is gonna be the node, right? And then again here at the bottom, we're always going to assign the tail to be the new node.

Okay. Pop, we're just gonna do return this dot delete. This dot length minus 1, right? And then we'll cut up the delete here in just a second. For the find, we're just gonna say if index is greater than or equal to this dot length. Returned no, right? So if we try and find something that's out of bounds just return nothing.

Otherwise let current equals this dot head. Then we'll do a for loop here for let I equals zero. I Is less than or equal to index minus 1. And then I plus plus. And we're just going to say current equals current dot next. And we'll just kind of be looping through all those nodes until we arrive on the one that we want.

And then at the bottom will return current. So this is just gonna be an internal find sort of method here so that we can find nodes. We never wanna return nodes directly to the consumer of this linked list because they wouldn't know what to do with it right.

This is an internal data structure here. Forget. We're just gonna say const node equals this dot find index. And here we can say if there's no node here, then return for zero, if you wanna return undefined, otherwise return node dot value. So that's the get, pretty straightforward and then delete is where things tend to get a little bit more hairy.

So the first thing we wanna do is we wanna handle, if they try and delete the head. So if index triple equals zero, then we need to handle that specifically. So const head equals this dot head and we're gonna say if head, they want to say this dot head equals head dot next.

Otherwise, we're gonna say this dot head equals null because we need to handle it differently. If it's the only item in the array versus, it's just the head of a long list, right? That's what this is doing here. And then here underneath that, we'll just say this dot length.

Minus minus and return head dot value. So that handles it if we're trying to delete the head, otherwise we need to say const node equals this dot find index minus 1, right? So this is going to find the node previous to the one that we wanna delete. We're gonna say const excise as in the the node that we want to cut out is gonna be equal to node dot next, right?

Then we're going to say, if there's no excise. Then here we could throw an error or something like that, we can return void zero you can do whatever you want I returned null. Depends on what kind of semantics you want to assign to it. Then we're gonna say node dot next equals excise dot next.

I'm gonna say if there's node dot next. Then this dot tail is equal to node dot next. And this done link minus minus. And return excise dot value. Okay, so let's see if that passes our tests. And thus, was great. So again, this is kind of where link less fall down.

Is that anytime you wanna do a look up, you have to loop through everything to try and find the thing that you're looking for. Just not necessarily always ideal. But, this is where it's kind of really great as these deletes, despite the fact that this codes kind of like not fun to look at, it's constant time, right?

All you got to do is move the pointer from here to here. It's just pointing at a new node and we don't have to like shift our entire array over like we had to do with array list. Okay, so questions about linked lists.
>> So intersect question on line 48.

So why is there like a index minus one record less than or equal to index minus one because we can we give like a. [INAUDIBLE] Than index. Because that's what's correct [LAUGH] I mean we can look here.
>> Just thinking like what [INAUDIBLE] right? I less than index for [INAUDIBLE]

>> I think it's just because we need to find, that's the way that those nodes had been numbered. It's, I guess you could restructure it, so that the indexes would be different. Like what refers to which index refers to which node because it's all depends on what kind of semantic value assigned to it.

Yeah, that's, I think that's just that's the one that we'll find the correct one because we're just looping through all these current until we find the one that we're looking for.
>> I think what she's saying you can remove minus 1, if you remove less than or equal if you just make it less than.

>> Got you. I see what you're saying.
>> Totally.
>> Yeah, and the other question is in line 65, like a, we are making a head tool model, but we are not making the tail to [INAUDIBLE]
>> This is true. Yep. That would have been a bug.

So that's correct. Good call. As you can see, these tests are not exhaustive either. So I'm sure there's probably more bugs buried in here. Again, really what I'm going for is the core of it, what I really wanted you to see was this logic of how to find something in a linked list.

And this logic here of just moving the pointer around. Right? Again, the point of this course is not [INAUDIBLE] thank you for helping me find the bug. I think that's a good to show people. But more what I'm interested in, what you find here is what's the actual logic here.

Learn Straight from the Experts Who Shape the Modern Web

  • In-depth Courses
  • Industry Leading Experts
  • Learning Paths
  • Live Interactive Workshops
Get Unlimited Access Now