Linked lists in Rust
today. We're gonna do this notorious problem of implementing a linked list using Rust. So for those of you know, the drama, linked lists are one of the classic things people show other people about Rust to basically say, hey Rust sucks, Don't learn Rust. Rust is terrible, death to Rust etcetera etcetera is even one of the most famous rust tutorials out there called Learning Rust. With way too many link lists to show how, you know, link lists forced you to have this in depth understanding of Rust memory model and all that. Well, I disagreed. So let's try to implement some link lists and see how bad it really is. The first things first. So just like we wouldn't see destruct in python, this would be like a class, right? Because a node in a linked linked list is basically you have a node that has some data and then points to another node, that one points to another node. And these nodes are all linked together. So it's a list of data held together by these nodes that point to each other. So we'll call it linked list down here. I have a vector. And you say I say 1st, 2nd, 3rd, because we're gonna turn the vector into a linked list and then try to print the things in it. Okay, So first you excuse me? So we have the current value. What type is that gonna be? Well that could be any type. I mean here's obviously numbers. We don't assume that they're gonna give us a vector of numbers, are we want our linked list to work with arbitrary generic data. Thing is since we're gonna copy the data and from a vector we do want to say that it implements the copy trait. That's how you do that, right? That's not how you do that do that and we will say that type T. And then we point to the next thing. Now here's where in normal language is you can say oh yeah this thing is a link clicks to write but this is actually a store like this truck when it makes its gonna store this much memory then they'll store another link list with that memory and so on so forth. We're gonna say hey that's actually a pointer to some data that's on the heat. So yeah it's boxed and this is also a link list with type of whatever type of this one is. So this is this means that we can't have this one be a number and the next one be a string. If one node has a data type, every other note has to have the same data type. Well that's it. The only thing I'm gonna add is that this is an auction. And the reason is that the last one will have a null pointer. Right. Well Russ doesn't support no pointers when you fuse boxes we could make it unsafe and use raw pointers but it's better to just say it's optional. It could be none or it could be a box that points to a valid dick piece of data on the heat. That's it. We've implemented link list. That's not so scary. Right? Doesn't seem so bad. Yeah. I think it seems rather simple. Or is it? Well first we need a way to turn this vector into a link list. So let's get that going. I'll make something called vector to L. L. For link list. And I just know this is also gonna take that uh generic type. So we'll say we are going to take V. Which is a vector. Actually we're gonna borrow the vector that we don't have to take ownership of the vector. They give us the vector of type T. Right? Because whatever type of this vector is that we're gonna make our link list out of. Mhm. And what are we gonna return? That's actually a good question. I don't know yet. We'll think of that later. For now. We can just say, hey we're gonna return a link list. Right? So we'll say let's create a link list value is gonna be whatever coming first in our vector V. And next will depend uh If we have if this is the last thing which is our base case. So we'll say like yeah V. Is empty then. Well I guess if there's one thing in it. Yeah there's only one thing in it. That's the thing we just added the value. That means there's not anything left to say none. There is no next. Right? And I think this has got this has to be box so good. And it's mad at me probably because I don't have an else. Oh no it actually is none because it's option it's either none or something boxed. Okay. None or else. Things really mad at me. Oh yeah because I'm returning a linked list. Just go ahead and say that we return a linked list. I'm very happy about that. Okay. And it's a linked list of type T. Where T. Is whatever they happen to have given us and this link this is saying hey I can only take things that are copy. So we need to add to this to like hey yeah this is only where it can copy to. Otherwise we return I think that might be of some other type that isn't copy able and that's that's unacceptable. Now I just want us to do an else who will say some need to return the box data. What is the box data? Well it's just gonna be vector L. L. On the rest of the vector. So yeah we'll call back to L. L. Okay See Why It's Mad because it takes one argument. So we want to give the rest of the vector. So we use a slice to say give it the rest. It's gonna be mad about the type when we pass a reference and we'll say to because this is a slice and we wanted to be a real vek beautiful. That's it. As far as I know that actually worked. Crazy. Huh? Um Mhm. And I think that if I were to change this to be a boxed option, this like option I do that. I mean I seem to have caused an error here. I haven't taken my coat in a long time. Okay. Yeah. I don't really know why but I'm not gonna think about it too deep because their code works okay. So Mhm. It's not a walk in the park but honestly this is still easier. Pretty much than doing it and see where you have all these like pointers running around and you're like, you know, de referencing them. Let's see if it's about to get worse definitely is. But we'll see. So I'll just say let l equal back to L. L let me pass it are back which is V. And mad at me because I'm supposed to pass it. Yeah let's try getting 1st, 2nd and 3rd 1st should be easy. Right? First is literally just L. L. Dot value. Yeah. I think whoops. First equal value might be an issue because I think it's gonna take ownership of L. L. Oh no, L L. Is just a link list. It's not boxed or anything like that. That should actually be fine. Okay. Okay. Okay let's see what we're gonna do next. Now we have to get 2nd 2nd equal L L our instinct is to do this right dot next up, that's what we were doing, python and say, hey, this is an option. So I need to unwrap it so we'll unwrap that value. That should be good to go now. We just need to get third, which will be L dot next dot. Unwrap got next. Unwrap valley. But it's mad at us because that's not a function. So use of moved value dot next. This is dot next. This is what we want. But we're moving in here so we could try this right. See if that makes it happy. It definitely won't. That's not happy, cannot move out of a shared reference. And let's see if it gives us any good hints. It says help, consider borrowing the options, content as ref. So I I I was trying still need to unwrap it. So it's basically saying I have this option like a pointer to an option. Let's try getting it as ref just following what Tyler says and all of a sudden, whoa, whoa, well, and behold our whole code is not giving us any little underlines which in rust means that it probably works. So let's give it a shot. Okay, it's taken about nine years to run. There you go. 1, 2, 3, that's it. So not trivial, but not really that bad. Maybe next time we'll try reversing a linked list that classic computer science interview question. But for now, I think that was pretty educational. We see a lot of stuff involving the way Rust thinks about memory and ownership, and some stuff that even for me isn't super familiar. I'm a Rust learner myself, so I gotta look into that stuff. But thank you a lot for your time and I'll see you soon. Bye bye.
The notoriously hard to implement data structure for Rust. Can we do it?
The notoriously hard to implement data structure for Rust. Can we do it?