Introduction to Data Structures for Interviews Linked List Demo
Transcript from the "Linked List Demo" Lesson
>> Bianca Gandolfo: So we also have a fun visualization for our linked list.
>> Bianca Gandolfo: Such a cool website, whoever made this. So we can insert things to the head,
>> Bianca Gandolfo: And just create pointers. So you can see that these are pointed. It has a value. We have a pointer here to the head, and we also keep track of the tail, which will matter when you actually implement it.
[00:00:37] So if you're thinking about a linked listing code, you could think about it as some nested objects. Remember, when we're storing things in memory, the next is actually a pointer. But visually, it might help to think about it like this. So you see that we have a linked list.
[00:00:54] The very first thing in a linked list is the head. And if you pass a linked list around, it's often, this is your entry point, you can't enter in the middle, or anything like that. You have to start from the head, or you could have a reference to the tail.
[00:01:08] You can access the tail, but a linked list, a singly link list only points one direction. So you can't go backwards. So you start from the head, you go one direction, cuz the next points, you have two things you can look at, the value or the next. And so, the next points to the next value, which also has a value and a next, which points to its own value, and if it's the end, then it's null.
[00:01:36] So if we get to the tail, which is this object right here, we don't know what's behind it. There's no previous, right? If we did have a previous pointer, that pointed backwards, then we would have a doubly linked list, which is cool. So this is useful if you ever wanna start from the end, and traverse backwards.
[00:02:00] But often, you'll ask the interviewer, can I use a doubly linked list? Often the answer is no, because they want you to do something a little trickier than that. But you should also always ask, this shows that you're aware that linked list can be singly linked, or doubly linked, and we can look at that in the visualization, so this is a singly linked list.
[00:02:25] We start at the head, and we traverse down to find something. If we wanted to, let's see what the search does. So it's searching, see, this is such a cool thing, checking for file, it's not gonna find it, it's gonna return false. And then, we could do a doubly linked list.
[00:02:49] Which you can see, you can either start from the tail, and go backwards, or from the head. And all this is, is you have another property on your node. So each piece of your linked list, each of these circles, we call a node. That's a reference to the fact that a linked list is actually a graph.
[00:03:10] It's just like a pretty good type of graph, and we'll talk about graphs some more later. But, when we talk about graphs, we call an instance, like a little piece of that, a node. And so, this node has three things on it, right? The first property is the value, 64.
[00:03:28] The second thing is the next value, which is a pointer to this node, which is an object that has a value, 72. And then, it has a previous, a property that points to, what, on 64, if you were to guess, what do you think previous points to?
>> Speaker 2: 29.
>> Bianca Gandolfo: Could be the tail, could be null, yeah, yeah yeah, so again, these were just pointers, and if we change 72 here, and we change it to 73, nothing breaks. It still will work exactly the same, except that now, instead of 72, there'll be 73. The other thing is if you wanna change the pointer, you just reassign it to another node.
[00:04:22] If you wanted to break off this linked list into a separate linked list, that pointed somewhere else, so maybe like 83 right here, you would just change the next property of 72 to point to 83, or here.