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

The "Linked List: Q&A" 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:

Taking questions from students, Bianca discusses considerations in the linked list when writing functions outside of the class, expectations for interview questions regarding linked lists, and more.

Preview
Close

Transcript from the "Linked List: Q&A" Lesson

[00:00:00]
>> Speaker 1: Why can't you just do this.tell.next = null and then set this.tell.next = 104, will that not-
>> Bianca Gandolfo: So for example if we look at this, the tails, next is null already.
>> Speaker 1: Okay.
>> Bianca Gandolfo: But in order to remove this one we need to remove this pointer, in order to get to that pointer we need to loop through it.

[00:00:35]
>> Speaker 1: Okay.
>> Bianca Gandolfo: There is a hack-ey way that you could also do it but I think it's bad practise, there's another way you could do it but this is the correct way of doing it.
>> Speaker 3: This might be the bad practise, but instead of closuring in current node to the while loop, I haven't even thought through this.

[00:00:56]
But it is possible to declare a function that takes in a parameter which would be the stack head, then recursively goes through and traverses down in?
>> Bianca Gandolfo: It's the same, that's the same.
>> Speaker 3: It would be the same function-
>> Bianca Gandolfo: Yeah, recursion is just a different way of looping through things.

[00:01:15]
So anytime you see a loop you could do it recursively but you are creating that extra space with the call stack, so you are just doing extra work for yourself.
>> Speaker 3: That is the big difference, the space complexity would be greater and there wouldn't be-
>> Bianca Gandolfo: Yeah, there are certain optimizations around recursion that Java Script sometimes has but in general,

[00:01:40]
>> Bianca Gandolfo: To an iterative solution, it's usually faster and easier to reason about, recursion can be hard to sort in your mind. You can only hold so many things in your mind at once and recursion forces to hold your maximum capacity. However, there are certain things when you get to a point where it's easier to use recursion but if you can see an iterative solution, just do the iterative solution.

[00:02:09]
Unless your interviewer is like, you can ask, do you want me to do this iteratively or recursively? But if you're just supposed to be looping through an array and you ask them to do it recursively, they might look at you funny, so think about that before you ask.

[00:02:23]
But if you're talking about a link list, it's a recursive structure, you could recurse through a link list, a reasonable thing to do.
>> Bianca Gandolfo: But you could just ask cuz that might be what they're getting at, the recursive solution.
>> Bianca Gandolfo: All right, so we're removing the tail. The other thing you can do, like if you wanna get constant time, you might delete.

[00:03:01]
You can do like a remove next where you pass in the previous node and it will just remove the next one. That's the constant time, easy thing to do, and you're just moving the pointer from previousnodes.next.
>> Bianca Gandolfo: So we could pass in the list, also previous node. Also note what I'm doing here, I'm writing a function outside of my class.

[00:03:36]
>> Bianca Gandolfo: When do I do that? A lot actually. In this case, there isn't really a real reason other than there's a bunch of garbage up there, I don't wanna clutter. But I would use it in the case where I think this function would be useful for a different data structure.

[00:03:55]
So if it's a formating type function or anything that's not necessary totally has to be tied to my class. I'll just make it outside and eventually I'll move it into its own file if this is part of the code base.
>> Speaker 1: But in an interview setting.
>> Bianca Gandolfo: Either, it depends, in an interview setting, they might say, write a function that takes a linked list and deletes the previous node, and deletes the next node.

[00:04:30]
And so in that case, they are passing the list and the previous node, right? And so, in this case, you would need to access the internals of the list, so you would need to,
>> Bianca Gandolfo: No, actually you don't but you could potentially if you needed to access the head or the tail.

[00:04:53]
But those are public anyway, so I guess it doesn't matter, we don't have an underscore storage or anything like that. So yeah, we could just pass it to a function, that's fine. And this is probably more likely what you're gonna see than say, implementing your link list from scratch.

[00:05:06]
It's gonna be like, here's a link list, by the way, this is what it's gonna look like. You're gonna have a next and then you're going to have a data or a value, and that's what you can expect the node to look like. And just assumes that all of the stuff underneath is how it works.

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