Introduction to Data Structures for Interviews Linked List Exercise
Transcript from the "Linked List Exercise" Lesson
>> Bianca Gandolfo: So the next one is a linked list, let's look at the different operations for a linked list.
>> Bianca Gandolfo: So here's our LinkedList class, again, we have a storage property. Again I can put an underscore there, to say that this is private, you shouldn't be interacting with it outside of this class.
[00:00:23] And just to clarify on that, since this is inside of the class, you can interact with the _storage. But when you instantiate,
>> Bianca Gandolfo: Like this,
>> Bianca Gandolfo: When you instantiate, you don't later access storage.
>> Bianca Gandolfo: Okay, but inside here is fine. So the expectation is eventually to do all of these.
[00:01:06] But initially, insertion, removal, and contains would be the main ones to work on. But being able to do all kinds of different things on a linked list is gonna help you on interviews. Because this is one of those ones where you don't use them in the day-to-day. And interviewers like to throw interesting,
>> Bianca Gandolfo: I don't know, interesting twists on this problem. So some things to think about insertion, is that it needs to be constant time. Removal can be constant time, if you have a reference to the node, or if you first need to search it, that's gonna be linear. So a contains is gonna be a linear-time operation, cuz you need to loop through all of the nodes.
[00:02:01] IsHead should be constant time, IsTail should be constant time. I'm going to write these two in the notes, when I am done.