Introduction to Data Structures for Interviews Linked List Commentary
Transcript from the "Linked List Commentary" Lesson
>> Bianca Gandolfo: Okay so, if I was learning linked list for the first time and you wanted to give me some key advice, what would it be?
>> Speaker 2: Being able to reference your head and your tail as vital to your survival of the linked list?
>> Bianca Gandolfo: Yeah. Holding those references, super key.
>> Bianca Gandolfo: What else? What about when you iterate through it? What about iterating backwards?
>> Bianca Gandolfo: Can you do that?
>> Bianca Gandolfo: Why not?
>> Speaker 2: Only if it's a w.
>> Bianca Gandolfo: Only if it's a w.
>> Speaker 2: Then it's going back and forth.
>> Bianca Gandolfo: Yep, absolutely.
>> Bianca Gandolfo: Or you can't usually do it, at least.
>> Speaker 3: Yes, I have a question that I think maybe pertains to my misunderstanding of how memory actually works.
>> Bianca Gandolfo: Sure.
>> Speaker 3: But we said earlier on that linked list are often used to compose of their data structures.
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: But they seemed so much scarier and more complex than other data structures.
[00:01:02] I mean is there something like overhead for attaching these extra properties or is it just like yeah, for implementation it's actually memory clutch application is so different that it doesn't matter or it's the.
>> Bianca Gandolfo: So I'm hearing two things, I'm hearing that seems a lot more complicated than other data structures and also is it actually faster?
>> Speaker 3: Yeah, yeah.
>> Bianca Gandolfo: And so I think for the computer they don't care about complexity. They just care about in terms of what we think reasoning about something might be difficult for us, a computer doesn't care.
>> Bianca Gandolfo: The things that are complex are the things that are slow on a linked list.
[00:01:48] It really just,
>> Bianca Gandolfo: Basically, if you don't want to, if you're. If you are trying to operate on the ends of a data structure, either the beginning or the end, the linked list is gonna be fast for that. It's not gonna be the answer for everything. As you can see, if we're trying to remove a node without a reference to the previous node, we actually have to loop through it.
[00:02:20] However, if you have the reference to the previous node, you can delete the next node very easily in constant time. So these are details that kind of make or break the data structure. And so the fact that they're being implemented under the hood of other data structures. The people who are writing the spec for the language and the implementation of it are the ones who are deciding what's best for this.
[00:02:48] What technical remove method would we use if we are talking about collisions on a hash table. So I know that answers your question. Kind of hand wavy. But it really depends and you probably won't be necessarily like in an interview, you're not gonna sit down. They're not gonna sit down and like okay.
[00:03:14] Write a hash table from scratch, handle detections, use a linked list or handle collision, use a linked list to remediate that. That's probably not a question you're gonna get, but underneath the hood when you are creating an object. Maybe one of your keys does have a collision and underneath the hood, someone took the time to implement a linked list because that made sense for them.
[00:03:41] That is not the only way to handle collisions, it is just one example. I don't actually know what the job script implementation uses to handle collisions.