Data Structures and Algorithms in JavaScript

# Implement a Linked List Solution

This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.

Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Implement a Linked List Solution" Lesson is part of the full, Data Structures and Algorithms in JavaScript course featured in this preview video. Here's what you'd learn in this lesson:

## Bianca walks through the solution to the Implement a Linked List exercise. The code for the solution is located on the "solutions" branch in the Github exercise repository.

Get Unlimited Access Now

Transcript from the "Implement a Linked List Solution" Lesson

[00:00:00]
>> Bianca Gandolfo: So here is our linked list constructor.
>> Bianca Gandolfo: I'm gonna pass in the value here.
>> Bianca Gandolfo: If, you don't pass anything we have a catch there saying don't do that.
>> Bianca Gandolfo: So,
>> Bianca Gandolfo: We're setting our head, right head value is gonna equal the value. And then the next is gonna be initialize to null.

[00:00:31] Cool, so we have two constructors here, we have our node constructor, and then we have our linked list constructor.
>> Bianca Gandolfo: Cool, and then we're setting our tail to head because when we start with a linked list of 1, the head is also the tail, cool? All right so this is a tricky one, so let's make a for each for our linked list.

[00:00:57] If we think about how we implement a foreach for an array, it has a few main components. Let me type this out for us, actually. How do I? There we go.
>> Bianca Gandolfo: So we have a few main components.
>> Bianca Gandolfo: But we're gonna implement this. So if we have maybe some loop, and we want to pass it some function, that takes the value, and I don't know console.logs to value, okay?

[00:01:38]
>> Bianca Gandolfo: myCall back.
>> Bianca Gandolfo: Yeah, cool.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: So if we're gonna implement our own foreach here.
>> Bianca Gandolfo: Right it's gonna take some call back. Let's pass the array to make it easier.
>> Bianca Gandolfo: And our call back. Is everyone following here?
>> Bianca Gandolfo: We would pass it, myArray, and then myCallback.

[00:02:28] Cool?
>> Bianca Gandolfo: So we're running in here. So now what we're gonna do, we're gonna write the guts of this foreach for an array. And then we're gonna think about how this is different using a linked list.
>> Bianca Gandolfo: So the first thing you probably wanna do is loop through our array and we're going to call our callback on each value.

[00:02:53] So the idea is for the first loop, you wanna pass 1, for the second loop, 2, and then, you guessed it, for the third one we're gonna pass 3. So at the end of the day, we want it to print out 1, 2, and 3, right? In that order.

[00:03:17]
>> Bianca Gandolfo: So we wanna write a for loop, right?
>> Bianca Gandolfo: That is the les than arr.length,
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: And now we wanna call our call back on each value of our array, right. So array at i, that's gonna be our value. When it's zero, the value itself is going to be one, etc.

[00:03:46] And this value is gonna get passed into our callback. So val is now one, and we'll just console.log val, we'll pop back out, loop again.
>> Bianca Gandolfo: This is gonna be two, meaning this is going to be 2, consolelog 2, and then we pop back out over here. Everyone clear how this works?

[00:04:11]
>> Bianca Gandolfo: Cuz it is a very basic implementation of foreach for an array. So what are the main components for a foreach function?
>> Speaker 2: Well a loop?
>> Bianca Gandolfo: Yeah.
>> Bianca Gandolfo: loop, and what else?
>> Speaker 2: Variables.
>> Bianca Gandolfo: Yeah, there's a couple variables in there. But what is an operation that needs to happen?

[00:04:44]
>> Speaker 2: Increment.
>> Bianca Gandolfo: What's that?
>> Speaker 2: Increment.
>> Bianca Gandolfo: Loop increment.
>> Speaker 3: Compare
>> Bianca Gandolfo: What is it?
>> Speaker 3: Compare, this is all in the loop signature here.
>> Bianca Gandolfo: Awesome. What else? There's one other thing happening here other than the loop itself.
>> Bianca Gandolfo: Hint, it is inside of a loop. [LAUGH]

[00:05:10]
>> Speaker 2: The action?
>> Bianca Gandolfo: Yeah, what's the action?
>> Speaker 2: Taking the callback on the-
>> Bianca Gandolfo: Yeah, so you wanna call the callback on,
>> Bianca Gandolfo: An item in the array. Cool? So we're all clear on what foreach does, how it would work with an array, right? So the main components here are gonna be the same for our linked lists.

[00:05:37] The main difference is how we loop through a linked list, since our linked list doesn't have numerical indices, right? That's why this for loop works, cuz we have numerical indices in our array. The for in loop works nice for objects because it's creative for an object. But we don't have like a native loop that's created for a linked list, right?

[00:06:02]
>> Bianca Gandolfo: So this is where we have to create our on loop. So we just roll out the for loop, the for in loop. What's another kinda loop I realize the answer's also on the screen, so you could easily cheat.
>> Speaker 2: I peeked, so I'm not gonna answer.
>> Bianca Gandolfo: Okay, how about someone who's been quiet today.

[00:06:24] How about Rosie? What's a different kinda loop?
>> Speaker 3: A while?
>> Bianca Gandolfo: For a loop, yeah, a wire loop, absolutely.
>> Bianca Gandolfo: And what are our conditions for our while loop?
>> Speaker 2: When I did it myself, I did a no .next is not equal to null, but I see that here, I'm used to C# and you can't do that in C#.

[00:06:56]
>> Bianca Gandolfo: Wild node?
>> Speaker 2: Yeah, so is that wild node translate to wild node is not null or is not undefined?
>> Bianca Gandolfo: Yeah, so what happens is this is gonna be forced into a boolean. If it's undefined, it's going to force into false, if it's defined it will be true.

[00:07:11]
>> Speaker 2: What about null?
>> Bianca Gandolfo: Null is also going to be false.
>> Speaker 2: Okay.
>> Bianca Gandolfo: Yeah.
>> Speaker 2: That's really cool.
>> Bianca Gandolfo: Yeah, so false values are gonna be undefined, null, 0, empty string, stuff like that.
>> Speaker 2: Awesome. Do we need to force? Would it be better well, node not equal to null?

[00:07:34]
>> Bianca Gandolfo: Well, this while node is not undefined.
>> Bianca Gandolfo: You're right, you're right it's null, yeah, yep. You could say that. while (node != null), but this is just a short hand, yeah. Cool, so while we have a node we're gonna do the callback. Passing the value, someone asked before if we should pass the entire node or the value.

[00:08:11] In general when we're doing operations on our data, we're gonna disregard some of the metadata, we're gonna do work on the actual value, right that's what we're interested in. The .next metadata that helps us organize our data and access it and things like that quickly. But, isn't what we wanna work on.

[00:08:36] Does that make sense? So in general you're gonna be working with the value itself, not the entire node.
>> Bianca Gandolfo: Cool, and then we set node to node.next. And as long as node.next is not null, it's gonna keep looping.
>> Bianca Gandolfo: And so that's a foreach.
>> Bianca Gandolfo: Cool, questions?
>> Bianca Gandolfo: Awesome.

[00:09:09]
>> Bianca Gandolfo: So here's our print, it's just gonna print out all the values. We're using our own foreach as well.
>> Bianca Gandolfo: So we're gonna store it into an auxiliary array. The reason we have to do that is cuz if you look in the internals of foreach, we're not returning anything.

[00:09:30] So, we have to push in an external variable.
>> Bianca Gandolfo: We're gonna look through, here's our callback. Our callback is just saying foreach value, push it to our result.
>> Bianca Gandolfo: And then you're going to return it at the end as joined.
>> Bianca Gandolfo: You might recognize this as kind of like a map, sort of, implementation.

[00:09:58]
>> Speaker 4: So, you've got, sorry, we've got one question from online from Tegan. And she's asking with this implementation, can you transform data?
>> Bianca Gandolfo: Can you transform data? Yes, you can transform your data with a for each, depending on what your callback is, right? So in your callback, you could say,

[00:10:22]
>> Bianca Gandolfo: Yeah, you're right. We need to have a reference to the node itself cuz we're only passing the value. If the value is an object, and you're changing a property on it, it will transform your data but if we're using primitive data types then it would just get lost.

[00:10:42]
>> Bianca Gandolfo: So yes and no. And traditionally in for each what you'd pass is not just the value, you're gonna pass to call back you're gonna pass the value, and also the entire collection. And so, in the more traditional implementation, then you could transform your data, even if it was a primitive data type, cuz you would have a reference to the actual node that you're working on.

[00:11:09]
>> Bianca Gandolfo: Cool, now I like how you guys are thinking into this, because these are all things that you need to think about when you're creating your data structures. Is specifics for your use case, right? So if you need to transform your data, absolutely, it's something to consider when you're creating an implementation, yeah.

[00:11:30]
>> Bianca Gandolfo: Awesome, okay.
>> Bianca Gandolfo: Anymore questions?
>> Bianca Gandolfo: All right.
>> Speaker 2: I had a question about print. So you made an array and then called join, that join I'm not familiar with that returns as string? Is that more for forment then concatonating the string as you go? Or is it just kind of- No, just for format.

[00:11:56] Okay [INAUDIBLE] Cuz this, if you think about it.
>> Bianca Gandolfo: Joining probably is just looping through the array and concatenating it, so you can either concatenate it as you go or do it after, it's still gonna be linear, yeah.
>> Speaker 2: Okay.
>> Bianca Gandolfo: Yeah.
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: Okay, so let's just do one more.

[00:12:27]
>> Bianca Gandolfo: All right, insert after.
>> Bianca Gandolfo: Great, so this takes a node and this takes a value. This is the current node and then you're gonna insert the value after, cool.
>> Bianca Gandolfo: So we saw a picture of this before but you wanna get a reference to the former next.

[00:12:49]
>> Bianca Gandolfo: So this is the old next, right? And this is gonna become the next for,
>> Bianca Gandolfo: This value that we're adding right?
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: So here is our new value, we're creating a node with it. So our current node in question, we're adding our new node to that one, and then our new node's .next is gonna point to the previous .next of our current node.

[00:13:28]
>> Bianca Gandolfo: Cool, and then also if it's the tail, you can reset the tail.
>> Speaker 2: Do you need the two temp variables? You do, okay. So I just did var new node equals new node on the value, and then new node.next, I set to no node.next.
>> Bianca Gandolfo: So, say that one more time, you did what?

[00:13:59]
>> Speaker 2: So var newNode = newNode, takes value.
>> Bianca Gandolfo: I see, like newNode like this.
>> Speaker 2: Yeah, and then newNode.next = node.next.
>> Speaker 2: Then node.next = newNode
>> Bianca Gandolfo: Yep. That's what I did.
>> Bianca Gandolfo: Totally.
>> [INAUDIBLE]
>> Bianca Gandolfo: Yep, great. What's the time complexity of this?
>> Speaker 2: Constant.
>> Bianca Gandolfo: Constant time.

[00:14:40]
>> Bianca Gandolfo: What's the time complexity of this if we didn't have a reference to this node but we only had the value of the node that we had to look up.
>> Speaker 2: Can be linear right, cuz we have to go through?
>> Bianca Gandolfo: Linear in the worst case because you'd have to loop through it, absolutely cool.

[00:14:57] So another thing I wanna show you, is that we also have, where are we going here.
>> Bianca Gandolfo: Some solutions for double linked list. If you wanna take a look at that as well, this is the same exercises but with a double linked list.
>> Bianca Gandolfo: Awesome, all right, any questions?

[00:15:24] Cuz we're gonna keep moving.
>> Bianca Gandolfo: No?
>> Speaker 2: So each node is an object? And does it have a name, like how do you refer to just one of the nodes?
>> Bianca Gandolfo: .next or .hen.
>> Speaker 2: Okay.
>> Bianca Gandolfo: Yeah, so you can save it into a variable if you want, and that would be saving a reference.

[00:15:48]
>> Speaker 2: Okay.
>> Bianca Gandolfo: But you're not gonna save a reference to every single node.
>> Speaker 2: Right, right.
>> Bianca Gandolfo: Except for in the .next of the previous node, right?