Data Structures and Algorithms in JavaScript

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 "Pseudocoding a Linked List" 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 pseudocodes a Linked List. She creates a Node constructor for initializing Nodes. The Linked List constructor would instantiate Nodes for the head and tail. The Linked List object would also have methods for adding to the tail and removing nodes.

Get Unlimited Access Now

Transcript from the "Pseudocoding a Linked List" Lesson

[00:00:00]
>> Bianca Gandolfo: So let's start by getting into our pairs and just pseudocoding out our linked lists together. So the first thing we need to do would be write a constructor function.
>> off screen male: I don't know if I did it right, but what I did was the function takes just a node as a parameter, and then it sets this.head equal to node and this.tail equal to node.

[00:00:29]
>> off screen female: What happened?
>> Bianca Gandolfo: Sorry.
>> off screen male: Does it take the node as a parameter or just the data that we're storing?
>> Bianca Gandolfo: Depends on your implementation.
>> Bianca Gandolfo: Yeah, so what do you mean? So-
>> off screen male: Yes.
>> Bianca Gandolfo: Do you mean this is gonna take an actual node, which has the next property?

[00:00:54] Or is this gonna be the data, like 11.
>> off screen male: It doesn't really matter. It just takes the data cuz it doesn't have a child property yet.
>> Bianca Gandolfo: Cool.
>> off screen male: So on the actual linked list object, I created a head and a tail property and set both of those,

[00:01:21]
>> off screen male: Equal to the.
>> Bianca Gandolfo: Whoops, cool.
>> Bianca Gandolfo: Set to the value.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: So we're setting it to the value.
>> Bianca Gandolfo: There's one little thing that we need to do here.
>> Bianca Gandolfo: Anyone?
>> Bianca Gandolfo: Okay, we'll discover what it is, okay.
>> off screen male: Do we need to have a place for the reference to the next one?

[00:02:05]
>> Bianca Gandolfo: Mm-hm.
>> off screen male: But it's gonna be null, right?
>> Bianca Gandolfo: Mm-hm.
>> off screen male: Okay. [LAUGH] Yeah, I didn't add a child reference until the add to tail function. In the first pass through I set an undefined child element to the tail. But then I didn't see why I was doing it, so I removed that.

[00:02:31] And I just have, in the add to tail method, I set tail.child equal to the next value.
>> Bianca Gandolfo: Okay, that makes sense. So one thing that we can put in here is a node constructor.
>> Bianca Gandolfo: That's separate from our linked list constructor. And this can pass, we can say it's a new node and we can pass the value.

[00:02:54] And so, in our node constructor, this is where we wanna say this.value, this.next. We wanna set it to null, not undefined, because just the best practice to set things to null and let the computer set things to undefined, so that you know the programmer set it to null, not it just wasn't defined, and there's some error somewhere.

[00:03:22]
>> off screen male: Purposefully done?
>> Bianca Gandolfo: Yeah, exactly. Cool, so this.head, we probably wanna set it actually to the node.
>> Bianca Gandolfo: Cool?
>> Bianca Gandolfo: Awesome, so how do we add to the tail?
>> off screen male: In my implementation, I did just a function that takes a node or you could have it take a value and then use our node constructor again.

[00:04:00] And then all I did was set this.tail.childs, or what you're calling next, to the node.
>> Bianca Gandolfo: Set tail.
>> off screen male: Yeah, set tail.next.
>> Bianca Gandolfo: Tail's next to the value.
>> off screen male: To the node.
>> Bianca Gandolfo: Or to the node, yeah, to the node.
>> Bianca Gandolfo: So probably, you might wanna create a node from value.

[00:04:26]
>> off screen male: And then update the tail to be equal to the.
>> Bianca Gandolfo: Great, so we have some pointers, right? We have our head pointer and our tail pointer. And these make operations much faster in our linked list, right? Otherwise, we might have to traverse through the entire linked list.

[00:04:53] But if we have a pointer to the tail, that makes adding to the tail, what?
>> off screen male: Fast.
>> Bianca Gandolfo: Fast, constant time, great. What about removing a node?
>> off screen male: I wasn't super happy with this, but what I came up with was just again, taking a node as a parameter, and then setting a temporary variable I called parent equal to the head, or equal to this.head.

[00:05:26] And I did a while loop, while parent.next is not equal to the node and parent.next is not equal to null, set parent equal to parent.next. So it starts at the head and goes through each one till it finds the one that has the child we're looking for.
>> Bianca Gandolfo: Okay, so just so I can catch up with you typing.

[00:05:48] You were saying, so you set the parent to head.
>> off screen male: Yeah, and then while the parent's next is not equal-
>> Bianca Gandolfo: It's not null.
>> off screen male: And also not what we're looking for.
>> Bianca Gandolfo: Or node.
>> off screen male: Then just set parent equal to parent.next. Are we searching? Yeah, that's what I, I couldn't figure out how to get the head of the one we were looking for without starting at the beginning.

[00:06:24] So then once it exits this loop, it will have found the parent to our node. And so then it just sets that next equal to our node's next. So parent.next equals node.next outside the loop.
>> Bianca Gandolfo: Okay, so when found, set the parent.next to the child's next, right? Or the node in question's next, right?

[00:06:52]
>> off screen male: Yeah.
>> Bianca Gandolfo: Cool, all right. How do you feel?
>> off screen male: Yeah, I didn't like that we were starting at the beginning, but I couldn't think of a better way to do it.
>> Bianca Gandolfo: Yeah, does anyone have a better way of doing this?
>> off screen male: I thought that remove meant removing the child node of the current node.

[00:07:13]
>> Bianca Gandolfo: Yeah, so this one is removing any node in the list. If you want to remove the tail, right? That would be a constant time, we have a pointer to that. If we have a pointer to the parent, and that's what you're saying. Your implementation was you have a parent, and then you say you wanna remove the next node.

[00:07:35] Yeah, cool, awesome.
>> Bianca Gandolfo: Any questions?
>> off screen male: Is there a better way to do it than to start it?
>> Bianca Gandolfo: No, with your constraints and it being a singly linked list, you don't have a reference to the parent, you have to find it, yeah.
>> off screen male: So you're saying you really have to loop for this?

[00:08:10]
>> Bianca Gandolfo: Yeah, yeah.
>> Bianca Gandolfo: Cool.
>> off screen male: So is there a way to do it without the head and tail property on the linked list itself? Could you do it with just giving the nodes the links and not having an implementation of the linked list that stores the head and the tail?

[00:08:34]
>> Bianca Gandolfo: So the reason we have the head and tail is because it makes a lot of operations easier. So you can add to the tail in constant time, you can remove this tail in constant time, stuff like that. But you do need a reference to the head. Cuz otherwise, you wouldn't know where to start, yeah.

[00:08:54]
>> Bianca Gandolfo: Mm-hm.
>> Bianca Gandolfo: Yeah, and so, this remove method has a search in it. And that kind of exposes one of the things that makes a linked list slow is whenever you need to search versus an array, right? If we're comparing it to our arrays, or stacks and queues, well actually, stacks and queues are the same thing.

[00:09:17] But an array, if we wanna find,
>> Bianca Gandolfo: Something, it's just a constant time lookup. Yeah, all right, so are we ready to code this out and do some exercises with this?
>> Bianca Gandolfo: Is that a yes? Or do you have more questions?
>> Bianca Gandolfo: Okay, let me have one more question.

[00:09:46]
>> off screen male: What's the context in which you'd use this remove node method? So when are you calling it? Is it inside something else? I don't know. I'm trying to get some context because initially, we did an if statement. So basically, if there was no reference to another node, that means it's the tail.

[00:10:08] So we remove the previous object reference and then return the node. But otherwise, we just change the reference to the following object.
>> Bianca Gandolfo: So wait, sorry, you said that you're just doing remove from tail?
>> off screen male: Or if it's not the tail, if it has a reference already, if the previous one has a reference, then it's not.

[00:10:34] Okay, I just confused myself. The one we're removing, okay, so if the one we're removing has a reference to another one, that means it's not the tail. So we just remove the previous object's reference-
>> Bianca Gandolfo: So you have to find-
>> off screen male: Change that to the last one, to the following one.

[00:10:51]
>> Bianca Gandolfo: So there is no way in a singly linked list to go from the current one, backwards.
>> off screen male: Okay.
>> Bianca Gandolfo: Right, you can't do dot previous in this implementation.
>> off screen male: Could you do, well but you'd have to call it a parent.
>> Bianca Gandolfo: What do you mean?
>> off screen male: Never mind, I'm confusing myself the more I talk, so-

[00:11:12]
>> Bianca Gandolfo: No, I think you have a good point. Like, you could, if you had a link to the previous node, you could do that really easily. Right, because all you'd have to do is redirect the parent nodes next to the next next, which is the child's next, right.

[00:11:28]
>> off screen male: But you're saying there's no link there, so you don't know what it is.
>> Bianca Gandolfo: Right now there isn't, and that would be an optimization, right, is to add a previous, or P-R-E-V is usually what we say, to make a doubly linked list.
>> off screen male: Got it.
>> Bianca Gandolfo: Yeah.

[00:11:42]
>> off screen male: Okay, that makes sense. Is that what it's called, a doubly linked list?
>> Bianca Gandolfo: Mm-hm, mm-hm, yep.