Why You Should AVOID Linked Lists

why should you avoid linked lists let's go okay here I'd like to to show an example that first was shown to Me by John Bentley of algorithms Fame make a sequence of random integers keeping them in order and so you you you're given the numbers 5142 and it builds up the sequence as you see it there and then you remove them again by giving a set of positions of which one you you take out and so the exercise is for which end is it better to use a linked list than a vector okay or an array okay and so for those that don't understand who here doesn't understand the question that was just proposed right here type one in the chat if you don't understand the question that was proposed by the way if you don't love 14p you know type one in the chat okay so it's actually a pretty it's a pretty simple question right uh here let me see if we can exit out of here uh let's go to the X Cali draw this that it's a very it's a very interesting question so you could imagine that there exists a world in which there is some large space like this in which you have a bunch of elements right one two three uh four or five all the way up to whatever right all the way up to I don't know 69 420. and then you have in another world something that looks like this where hold on let me get this thing and drop it all the way down to this and you have one and one well guess what one points to two right there you go one points to two two points to three all right so a linked list versus uh a contiguous memory region called an array right and so if you were to remove some random number from here what has to happen well for this to happen is that it has to take say you remove 17 well 18 will have to shift down to where 17 was 19 has to shift down to where 18 was 20 has to shift down to where 19 was etc etc et cetera all the way up to 69 420 whereas with the linked list if you were to remove two well we removed two and then we just adjust this nice little thing right here boom there we go it's it's constant operation right you do effectively if it's doubly linked list you do like four operations on it and that's it whereas if you had a memory array you'd have to do a lot of operations on it to get the same effect so there you go so that's the problem he's proposing how big of n do you have to be where a linked list is faster than using an array oh they would have known this if they watched your free algorithms course on front end Masters you're right free algorithms course on front and Masters by the way frontendmasters.com trial I get zero dollars if you sign up never pay for anything and just watch this go for it free algorithms course it is like 11 hours long okay 11. nine hours and 21 minutes long of me just talking about algorithms and we actually go over this exact problem even in there anyways okay so let's keep on going hey hey baby girl all right let's keep going everybody gets this one wrong um his yep let's go let's do this I don't know how fast I want to do this because I don't want because I don't want to make it hard to understand he's struggling My Graph has disappeared the man the man struggled with presentation okay um okay so imagine this to be a graph beautiful graph the um imaginary low line down by the bottom showing efficient usage little time is the vector the one that is looking like an exponential trying to go through the ceiling is the list and trying to figure out why the the list is so inefficient I thought maybe it's all this allocation that's been done for the nodes so the little middle green line which you can't see either is is the lists with allocation taken out precurely pre-allocated the point here is that the vector is always better than the list and the list gets worse the further you go out and this is for the case where you're doing a lot of insertions and deletions which when I was taught about data structures was what you use lists for because they're really good at inserting deleting if you want to insert in the middle of a thousand a hundred thousand integer Vector you have to shove on average 50 000 elements in one position if you yeah take one out you have to shot them and roughly half the way back I was taught this exact same thing like this is this seems very intuitive this seems like the exact reason why you one would use a linked list I I'm a little flabbergasted right now now this is completely irrelevant what matters is a linear search to get to the insertion point of course you have to go through half of the list to find on the average insertion point for a list and in terms of fairness I also took the same vectors instead of using a binary search but anyway so the linear search dominate completely and linear search vectors it's not actually such a good idea first of all a vector for a list a list is much bigger for a given data structure than a vector because you don't have to just store the element the integer you have to store the two pointers forward and backwards you have to use a doubly linked list if you're inserting otherwise you have the extra problems that makes okay so this this this already makes a lot of sense because one thing that is unique about a vector is that it's contiguous memory right whereas linked list is not a contiguous piece of memory right each each little node has been mallicked somewhere in the universe of space and so you you most certainly get like a lot of different you know I can't believe this man-made this you can't believe this man-made C plus plus if I were to ask Chad gbt what does someone look like who probably invented C plus plus I think they would they would create this right so you get this whole you get you get something beautiful that happens with the vector that just can't happen with this uh so that makes sense and the second thing I guess I never really thought of in this problem is that to get to the node you wish to remove you have to do a linear search every time and that completely dominates um so the the the graph here this graph here that you can't see so I guess the only thing that would make sense is if you did head removal head removal and head Edition probably definitely winning linked list at a pretty small number but everything besides for that any sort of manual looking through the list to get to a point I guess this makes a lot more sense than I ever realized because you have to follow so many gosh darn dang pointers just to get to that point uh shows you that there's not a minor uh a disadvantage here we're talking about things being 50 or 100 times slower with a linked list and the traversal dominate so compactness matters vectors are more compact than lists and predictable usage patterns matters enormously with the vet so you have to shove a lot of elements to war but caches are really really good at that so surprisingly vectors are random access constructs but you can stream them lists don't have Random Access but when you Traverse a lists you keep doing Random Access there's a node here it goes to that node in memory so you actually random accessing your memory and you're maximizing your unpredictability cash misses yeah which is exactly the opposite of what you want so the the the lesson I'm trying to say here is stay compact stay predictable and you have three orders of magnitude of performance to uh to to to to deal with here to gain by being compact you know I have I have his book I think a tour of C plus plus I actually think I can see it right now and uh in there he says always use a vector unless if you can prove a map is faster and I thought that was very interesting because it is better often to search position by position to get the thing you want then to perform some math calculation that offsets correctly into some larger memory region which could follow a linked list or maybe some sort of vector or whatever it has underneath the hood to get to the point because of cash uh because of uh key collisions right and so it's kind of surprising that that is a real thing and it's true we did it with I did a video where using a map to do character lookup was slower than storing the characters in an array or even a vector even a vector in Rust was faster than using a map which then an array was even faster now tour is awesome tour is good true oh style look at that Beauty look at that beauty and said well I I don't use lists of a hundred thousand and two hundred thousand filaments and there's two kinds of people there's a sort of the the Google and Amazon people that says because I don't have such little data by the way this is uh literally this is just what JavaScript looks like I mean this is one of the reason why JavaScript is super hard to make it fast people always are like well javascript's only like 30 slower than C plus plus or whatever it's like no it's 30 slower in these really trivial situations where you're doing math because JavaScript is great at jitting and if you just do math of course it's great but the moment you start really playing with memory that's where everything just falls apart there's two kinds of people there's a sort of the the Google and Amazon people that says because I don't have such little data structures and then there's the students that uh that I think a thousand elements is a long list um and so I don't use that many hundred thousand lists but using a few hundred thousand element lists just exactly the same as a matter of fact you can get the performance effects out of individual data structures so here's a very simple one up there a vector of points with um with four points and the way that will be laid down in memory if you use the standard is up there label C plus plus you have a little Handler a lot of C plus is these little handles that tells you how to use things and then the resource manage which happens to be a compact data structure with h uh integers because it's integer points and um that's fine it's compact you have a single D reference to get to it you have a little bit of memory overhead because Vector keeps its elements on the freeze door so you get the the extra word or two as a free store header but that's the way it looks it's fairly compact if you don't want to put it on the free store don't but usually like you can afford it now by the way this is if you if you don't understand what's Happening Here this is fantastic this is really really really really really good I'm told very often that I have to write in a truly object-oriented style and there's languages that ensure you do that yeah and in truly object-oriented style of course an object is referred to by a reference so you have a reference to the object there's the object down there in the next line with the four with a count in it and this happens to be a container of um this is exactly what JavaScript does I can even go over this here in just one second this is exactly what JavaScript will do of of user-defined objects so again you have a container of references and there you have the objects so that turns the linear compact data structure into a linked structure we just saw on this invisible slide what link structures do to your performance and and here you get a rough doubling of the size of the data structure and whenever you want to access an element instead of getting one in Direction you get one two three in directions and in directions again is things that that modern computers don't like very much pointers are poisons in most of our optimizers interesting yeah you know like you know all those things but it's so great how he says it by the way I released all these videos why are you showing me videos of mine um so what's really interesting so like how that works is that you can imagine this like if you go over here to this sorry we did a bunch of uh showing someone how to copy and paste here but you can imagine that if we went to something that was a little bit more typescripty right and you went in here and you jumped here if I had something like a point right it doesn't matter uh function create uh point it doesn't matter if it's a class or not return uh X Y right uh X Y right who cares right here you go boom if you go const list equals this and in here you have create uh 0.42 for 20. uh yank that 69 420 uh 420 69 uh and let's go Bam Bam Bam Bam Bam why not even though there's no Rhyme or Reason to any of these things I did so there you go so you have this nice Point what's actually happening here is this is created and stored somewhere in the garbage collection every single time so each one of these points are stored just somewhere in the engine of of JavaScript it's not like you get this nice compact format where it is literally a space that holds a small amount of value how you could recreate this though in JavaScript you could imagine something more like this uh let's see const uh you know compact would be a new array uh or new you let's go what float64 array right and you could imagine you could have something like eight this on the other hand you have eight positions and you could actually have a function read a point and you could have a uh the you know uh points and you could have the offset right and this on the other hand could return you know something right create Point why not this is terrible but you get the idea right there you go you have something that holds all the memory I know I'm creating the point again just let it go right and that actually gives you out the point right here it's kind of interesting right you get this kind of you get this like a very different kind of views of the world which is one you store everything in a Row the other one you just store them randomly throughout your program the name the hippogen

Channel: ThePrimeTime

Views: 271,501

Keywords: programming, computer, software, software engineer, software engineering, program, development, developing, developer, developers, web design, web developer, web development, programmer humor, humor, memes, software memes, engineer, engineering, Regex, regexs, regexes, netflix, vscode, vscode engineer, vscode plugins, Lenovo, customer service

Id: cvZArAipOjo

Length: 14min 11sec (851 seconds)

Published: Thu Jun 29 2023