Four Semesters of Computer Science in 5 Hours Linked List

[00:00:00]
>> [MUSIC]

[00:00:03]
>> Brian: So linked lists with arrays, we just basically were thinking them that we were addressing individual spaces and memory. The way that a linked list works, where's my pen here, and I'll show you.
>> Brian: Okay, so say, I have a list right now, and I create the list and it has nothing in it, okay?

[00:00:30] And now I'm going to create a new one, or I'm gonna add a new element to my linked list. And it's gonna be value one, or a, let's do a. I'm gonna create a new node,
>> Brian: I have to draw. Okay, so I'm gonna create a new node.

[00:00:51]
>> Brian: Okay, and every node has two pieces to it, it has the value. So the value in this particular case is going to be a.
>> Brian: And this is called next right here,
>> Brian: Okay, and next just right now, it's gonna point at nothing because there is no next, right, like that is the end of the list.

[00:01:13] And then, the other thing is because this is the first element, this is also called the head.
>> Brian: Okay, so now I'm gonna create another node, cuz I'm gonna add b, so I create another node.
>> Brian: This is gonna be b, and it has a pointer that points at nothing, okay?

[00:01:38] Then I'm gonna create another node,
>> Brian: At c, right, and this, so on and so forth, right? So you have these nodes that just keep pointing at the next one, right? We're also gonna keep track of the tail. So the first item in the list and the last item in the list, we tend to point out, you don't always have to point at tail.

[00:02:01] However, it tends to be pretty useful when you're trying to do things like pop, right, because you can just pop things off. Or push, actually, in particular, push, it's very useful for. However, this ends up being kind of difficult because let's say, let's add one more on here.

[00:02:20]
>> Brian: So if I add one more, this is now d. And this tail no longer points at there. Data points at this, right? Let's say if I ask for element two, index number two of this, the third element in the array. Well, I don't actually know where it is in memory because I've given up that abstraction.

[00:02:41] Now what I have to do is I take the head, and I have to follow next, right? So, if I asked for index number, I asked for the third one. So if I'm asking for c in this particular case, I have to go, I grab the head, and I say okay, now I'm gonna loop over until I've gone three places, and then I know that's the one I'm looking for.

[00:02:59] So I'm gonna hop here, and then I'm gonna hop here, and then I know it's this one, right? Now as you might imagine, if I have a list of 10 million elements, I have to hop 10 million times to get towards the end, right? So that's why gets, in this particular case, are super duper expensive.

[00:03:19] Now you might ask yourself, this seems like a really dumb idea, right, like why would you want to do this? Well, there actually is a really good purpose to this, because now deletes are super cheap. Let's talk about why deletes are super cheap. So, let's say I wanna delete c here, so I ask for a delete.

[00:03:36] What I'm gonna do is, I'm gonna hop to this one, I find b, and then I'm just gonna change its next to just point over there. So all I have to do is change one pointer to point somewhere else and it's already out of the list. It doesn't matter that c is still point here or anything like that.

[00:03:51] I just stop referencing it, it gets garbage collected and it's gone.
>> Speaker 2: Don't you have to find c first?
>> Brian: You do have to find.
>> Speaker 2: I mean if you're leaving the last item on the list, you still gotta go through them all [INAUDIBLE].
>> Brian: You do but that is decidedly less expensive than trying to shift everything to memory.

[00:04:09] Because that's a really expensive operation. Doing a bunch of hops, it's annoying, like you have to go through a bunch of things, but it's really easy to just follow a pointer, right. That's a pretty cheap operation even if it's a lot of it.
>> Speaker 2: Doesn't that contradict what you said the weakness of this is, finding the item in the middle?

[00:04:29]
>> Brian: It certainly is, gets are [COUGH]. It does contradict it in the sense of it's not instant, right? It's not constant in terms of like an array list, you just go grab it and it's there, right? Deletes in a number of cells are just expensive operations, but shifting everything over memory is really expensive.

[00:04:50] Finding something and then changing the pointer is way less expensive. So it's still somewhat expensive, like there's still cost I guess is what I'm trying to get at. It's just lesser than trying to shift everything in memory. Does that answer your question?
>> Speaker 2: Yeah.
>> Brian: Cool, any other questions about linked lists?

[00:05:11] Conceptually does it make sense what's going on here? Okay, so let's talk about push. Push is really easy, especially if you're keeping track of tail, which by the way you don't have to, it's just a convenience. It just makes push super duper simple. Cuz at push you just grab the tail and you point the next at e, right?

[00:05:39] And that's it, right? Push becomes really easy. However, pop becomes a little bit less simple so you can do something, I've seen people keep track of the penultimate tail or the former tail or something like that. I've heard it's called bunch a of things, right? Cuz this is kind of a mess, let's get a new one here, so if I have,

[00:06:07]
>> Brian: a which points to b,
>> Brian: Which points to c.
>> Brian: Oop, good job.
>> Brian: Okay, so pop isn't quite so simple because with pop, basically you have to make the second to last item point at nothing. So you still have to go find to that and then just point at null, right?

[00:06:36] And not point at this. But that's the idea behind pop is you just point that at nothing and that's now the tail is this, right.
>> Brian: And then head is this.
>> Brian: So you have to keep track of head, because that's how you keep track of the whole list.

[00:06:59] Right, that's you just have to keep track of the head. The tail is optional if you wanna make push super easy. We start introducing these special pointers right, like the head, the tail, the second to last tail whatever you wanna call that. It just makes a little bit tougher because you have to provide for Edge cases now, right?

[00:07:19] So now when I delete something I have to move my tail point whereas if I'm not keeping track of tail, it doesn't have to matter, right? Or if I'm keeping track to the second to last tail, what happens if I call, cuz right now in this particular case, if I call it ptail, ptail would actually be the head, right?

[00:07:37] And now if I delete it and I have just a head, I have head and tail, which are both this one, right. And ptail, which is nothing because there's no second to last. Right, the second the last is a negative one, right, which doesn't make any sense. So all this to say, don't keep track of the second to last.

[00:07:54] I'm just gonna say right now, unless you're writing something that specifically is optimizing for a stack, for pushing pop, don't do it. It just makes things way too complicated.
>> Speaker 3: I got a question related to gets from Jan Heine. Does the linked list have old and forgets?
>> Brian: Yes it does.

[00:08:15] It definitely does. That is a good observation. And as Christian was pointing out, the big O cheat sheat is perfect for this kind of stuff.
>> Brian: So right now we're doing array lists, which is this one. And we're doing singly-linked lists. As you might imagine doubly-linked lists are things that point forward and backwards.

[00:08:46] Again, by introducing those backwards facing pointers, you now have to constantly worry about making sure that they point at the right thing, and it makes everything more complicated. However, if going backwards and forward on the list is important to you, then you might want to do that, so,

[00:09:04]
>> Brian: Good questions. Any other questions?
>> Brian: So which one is better? Inevitably people ask a question, and just it's a trade off right? I say it every like ten minutes in this course, everything's a trade off. So let's go ahead and dissect the delete down here. So let's say, let's call it an index 2, which is gonna be value c here.

[00:09:31] Grab the head which is a, okay loop through the next right, so you're gonna use a while loop that keeps going through until it finds the second index. And then you're gonna be also keeping track of what the previous item in the iteration was and you're just going to move b's pointer to d and that's it.

[00:09:54] And you're gonna make sure you document the length. And return the value of the deleted node, that's it, that's all you need to do for a delete. None of this collapsing business. Okay, so let's check out the exercise unless anyone has any questions about this, yeah.
>> Speaker 3: Rob is asking, the cheat sheet indicates that delete is O of 1, does that mean that's wrong, which one is right?

[00:10:25]
>> Brian: The actual deletion itself once you have a hold of the node is constant, right, because you're just moving a pointer from one thing to another, right. But you have to do the find, and I think that's what they're getting at.
>> Brian: The reason why array is O,N, right, is cuz you have to shift everything over.

[00:10:47] Whereas with single linked list as soon as you have the thing that you need to delete then all you have to do is point it at something else.
>> Brian: Right, so yeah, here we go. The access, right, so a delete is a combination of access and deletion or search.

[00:11:12] You can also say search and deletion. So I think that's more what they're getting at here.