Introduction to Data Structures for Interviews

# Linked List: Usage & Constructor

## Bianca Gandolfo

Thumbtack

### Check out a free preview of the full Introduction to Data Structures for Interviews course

The "Linked List: Usage & Constructor" Lesson is part of the full, Introduction to Data Structures for Interviews course featured in this preview video. Here's what you'd learn in this lesson:

Bianca defines the expected outcomes from the methods in the linked list data structure and implements the constructor() method.

Preview
Close

### Transcript from the "Linked List: Usage & Constructor" Lesson

[00:00:00]
>> Bianca Gandolfo: We are going to jump into live coding our LinkedList class. So I'm just gonna start like I did before and this is how I really would do it in the interview. So I would just initiate a new linked list. It looks like this linked list, let's see when we initiate it.

[00:00:19]
It's actually not taking a value, but that's interesting. Something to think about, should we initiate it by passing a value? Or should we initiate it empty and then have some insert method that does that logic to check if it's empty or not? So that's something to think about.

[00:00:37]
So I would probably just write a note to myself. Or I would ask my interviewer, how should I initiate this? With a value or empty? So let's say that we initiate it with a value. What would that look like? So with a value 1, so my whole linked list, we have our storage.

[00:00:59]
And we have that as an empty object. And then I need, I definitely need access to the head of my linked list. If we do initiate it, with a 1, then I need to make sure I have a node in here.
>> Bianca Gandolfo: Maybe I don't even need this.

[00:01:22]
Maybe I just need the head because we don't have a continuous block of a memory. We just have pointers to each one. So maybe our storage can really be our head. Let's play with that idea. What would that mean for our data storage? So, if we initiate it with a value, our head would just point to a node that has a value, 1, and then a property next, which we would initiate as null.

[00:01:47]
Because we don't have a next value yet. Okay, that seems reasonable. Okay, so that is, if I initiate it like this and then if I wanted to gain access to it, so my linked list would look like this. So maybe I want my head actually not to be a secret.

[00:02:08]
I want that to be accessible because I'm thinking next. So if I wanna insert a node, if I wanna insert it after something, I might wanna put a reference here maybe. So I might wanna put a reference to myList.head.
>> Speaker 2: The node is gonna be the value in the pointer.

[00:02:35]
>> Bianca Gandolfo: Yep, exactly. So and then I put some value here, I can have 2. So when I insert, I pass the head.
>> Bianca Gandolfo: And maybe I wanna add a value to it. But let me just double check what we have defined here, inserts a new value to the end.

[00:02:55]
That's interesting, so maybe we don't even need this right now. So this would just automatically insert at the end. So that makes me think, okay, how do I know what the end is? So I need to keep track of the tail. So in addition to the head, maybe I should have this tail thing at the beginning.

[00:03:15]
The head would also be the tail. So I would initialize it and it would look something like that. Now I'm pretty convinced that I don't need storage. Does anyone have an argument for why you wanna keep this storage object around? Okay, we'll just nuke it for now, and if we change our mind later, we can come back to that.

[00:03:32]
Seems like maybe we don't need it. Okay, so we initialize it as 1, it looks like this. We're gonna insert 2. Okay, so then, after we do that, we want it to look like, so the head would stay at 1. And then the tail would be 2. And then we'd also wanna make sure that the null points to this one, right?

[00:04:01]
So this is a pointer to this object.
>> Speaker 2: Are you referencing it by value?
>> Bianca Gandolfo: No, this is just me pretending that it's a pointer. I can't really draw a pointer, but you can imagine. I could put a copy of it here. But they're the same thing, they're not two different things.

[00:04:21]
So we could do it like that for now. Let's see, if me saying pointers by reference by value is confusing to you, I recommend watching a JavaScript fundamentals course on Frontend Masters that deals with passing by reference and passing by value. It will help you understand this concept.

[00:04:45]
However, it's a little bit out of the scope for today. But if that seems confusing, you could just check that out. I'm sure either my JavaScript fundamentals course or Kyle Simpson's mentions a little bit about that.
>> Bianca Gandolfo: Okay, okay, so we insert 2, and so now we have our head and we have our value.

[00:05:06]
And then if we insert 3, we want something a little similar.
>> Bianca Gandolfo: We wanna update
>> Bianca Gandolfo: The tail, we also need to update this, whoa, okay. So this is how I'm imagining this insert method will work. Okay, feeling pretty good about how I'm going about this. At this point, I would ask my interviewer, is this kind of what you had in mind?

[00:05:42]
Are there any edge cases that you want me to consider? In assumption, I started off that this was just a singly linked list. And the reason that is is because we have, we're not really being presented with a problem that a doubly linked list would solve. And a doubly linked list just means that you're taking more space.

[00:06:06]
So for every pointer, you're taking a space in memory. And so as your linked list grows, so there's a space that it takes, right? So it's like a linear amount of extra space. And if you don't need it, it doesn't seem like you need it right now. No need to preoptimize or add more space if you're not saving yourself any time for anything yet.

[00:06:34]
>> Bianca Gandolfo: Yeah, okay.
>> Bianca Gandolfo: All right, so let's start with the initialize, so we had a head that we passed in some value, actually, here.
>> Bianca Gandolfo: And so we could have the head.
>> Bianca Gandolfo: The value.
>> Bianca Gandolfo: And then next would be null.

[00:07:18]
So this is the same as saying value : value.
>> Bianca Gandolfo: And then we would also say this.tail = this.head. So we're setting up that point relationship. These two properties point to the same object and memory.
>> Speaker 2: Cuz that's we're just neutralizing it that way.
>> Bianca Gandolfo: Mm-hm, but if we did like this, these would be two separate objects.

[00:07:56]
So just be careful of that. We're initializing like that the interface that I decided on this that we would just initialize it with the value. You don't have to do that. The other option would be you would just set this with just be null. And then when you insert, you could add your first value.

[00:08:12]
And you could do a check that like if head is null, tail is null, then you can insert your first one and set the head, etc. So we're gonna and then insert a value. Well, let's check our constructor and make sure our constructor is behaving correctly.
>> Bianca Gandolfo: All right, what have we got going on?

[00:08:41]
Great, that looks like what I expected.
>> Bianca Gandolfo: And the core of my debugging strategy is just ahead of time, figuring out what I'm going to expect. Write my code out to meet that expectation. Test it, if for whatever reason it's not meeting the expectation. Then I kinda go backwards and try to figure out where I could have gone wrong.

[00:09:11]
So that's just how I go about it, and I think it's a good strategy.

### Learn Straight from the Experts Who Shape the Modern Web

• In-depth Courses