A Singly Linked List in Rust

all right welcome everybody to another rust stream today is going to be a little bit different than we've done in past weeks today we're going to be talking uh about a data structure and specifically talking about linked lists um the reason that i wanted to do this is because still after many many years when people are coming especially from cnc plus background they often ask you know or they often attempt to do a linked list as their kind of first thing that they do with rust and it's a horrible idea link lists and rusts are not necessarily difficult but certainly more difficult than they are and see and it's i wouldn't say a very beginner-friendly exercise it's more of kind of an intermediate um or like late beginner exercise um and and so people often get frustrated with that um not realizing that hey rust isn't c and c plus plus it's a different language and so things that are easy in one language might be hard and another and vice versa and so what we are going to be uh working on is looking at linked lists and specifically a singly linked list uh today because doubly lengths are are actually i wouldn't say hard but are really like you require kind of intermediate or high intermediate understanding of us to get right we're going to be looking at singly linked lists today because um it does give you a good impression of um you know what's what how rust works and and we will touch on a lot of uh interesting topics in the language um all right so without further ado uh let's go over to the screen real quick so um what we're gonna be looking at today um kind of the the i think the uh the real kind of gold standard when it comes to understanding like lists is the learned rust with entirely too many linked lists a mini book that i believe was originally written by gankra back in the day but i think is is now kind of uh maintained by the rust project itself um and you know uh i'm glad that you're watching this but if you really if you prefer reading things then this is a really great resource and i definitely recommend you take a look here at this um real quick my my chat has been has been lost all right there we go um so this is a really great resource to take a look at um and you can follow along uh using this and of course uh today we're only going to be talking about singly linked lists because i i only want to do about an hour of streaming today and i don't think we'll have time to get beyond that but if uh if people like this and let me know and we can continue using this resource as a as a as a as a guide to learning about rust through uh linked lists the thing to say about linked lists uh as well is um not only are they like not super trivial to implement uh n rust um but they're also generally a bad idea um and one great thing about this resource here is that it goes into uh an obligatory public service announcement um about why link lists are generally a bad idea um and so you can you can read about here you know why you should use a linked list and it and it's usually um often times for you know very esoteric reasons um and so um in rust when you're asking yourself if you want to use a what kind of collection you want to use um you basically should not reach for a linked list unless you are absolutely sure that that's what you need um and and you know maybe you actually do need a linked list but you should no reason why you shouldn't just grab for it because that's kind of the the standard um there is a linked list in the russ standard library so if you need a doubly linked list for entrant uh for uh for instance um the the standard collections linked list um is probably one that you want to reach for before you kind of start writing your own um but uh i'll be perfectly honest with you i've i've literally never used this i've used basically every other collection in the center library multiple times for many different projects and i've never used the linked list collection i'm sure there are plenty of people out there that use standard collections like lists all the time but i'm just saying i've been writing rust for for quite a while now and i i never use this um the the go-to uh collection and rust if you're just starting out um if you need kind of a um just a a normal collection is vec um and so most the rest code you'll see will kind of default to vec unless there is some other reason to use it and of course if you need a hash map there's hashmap but there and then there's kind of other i would say other collections that are specialized versions of of that can hash map and and and hash set i guess although hash said you can you can just use a hash map for that as well um all right so enough talking about uh the standard collections and stuff like that we're gonna start writing um a linked list and uh chat let me know if you have any questions because i hope to make this a little bit interactive so that we can kind of um get ahead of myself get ahead of ourselves and and hopefully go down some like not right paths so that we end up making common mistakes and and um talk a little bit about why those are our mistakes all right so i'm going to go over here and just do cargo new linked list as a project and it's going to be a lib project and we'll just open up a linked list here nvs code and wow that's big and get started here let me know hopefully everybody can see this fairly well i'm just gonna make it a tiny bit bigger here we can make this smaller for now all right um and one second here cool so looks like it's uh it's visible for everybody so the first thing that um you know normally what you would do when you have a linked list of some sort is is think about okay that that linked list can can either be um let's go ahead and get rid of the uh i will leave that for a second we'll leave the test for a second um so we'll just think about uh our our linked list like this as being either it's an empty list um or it's a you know a non-empty list or um we can do non-empty here um and it's it's pointing to to some other thing right um and so uh you know really we could think of it as like a node in our list and the node is either empty it doesn't have anything inside of it um or it's not empty and it has you know something inside of it the the value that we're keeping in our list like you know let's just say for now it's a a u32 of some sort um and then maybe it's pointing off to um you know to it has another it's pointing to another node um and so you know you might be tempted to write something like this um and uh this is the first problem that that people often run into um when when writing link lists and rust um where we have a recursive type here so node is either empty or it's not empty and if it's not empty then it kind of contains a node and of course that means that you can like recursively have as many non-empty nodes in this thing as you want and everything in rust is is stack allocated um so when we create a node um like down here in our test let's go ahead and create a node here um you know we want to we want to like russ will kind of look and see okay how much space does this thing take up on the stack and then i can you know i will generate code that takes up that much that much room on the stack um and so you know if i write node is not empty okay and node is not empty uh sorry node is not empty and it has you know one in here let's say and then node is not empty um and it's going to keep on going for forever and ever and ever um and it might end up being you know infinitely large all right it potentially can be infinitely large we don't know um how big a node actually is of course when we're creating a node here we'll know how big it is but if we have a function that takes you know my funk here that takes a node um sorry not none a note here how much how much room in memory how much room on the stack does this node take we don't actually know um because it can be you know it can be five nodes deep it could be a million nodes deep we don't know and rust doesn't play well with that rust has to know for for stack allocated things how much room it's actually taking up okay and so the first thing and i think if you go ahead and actually run this it will give you this this you know has been written so many times that they've actually built in a compiler um error message here that that um you know gives away what uh what's happening here and says you know node has a recur as a recursive type and it has an infinite size we don't you know we don't know how big it is it can be infinitely big um and it's recursive without indirection um meaning that we we it's okay to have a recursive data structure where it's where it's infinitely big or as big as memory can hold or whatever but we have to we can't do that on the stack itself we have to kind of um do it indirectly by by having this thing live you know having having a pointer to somewhere else so that the the note itself is always a certain size um and we it's telling us here to insert some indirection here through a box or an rc or an amp you know just a plane reference or something like that to make node representable to to ensure that that node has a um a like a finite and well-known size that node is always the same size in memory so we can go ahead and do that here by wrapping it in box here and so now um you know we have uh we have an actual linked list here in a way right we have um a node it can be empty and if it's or it can be non-empty and if it's non-empty then it has um you know an element and and we're kind of hard-coding it to u32 here and along with that it has a pointer to the next thing in line um and that next thing in line can be empty it can be the kind of the end of the list here or it can be non-empty um and and it will contain a u32 and the next thing in line and so this this really is kind of the minimal um the the minimal thing that we need in order to implement uh a linked list here um and so you know it's not the most usable right um in the world um so we probably want to build some abstraction around this and there are other problems with it as well that we'll talk about in just a minute but this is kind of the minimal that we that we need in order to to build up our linked list and uh if you're if you're confused um about the the infinite size thing um chad of course you can let me know right here but if you're watching this later on and you're confused about it just remember that rust always needs to know if you have a value of a given type that value should always be the same size and memory and the only way that we can get that to work is by inserting this in direction here because a box node is always going to be the same size it's going to be a pointer because that's what box is it's a heap allocated owned pointer here so we know how big this variant is here it's a u32 which is four bytes big um and it's a pointer which on my machine is you know i'm a 64-bit machine here uh this is uh uh eight bytes big then so we know that this on at least on my machine on my architecture is going to be 12 bytes big all right cool let me know if uh if there's any questions here if we look back at um at learning uh rust through too many linked lists here you can see that this this is discussed here the actual um layout that we that we have and you know they end up doing basically exactly what we end up doing um we they have a list here it's either empty or it's an element that you know they're using different names they're using i32 as the hard-coded type that it has and then they're boxing the list here um but as i point out here this is a really foolish definition on our list uh for for two reasons we're we're allocating a node that just says hey i'm not actually a node and what they what they mean by that is like let's create um a a one element list here so our list is going to be a node and it's going to be non-empty and it's gonna have some number in it you know 1091. um and then it needs to have another node in it so um you know we have to box up that node box new and then node and if we want the list to end here we say empty like this um and of course we need to bring in these types into our tests so that we can actually use them so so this is a little bit wasteful in that we you know this right here is basically just saying that the next element the list is empty but we're we're calling into the you know into the system allocator here where we're actually allocating memory on the heap here um just to say that that this element is empty here which is a bit of a shame right um that would be it would be much nicer if we if we didn't have to to do that chad has a question here what's the difference between using uh ampersand and box both are pointers yes so so the question is um we use box here which is an owned heap allocated pointer here which you know we've we've chosen to do um when we looked at the error message before it was saying you know you can use uh rc you can use box you can use ampersand why why don't we use ampersand here so let's give that a try let's let's try to use ampersand and see what we end up up with here okay well first of all we're going to get a basically a syntax error here where it's saying we're missing a lifetime specifier so what it wants to know is you have a reference to a node here a pointer to a node here that's going to live for a certain amount of time and we would we need to know how long how long does it live for and so in rust uh we don't need to know that for box for instance um because box is an owned pointer meaning that we decide when we have a box when the value that it's pointing to is destroyed is cleaned up but with references we don't decide that we're simply borrowing the value so there's some other you know variable in our program that owns that node and we'll decide when to destroy that node and we're borrowing it so we need to like does how long does this thing live for because it we have to prove to the compiler that it lives for uh a shorter amount of time than the then the node itself actually lives right so it's asking okay like give me give me a lifetime here that i can deal with i i need to i need to understand how long this thing is and lifetimes are always generic so we need to like come up with a lifetime here like uh and by convention we usually use tick a as the name here okay and then we get another syntax error and saying okay i don't know what that is that's because tk is some lifetime we just called a we're just coming up with it with a lifetime and we're giving it the name a we could call this literally anything except for static which has special meaning um you know we could say take foo here and that works as well um or rather doesn't work for the same exact reason right it doesn't know what foo is um we'll stick with the convention here and just do tick a and the way that we say this is we come up here and say that node is generic on this lifetime a and the way that you can think about this is the following the way that you can think about this is that this node when we have a node it is constrained to live for as long as some lifetime a and that is however long the the reference that it that that node contains inside of it lives because it doesn't make any sense if we have a node that lives for you know a certain amount of our program and let's look at it visually here if we have a node that lives for this long in our program but that node contains a pointer to another node that lives this long well then for this part of our program we'll be carrying around a dangling pointer we'll be pointing to some node that is that is junk memory right and that's not very good um so we're kind of tying this outer node value here to the lifetime of the enter node here all right hopefully that makes sense um and of course then node itself now is generic on on a lifetime so we probably wanted to do this here and this this works fine you'll you'll you'll notice um that you know we're getting some warnings here or whatever but um but this you know this compiles this part right here compiles and in fact you know if we remove this like our program is going to compile just fine here this is totally fine the the the part about this that's difficult though is that this doesn't this is very hard to use right but as we need node we need to to uh explain to to rust uh that node will live for some lifetime a right and so how do we do that um well we can go ahead and say node is going to be empty like this um and we'll go ahead and borrow it right here and now we can say oops and this works um but if you keep trying to actually use this thing like you know once we start passing this around and stuff like that it's going to be it's going to be very difficult to actually use so we can use decay here that's totally fine but it gives us less control over how we're using our node because now node is going to be constrained to some lifetime ticket here whereas before we didn't have that constraint because we were using owned pointers in a box let me know uh if that makes uh sense to you um and and if not we can kind of take a look at it in a different way and chad is kind of joking around and saying you know but we we can get rid of this generic here by using the one like non-generic lifetime that russ comes with which is take static here and this is also possible uh um oh of course doesn't need that uh this is also possible um but again you're going to run into a lot of situations when you try to use your linked list where this will be not so not so useful all right cool it looks like chat is saying that that makes sense which is good [Music] and and it looks like we've got some uh malac trolls in our chat as well uh wanting me to use malakai this is not this is not c so we're not going to use malek directly unfortunately um all right um cool so we're gonna go back to uh the box syntax that we had before like this all right so um whoops sorry about that then uh going in here um you know we can we can we talked about uh the problems that we had here we're allocating um the last element in there just to say that it's empty um and uh and one of our nodes isn't keep allocated at all so um you know it says like on the surface this you know this kind of cancels itself out and stuff like that um but uh you know we this isn't ideal right um we we would rather have a layout that is that is uniform where each element has this has the same uh has the same layout and um if you want to read in like some possible other ways uh that we could do this with with empty elem then empty um that's that's also not so nice and stuff like that um but instead we can kind of separate out um the idea of a node um from the the idea of the list as a whole um and i wish my wish my phone was not turning off so that i could continue to see what what chat is up to um real quick here all right um all right and chad is also asking um they're curious about the rules for when a box is freed um so box box and rust is a an owned pointer it owns the value that it points to so this box owns this this empty node here and in rust things are freed things are are dropped as the um is the term in rust when they go out of scope so as soon as this box new goes out of scope here and this this box is in turn owned by this this non-empty node here so when all this kind of goes out of scope which happens just on line 12 here then recursively everything will be freed here so that's very important in rust when you have an owned variable at the end of the scope of that own variable that's when uh the the own variable uh gets free to gets dropped so hopefully that helps a little bit so here uh what what is being suggested is that we break up the idea of a node with the idea of a list as a whole here where we say something along the lines of uh enum list here right is going to be empty um or a link of some sort right and i guess they call it uh more we can stick with that as well more or i like the name link and then we're going to box up our our node here and then node is no longer an enum node itself is actually going to contain the element and the the next list so element here element we were saying a u32 um and next just like that all right and this has a more uh uh uniform um layout then so the tail of the list never allocates extra junk um which is great um and uh there are some other things here um that it's a null pointer optimized form which we're going to talk about in just a second and all elements are uniformly allocated which is which is good this is exactly what we want let's see and then we have to come back down here and change um our test here to say okay our list is going to be a link um and it's going to be a box new node um and it's going to sorry box new node element and our element's gonna be 1024 some number of some sort and next and then it's going to be list empty so hopefully you see the difference between this and the previous thing that we had here we've basically flipped it around now where uh ins we're kind of always allocating we're allocating first and then if the next element is is empty then we don't have to allocate whereas before it was the other way around we were uh not allocating at first but if the last element was empty then we would still have to allocate there's a question here can you prove that final bullet about the allocation concern being resolved do you mean this one i'm i'm not exactly sure what you mean if you can if you can let me know what you mean then i i'll be happy to talk about it um all right great um so we have we have a a a list here um and in fact i think uh if you keep on reading here then yeah this is this is a good uh point to add here um we're kind of exposing out the um the the the inner workings of how we are um you know we have we had two ways of building up our our linked list and we've switched between the two of them um and of course if we were exposing that to the user the user would be would be well aware of how we're actually building up our linked list um instead of us providing kind of a nice wrapper api around it so that the user doesn't have to look at the the inner workings of our of our linked list um implementation here and so instead you can do something which is quite common in rust where you you basically provide a wrapper struct around these inner workings so now we have our linked list um uh struct here and the linked list uh is going to have just a single field head where it takes a list here right um and in fact we probably want to we probably want to call uh like this link and something like non empty all right we can do link on empty and link all right and this will become important that we're providing this this wrapper here in just a second now uh there's one particular aspect that that kind of calls out to me when when looking at this right this link element here is either empty so that either doesn't exist or it does exist and it's a box node and so we've implemented what essentially in standard rust ends up being an optional type and an optional type if we look at option here an option type is either none it doesn't exist or it's some it does exist which is exactly what we have here just with different names um and so instead of our our link being you know and our own enum that we implement here we can just do uh link as a type alias around option box node just like this and this is effectively the exact same thing that we had before except now we you know we get the the standard libraries implementation on top of it and we'll be able to take advantage of all these nice um uh apis that that standard libraries option comes with excuse me thank you all right so now that we've gotten that sneeze out we can uh change this here um i think we can go ahead and do yeah link sum and link none and in fact we don't actually need link colon colon here we can get rid of those um and just do summon none because those are available for us to use all right let me know if you have any questions here about why we chose to uh gesundheit oh thank you either yiddish isn't it or is it dutch i'm always confused sometimes when i see dutch i think it's the and sometimes when i see yiddish i think it's dutch so um yeah let me know if you have any questions about uh about this year but we're uh we're basically um you know re-implementing what we had before using the standard option type instead this down here where we're actually creating our our linked list is you know we're actually not creating this linked list struct here right so we'd have to do something uh like linked linked list uh head and hopefully yeah there we go so now we have an actual linked list here but this is really nasty right it would be nice if we if we didn't have to write um things like this um and in fact um if we're creating a library here and and users of this library won't even be able to write code like this because head here is not public in fact nothing in our in our library is public yet so we should probably do that right here and now now things are good like linked list is the only public thing so our public api for this library is just this linked list type and and users of our library don't even have access to to these things here they won't even be able to to construct this um which means right that we have a linked list that that users of our library can do nothing with they can't they can refer to the name linked list but they can't create the linked list because the only way to create the linked list is to build up a node and they don't have access to node because node is private right so we need to provide a way to actually expose this out to them and that we do that by building up some nice you know methods for them our first thing we're going to do is a constructor function of some type which by convention is called new linked list here and we're going to do linked list with head being equal to none so this is the empty linked list here we could also call this empty if we wanted to like this so now we have a way of actually constructing a linked list by saying linked list empty all right hopefully this makes sense to everybody that we haven't we have a way of uh of constructing an uh an empty linked list here where we've simply specified that the head of our linked list is does not exist it's none right all right great but now we need to have this is where things get really fun now we need to have a way of actually pushing an element onto our list um so let's go ahead and create a push function here which is going to take a mutable reference to self because we want to we want to mutate self here and it's going to take the element which we've hard coded to be a u32 here and it won't return anything and we can just use the to do macro here um so that it will compile um an effect like implement to do if you've not uh implemented push do not use the to do macro before this is simply a way of of saying let the code compile but if we run this code it will it will crash right here um chad is asking are we going to be using iterators in this implementation of the yeah we can we can go ahead and implement an iterator as assuming we'll have enough time all right so down in our test then best thing to do is list dot push and 1024 and uh and of course we have to mark our list as mute because we're mutating it oops and this compiles uh but if we go ahead and do cargo run oops sorry cargo test um it crashes saying not yet implemented because we have not implemented this push method so let's go ahead and do that so i have to ask ourselves like what do we what do we actually want to do here well um the way that a linked list works right is you take the head of the linked list and you construct like a new node um and you make the former head of the linked list the next uh the next link in that node right um i'm wondering if they if and here we have some nice visualizations of a of a linked list just to uh i thought we did yeah here um this is not exactly our uh this is not the best anyway let's let's just think about this again logically you have the head of your list and it points off to more things and it has an element in it you want the new head of your list to basically be another node that is pointing to the previous title of your list right so let's let's start writing this in a somewhat um naive way right we can can match on our head here and see like if we don't have a head then our head is simply going to be equal to box new uh sorry um it's going to be sum box new um and then we just do link with the element and the and the next is simply none just like this um oh sorry this is node so this is the easy case right we didn't have any head before our head was empty we have an empty list right and now we're just setting the head of our list to be uh to be a boxed node where the data inside of that is what was passed into us for push and the next element is none so now we have a one element linked list right and if we do sum [Applause] to do then this is working fine this this completely compiles fine we are not um implementing the sum case yet uh so that's so this is fine this this compiles fine and in fact if we if we run it the the test pass right we don't crash or anything like that but of course now if we go ahead and push another element onto it uh 42 here then it will crash because we've reached this point where we had a head of the list and now we need to actually go ahead and implement this as well so hopefully that makes sense to everybody let me know if it doesn't so we can go over it again so now we need to need to make the decision and you might be thinking okay so this is the node that was the the previous head of the list what we want to do then is to construct a node a new node where the element is whatever was passed into push and the next element is the previous head of our list like this okay of course we're not quite done yet this is our new head right and then we say self-head is equal to new head and this is where we run into issues right um oh and of course right now we're running into the issue that we have to wrap this in the sun this is where we run into issues and the issue is right here we are moving out of self.head right here which is a is behind immutable reference let's let's compile this here and this becomes a little bit uh more transparent what's happening here so we're matching on self.head and when we match on self.head then we are moving out of it we're trying to like rip out self.head from our from self we're trying to like take the the head from it rip it out of the thing and we can't do that we can't rip out pieces of our data structure because we don't own that data structure the only time you can move things out of a data structure is when you own it otherwise you're simply borrowing it and just think about it if you were to try and rip out the head of this list you what would be left right there's nothing there right um nothing would be left and that's that's that's that's can't be right um we we need to leave something in its place right um chad is asking is there any comparison between russ compiler and c plus plus compiler code optimization assembler output um there's a lot of uh comparisons between the two um it would be i think that's a very very very broad um uh question like comparison uh i think you'd have to have more specific questions for the for for us to like dive into that and chad is also asking if we're going to get into doubly linked lists today unfortunately i don't think we'll have time um i'm trying to take this slow um and uh i don't i don't think we'll have time to get the doubly linked list but we can go ahead and do that maybe next time and you should be able to do wlankless without unsafe um that's that's certainly possible although it probably is not the most performant double link lists if you don't use unsafe um cool and there's a little bit of a spoiler alert inside of chat which we'll get to in in just a minute um all right so we we have the head of our list what we want to do with our head of a list is basically take the head of the list like put something in its place and say like okay the head of the of the linked list temporarily is here stash the old length uh head of the list inside of our new head and then set the new head of the of the linked list and in fact there's a there's a good reason why um we can't do this this way um in particular like we when we rip out the the old head of the list here um we don't have anything kind of sitting in memory we can that that is valid sitting as the old head of the list which is fine like inside of this function right here because we're like the next line we're setting uh that head to be the new head here but just imagine for instance that we panic right here for some reason if we panic right here then other code will be able to see that you know we've ripped out the head of the old list and then that can lead to a whole bunch of um of terrible terrible things happening here so rust is preventing us here from ever being in a a memory invalid state here where the head of the lifts is is just kind of uh invalid memory essentially all right so how do we actually uh handle this well we need a way for taking the head of the list and replacing it with something else and giving us access to the previous head of the list right um it looks like we have a spammer inside of chat which is unfortunate i'll hold on one second here just going to take care of this real quick oh it seems like i can't seems like i can't uh take hopefully that doesn't get any worse but we'll keep our eyes on that all right so we need to to replace the the head of the list at this point with with kind of a placeholder right and there's a perfect uh standard library uh function for doing this and that is standard mem replace and what standard mem replace does is it takes immutable reference to to something and an own value and places the old value at where the immutable reference is pointing to and returns back the old value so let's let's write some code so we can see what that actually looks like what we want to do here i'm gonna comment this this code out here we want to replace our head of the list with nothing with none so temporarily the head of our list will be empty but what standard mem replace gives us back is the old head so now self.head is none but old head this value that's on on uh on the stack is the old head of the list and then when we have that we can simply build up one of our one of our nodes where we say box new node element is whatever was passed in and the next is our old head here and this is our new head and now we can set self.head to the new head and this should compile just fine and hopefully run just fine and it seems like it it is so let's take a let's take a step back and and figure out um figure out exactly what's going on here again take a take very slow here we have essentially replaced the head of our list with a temporary holding value of none so our linked list is temporarily empty giving us access full on owned access to the old head of the list then we build up the new head by creating a node and setting the next field to the old head and then we set self.head to equal that new head and this means that every point head is pointing to a valid value now you might be thinking to yourself okay well between old head between this call here to statement replace here and this call here to setting the new head self.head is equal to none which isn't isn't true right like um we are kind of temporarily erasing the fact that our linked list is potentially non-empty and lying and saying oh temporarily it's empty while we kind of build up the full tree that's totally fine that is um the only way that that people will ever be able to to see that potentially is potentially during a panic unwind when um and this is getting way ahead of ourselves so we don't really have to worry about this and in fact like we don't even have to worry about thread safety or anything like that here because we have an ampersand mute self here which means we have exclusive access to self so there's no other thread possible that's pointing you know to to the linked list here and being able to observe that we're temporarily setting the the head of the list to none we have exclusive access to our to our linked list here so chat let me know if if that makes sense and of course we had a uh if you were following along in chat we had a little bit of uh of a spoiler alert and sorry sorry to call it a spoiler alert it's not uh it's not a big deal it's really great to see people uh in the chat um offering up answers to how we can solve this this this whole idea of an optional value where we want to temper we want to get the inner value um of an option um and replace that value with none just like we're doing here this this pattern here is very common it's so common in fact that option comes with a shortcut where we can say self.head dot take which does exactly what what we had before let's take a look at the the documentation for take take says it takes the value out of the option leaving none in its place so if the value is set then we get the value you know if it's if x here is sum two and we call x dot take then y here is equal to sum two and x has been replaced with none which is exactly what we want to do we want to replace head with none and get back the old head here all right so now we have now we have push any questions uh about this hopefully this this makes a a lot of sense um hello hypermanu how's it going this is essentially um a fully working linked list except of course that um we're missing a bunch of important functionality here but at least we can construct our linked list fully will the video be available somewhere yes where i'm i'm recording this and will be available on youtube uh later on and of course if you're watching from youtube in the future hello so uh what's uh and chad is asking a very important question here what's the difference between none and the invalid memory configuration both are in valid states on panic right they are both in they're both in valid states but one is a ver a much more serious and valid state and this is kind of the the reason that rust exists the invalid state where the head of the list is temporarily set to none is potentially a little bit of a business logic error where our list has been replaced has been made empty which is totally fine like push like we have we have ampersand but self here like we make no promises like we're allowed to make the list uh empty here of course push making the the the list empty on push is not kind of correct from uh from the standpoint of of um of doing what push should do um but uh but we're allowed to do it having the head be invalid memory opens yourself up to a whole bunch of potential nasty bugs um that can be quite dangerous in terms of security and stuff like that and so at the end of the day you have to remember rust is a memory safe language so we want to have we want to have a language where we always have a fully memory safe view of the world where all of the memory that we're accessing is always valid because we don't have that then you open yourself up to very interesting and very hard to track down bugs um uh so there's there's kind of a key difference between um kind of business logic invalid states versus invalid memory corruptions essentially is what the way that you can think about it it's not a it's not a invalid state it's a corruption of memory that we are avoiding um hopefully that makes a little bit of difference um yeah chad is saying for the example the invalid memory could look like a valid node but the pointer to the next code could point to arbitrary memory yeah which is a great way of saying like sometimes you have a bug and you don't even know you have a bug right um if we set it to none then the code that that is able to view that let's say in a panic handler somewhere or something like that potentially you know they can look at it and say oh this this list is just empty or whatever that's fine um and in fact the code that it's not leaking memory or anything like that like the the elements in that list have been freed as well so it's it's totally fine but if you were able to expose invalid memory then um it's potentially that code could look at that and say oh this is this is a totally legitimate list and chase down memory and go into memory that is not um correctly allocated and then really weird things can happen from there on there's a thing i think in this case if we don't take the head we can double free the memory um how so i so no we can't double free the memory because uh and this is great this is a perfect example like there's a question about can we double free the memory here and the answer is we cannot and you know how i know because we've only written safe rest and in rest you cannot double free memory it's it's impossible um so we have definitely not double freed memory but um let me know what makes you think that we might have double freed memory and we can talk through uh what's actually happening there but this is a really great point about how if uh in another language you might have to worry are we potentially going to double free memory or even an unsafe rust you have to worry about double freaking memory but in this particular case we don't have to worry about it because we know we're writing safe rest and in safe rust you cannot double free memory all right let's really quickly go through and see if we can write a pop operation which is essentially the opposite of push here this needs to be itself and when we write pop we want to return back an option um u32 here so if the the list is non-empty or return to 32 and if it is if it is empty then we will return none yeah so so chad is wondering about the double double frame of memory in here inside of push if we end up copying um if we end up copying old head here right well here's the the great thing we can't copy this old head in the sense that we can't create an aliased pointer to the old head like this we can't create a box that also points to the same node we can clone it where we would essentially just create a deep copy what is known as a deep copy of it but uh box node and rust does not allow you to make a shallow copy does not allow you to alias the the the pointer that's pointing to to the node here for this exact reason box node and roster box t and rus is an owned pointer it's an exclusive you can think of it in c plus like unique pointer it is an exclusive pointer to the thing that it owns and so there's no possibility for you to to copy uh the pointer there you can only do a deep copy which would essentially just reallocate all of that memory and you'd have a completely deep copy of the thing this is exactly what we're talking about with rust where you can't run into these issues and the reason for that is because in safe rust these issues just do not exist they're impossible to introduce and in fact you can use this as a challenge think of all the interesting things that you've run into and rest with double free use after free and stuff like that and try and write say for us that where those issues occur and you won't be able to do it now you can write unsafe for us where they do occur but that's for another video where it's a little bit more advanced all right hopefully that answered your question i don't mean to attack antagonize or anything like that this is um this is a really great learning opportunity for understanding the safety properties of rust these these issues just cannot occur cool so let's do pop real quick and pop like i said does the opposite of push where it kind of takes the the head of the of the list and removes it right and chad is saying make illegal states unrepresentable that's that's essentially what rust is doing it's making these these types of states impossible to introduce yeah chad is clarifying maybe the point of of what chat was saying like um yes i see here exactly like uh exactly as you've said if rust were allowed to uh to allow you to copy the pointer itself then it would end up double freeing the memory but rust doesn't allow you to do that and that's why it's fine to do this in rust but in c it's not fine and see you have to worry about this stuff awesome stuff chat thanks thanks a lot for that it's great so for pop we're gonna we're really gonna do the exact same thing like we're gonna get the old head here this is the old old head here we can match on an old head and say you know if it's some thing in there then we can go ahead and get the node out and the node we can go ahead and get the element from it and return the element like this and if it's none we'll return none here oops and i gotta put the and this is almost what we want right but now we've essentially made the entire list empty which we don't want to do and really what we want to do is say self.head equals trying to think what the best way to do this here is because what we want is in here for self.head to equal um this is probably the best way next and this is this is fine so we're essentially taking the head of the list replacing it with none then if we had an actual head of the list we set the head to be whatever that head was pointing to before and so now what it was pointing to before is the new head of the list and we return back the element and otherwise if we didn't have an old head of the list then we can't return an element so we just returned on and in fact this is a very common pattern here where you're matching on a value and if it's sum you do something and if it's none you just return none here and that is a map operation so you can do this instead and this is the same same exact thing here as before oh and of course all right so this is pop done right here let me know if you have any questions about pop and i think the last one um that we need to do is peak and what peak does is let us look at the element where we're returning back a reference to the element um instead of returning back an owned version of the element um so we're not rip we're not kind of like taking away the the element at the head of the list we're simply like providing a reference or a pointer to it and chad is asking you don't need the old head variable anymore no no in fact you don't we can we can just do this instead oh yes i've misspelled peak to be like the peak of a mountain instead of peeking at something i don't think you need the the temporary variable i think that the bar checker is able to oops yeah the bar checker this this code right here i believe used to not um compile in rus 2015 because the borrow checker wasn't capable of understanding um that uh self.head here is not mutably borrowed anymore but now it does compile if that doesn't make any sense to you then don't worry about it alright and then peek peek is pretty simple in that and of course peak needs to return an option because the list might be empty and if the list is empty then we can't return back a value and we can look at self.head here and if it's sum then we return back in dot element and i'm always for getting this right here and if it's none none um and this is not compiling here um because of this um this is not compiling here because we are trying to move head out of where when by default when you do self dot something you're trying to move it trying to rip it out of the um of the thing that contains it here and we don't we simply want to borrow head we want to take like we want to look at it but not take ownership over it so we can do this instead and this this is the same reason we need ampersand here as well if we try and do this it will complain it will complain in this case because the types don't line up but um we need that as well there to to borrow n.element instead of ripping in.element out of of the node and again we can just do self dot head dot map n n dot element um and this is exactly the same thing that we were doing before um oops and this doesn't compile for the same reason we're still trying to rip out head from self we're trying to take ownership of it instead of simply like instead of simply borrowing it and the best way to borrow an element inside of an option is by using this as ref method here and we need this as well so that is equivalent to what we previously wrote and you know depends on on taste which one you think is more readable i think in this case i might actually prefer the match statement or the match expression instead of of this this style here all right we're reaching the end here the last thing i want to do real quick is simply just make this generic because we're hard coding um this element here this u32 element here wouldn't it be great if we could keep anything inside of our linked list here and so if we go here let's make this a generic type t and it's a generic type t it says i don't know a type t by default it doesn't know that this is generic right it doesn't know that it's looking for a generic type t we need to say that node is generic over some type t and now it's now it's fine and we basically need to allow this to kind of bubble up and say link itself is also generic over some type t so we can pass that into node of course now link is generic over type t and link is generic over some type t and that means link lists this generic over some type t and that means here that we need to be generic over some type t if we do this right here again impul linked list t is looking for an implementation for linked list where the element of the linked list is some concrete type called t which there is no concrete type called t right and in fact a lot of people don't know this but you can have different implementations of things for different concrete types so we can have some methods that only work on linked list when the element is a u32 and we can have another implementation [Music] that only works on linked lists of strings and these will all these uh implementations here will be methods on um linked lists when the element is a string and no other time right and so in order for it to say this is this is the implementation for a linked list for some generic type t we have to first say we have a generic type called t and now this knows that this t is the generic type t that we've previously defined and we're getting an error here right because we're passing into u32 and it expects the type t we have to change this to t and we got to change this to t and we got to change this to d yeah and peek is rightfully saying that uh peak chat is rightfully saying that peak doesn't need to be doesn't take need to take immutable reference because we're not actually mutating the um mutating the the linked list when we peek at it we're just looking at it thanks thanks for pointing that out chad and this is this is it we we basically have a um an implementation of a singly linked list and rust um you know it's not that bad right the reason that this is um oftentimes talked about as you know being not the the easiest thing to do when you're first learning russ is because you do have to have a little bit of an understanding of how ownership works right if you go through the naive way of doing things that we saw before where we were simply trying to rip out the head of of the list and not replacing with anything russ prevents you from doing that because that would leave memory in a bad state and then rust you cannot do that and so we have to go through a little bit of extra [Music] mechanics here which are which are not boilerplate right this is you know we do that in in one little method call here um so it's really not that difficult um but um you know we do have to go through a little extra work here to always keep our linked lists memory and a good state here and chad is also saying we could also implement our own drop implementation so that it doesn't recurse through the entire data structure to to drop it we could that i'll leave that as an exercise to the reader there are definitely a few things that we could do to optimize this a bit further but i mean this is a linked list generally how you would write it and see except for the drop empl that we're talking about where you would probably loop manually and free things but it's nice to know in russ that we get a we don't have to write a drop and pull here our memory will be freed when our linked list is dropped for us because the linked list will drop its link when the link gets dropped it drops its box when the box gets dropped it drops its node when the node gets dropped it drops its element and its next link and so on recursively all the way through until there's nothing left to drop so we don't have to worry about drops even though there's potentially a slightly more uh a slightly more performant way of doing drops than you get out of the box for free and one last thing the chat is mentioning um using uppercase self here we can for instance we don't want to refer to linked lists here because we might change its name in the future we can call itself this is the self type it just refers to the type of the implementation you often see this i don't believe you can do this here for generic types you can't write stuff like this um that doesn't work unfortunately type arguments are not allowed for self types here so we don't get that for free but this is one potential cleanup that we can do here oh just self works okay we can't do this great so now we're not explicitly naming linked lists uh here which can be useful um if you don't want to have to repeatedly say linked list all the time all right so the last thing that i'll mention while we we wrap it up for today is this was the singly linked list right there are doubly linked lists where for our singling linked list right the node simply refers to its next node and a doubly linked list a node refers to its the next node at the list and the previous node and this is quite this is somewhat difficult in rust to do i should say it's a little bit more difficult to do it in a safe way and rust but it's not that performant and it's pretty darn difficult to do it in a very performant way and rust um again the standard library comes with the double d link list uh implementation if you really need a doubly linked list just use the standard libraries version but most of the time you don't need a doubly linked list and russ just use vec that's uh like 99.9 percent of the time what you need so we will um it seems like there's enough interest and perhaps i'll come back next week with a with a a stream on doubly linked lists instead and of course vectq is a great is a great um an even better potentially way of replacing a doubly linked list because effect dq is just like vector except that it allows you to pop from the front of the vector and the back of the vector instead of for vectors it's just the front all right so just uh finishing up with a few questions here yeah the docs on standard collections uh for linked list we looked at that before start with it is almost always better to use vector vectorq because array based containers are generally faster more memory efficient and make better use of cpu cache and they're also yeah just just use vector vector unless you really know that you need a linked list use vectorvec dq and chad is also mentioning also with slabs you can do safely and even faster than usual it's basically just using the back yeah so slabs are are a way of basically like chunk allocating memory just like you would do in a vector and then using indices to build up a logical linked list but where all of the elements are allocated in one continuous array of memory instead of how we're doing a linked list here where each element is boxed it's it can be anywhere and memory the allocator is free to put it where it is with a slab you say you basically create in a way your own allocator which sounds more difficult than it actually is but that's also an interesting thing that potentially you can take a look at is is creating a linked list using a slab instead all right any more questions if not then i think uh that we're going to end the stream for today um my goal with this was to take things slow if i didn't take it slow enough if you're still lost feel free to reach out to me [Music] and you can see up here up top at the very top of the screen you can see my uh my twitter handle my github handle up where you can find you can search for me on youtube as well where i'll put the video for this after the fact so let me know if you have any questions if you if you followed the stream today then you are very much on your way to being a intermediate rustation very much on your way to understanding the borrow checker and how memory management and rust works so this is definitely not something that you should just take for granted and this is kind of the foundation of rust this is something you should really spend some time learning if you want to get into the language so make sure to give this another view on youtube and thank you everybody thanks chat for for a great discussion and um it was a real pleasure and hopefully i will see you next week maybe we'll do um round two of this where we just try to tackle a doubly linked list which will be even more fun all right appreciate everybody and have a good weekend

Channel: Ryan Levick

Views: 7,215

Rating: 4.9566789 out of 5

Keywords:

Id: IiDHTIsmUi4

Length: 79min 29sec (4769 seconds)

Published: Mon Oct 26 2020