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

The "Link List Use Cases" 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 discusses use cases of linked lists including use in stack/queues, caching, and handling of hash table collisions. Answering a question from a student, Bianca shows what a doubly-linked list would look like in pseudocode.


Transcript from the "Link List Use Cases" Lesson

>> Bianca Gandolfo: A common example for a linked list in real life is the least recently used cache, which means that, it's used for recent searches, anything that says popular videos, things like that. That's a least recently used cache, which means that it's keeping track of, you have some amount of space allocated.

And as you add new searches, for example, you're adding into this data structure. Once you reach capacity, it needs to have an exit, right? This is just like classic caching kind of process, like you put everything in and then you have to have a way to take things out, and these are different strategies.

So the least recently used will take out the oldest one. So you could say, it's like a common one. And there's also a most recently used, which is D1, that was the newest one that will be exited, so we'll keep the older ones.
>> Bianca Gandolfo: So use a linked list for that.

Like I mentioned, hash tables, they're gonna use a linked list underneath the hood.
>> Bianca Gandolfo: Yeah, cool. Any questions? Yeah?
>> Speaker 2: So on the screen, that's a singly linked list?
>> Bianca Gandolfo: Yes.
>> Speaker 2: Right there, okay. Is it quick or easy to show us what a doubly linked list would look like?

>> Bianca Gandolfo: Yep.
>> Bianca Gandolfo: Definitely.
>> Bianca Gandolfo: So,
>> Bianca Gandolfo: So here's a singly linked lists. A doubly linked list. So each node looks something like this. So we have the value, right, in this case, 1. We have the next, that if some pointer,
>> Bianca Gandolfo: This is pseudo code, by the way.

This is not real valid JavaScript. And then, so this is a regular linked list. Every node has these two values or these two properties, a value and a next. The next points to the next object, which also follows this format. If we are gonna have a doubly linked list, we just have a previous that's also a pointer.

It will just point, so the one, the next points to the two, the previous often we just initialize as a no just like this tail's next is null, that means there's nothing there. We need to initialize null instead of undefined because we want other programmers to know that we explicitly set that versus undefined is set by your runtime.

>> Bianca Gandolfo: Cool, so this, so if we had this, then this previous would point to two, except we can't really draw that here, but this would point to this object.
>> Speaker 3: Why are you using the spread operator there?
>> Bianca Gandolfo: That's ellipsis, sorry.
>> Speaker 3: Okay.
>> Bianca Gandolfo: Yeah.
>> Bianca Gandolfo: Does that help any?

Any other questions?
>> Speaker 3: And the pointer is just basically just the next value, right?
>> Bianca Gandolfo: Yep, yep.
>> Speaker 3: It's not like a cryptic code. It is just like, hey, next value in this?
>> Bianca Gandolfo: Yeah.
>> Speaker 3: Structure is that?
>> Bianca Gandolfo: Well, it's actually the next node. So it points to an object.

It doesn't point to the value.
>> Speaker 3: Okay.
>> Bianca Gandolfo: Yeah. So that's because, so since it points to the object, if we change this value, it would still point to that node.
>> Speaker 3: If it doesn't match, so you can replace the value?
>> Bianca Gandolfo: Mm-hm, yeah, exactly.

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