@@climatechangedoesntbargain9140 I don't remember what I was thinking, but full disclosure, I SUCK at making thumbnails. This one has an awful click through rate, so I gotta change it anyway.
On Modern x86, the most important thing for code optimization is cache. A cache miss is more expensive than a floating point divide. Arrays offer significantly better cache locality than linked lists. This means that they are almost always the better option on modern x86
modern allocators will also store their memory on the heap sequentially, and the cpu doesn't cache just the bytes you need at a time, it caches the bytes ahead of it too. So when you're working with a linked list and you allocate nodes on the heap its likely that that memory is cached since its near so much other data.
Well, at other end linked list guarantees you O(1) time complexity at each append operation instead of amortized O(1) in case of array list. This could be critical in some applications
I think in many ways linked lists are of pedagogical interest in computer science, partly because implementing them is often simple. It's a decent example for teaching recursion, it helps you understand other "node"-based structures like trees and graphs. In OS class or something with assembly, you might implement a free list, for which remembering linked lists comes in handy. But again, that's all part of the conceptual background. Sometimes it helps to know some other option exists, if only to be confident that the option you're using is the better choice.
Or just bad teachers torturing students. Most CS programs don't teach anything useful to students. My 4-year programming degree was about as useful as if I'd done a "hello world" and then hopped onto one day at a real job. Any decent internship is way, way, way better than most 4-year degrees. I had a CS prof, head of the department, IBM vet of 30 years. Loved his pointers. Whole exams were one code problem, and pages of pointer questions. We had to use some weird compiler because our school got sold some garbage. When I tried to do linked lists I was doing "something" (prof could never explain) that was technically correct but unusual. This wasn't handled by our weird compiler, so it caused issues. The prof dug into it. 48 hours before my semester-long project was due, the prof handed me 12 pages of documentation he'd written. He was proposing a fix for C++ itself as I'd found an undocumented bug. He basically gave me high-level instructions to personally re-code the C++ language by hand to fix the error. All I had to do was re-code C++ itself. Implement my new language in the weird compiler. Then re-run my code which would definitely have more errors. And submit that in under 48 hours. I'm glad I didn't own a gun. I've worked in programming for a decade and literally never had to know what a pointer is in my whole career. And I'm a web developer, full-stack e-commerce, which is a very popular role covering many technologies.
@@KevinJDildonik I have to disagree with you, a CS major does not prepare you fully for a web development role, web dev is just a small fraction of CS. You're better off taking a software engineering major if you want it to be relevant to what you're working as.
Linked lists are optimal for some algorithms. Talking about data structures outside the context of an algorithm using them is nonsense. The video here might confuse, as without context or the right circumstances as he says, it's hard to understand data structure choice. Linked lists are a fundamental concept learned everywhere in the world.
@Jeffris (Suspicious Manifold) sorry, I replied to the wrong comment. It obviously doesn't even make sense I context to what you wrote which I agree with...
From what I understand, memory is often pretty slow, especially compared with the processor. So rather than just fetching the data needed for the current operation, it instead gets a whole truckload of data at once including both the request and the data around it. Arrays exploit this to its full potential making data insertion and deletion much faster than it could be otherwise since it's moving entire blocks of the array rather than single elements. This alone often makes up for the theoretical savings of using a linked list.
Yes, that's roughly right. The CPU has L1, L2, and L3 caches on the chip itself, and if you need to do a memory access, first it queries the L1 cache for the data. L1 is smallest in capacity, but fastest access time. If the data isn't in L1, it queries L2. L2 is a bit bigger capacity, but access time is slower than L1. Same with L3. If the data in question isn't in any of the L1-3 caches, then the CPU has to go out to main memory to fetch a "page" of memory. This is orders of magnitude slower than accessing data in the CPU cache. When this happens, you have a "cache miss". Linked lists are a series of nodes scattered all over the heap, so accessing each element in a linked list could, in the worst case, mean a cache miss for each element in the list. With an array, it's stored as a contiguous block of memory, so it's more likely that you'll load a page of memory into the cache and you won't have as many cache misses. Your array could still be larger than a page, or the array boundaries might overlap a page of memory, but at least your cache misses will be significantly lower and you'll get much better performance.
@@slayemin Exactly, the "truckload" in the array context basically includes most if not all of the array in the same delivery, while for a linked list, the delivery contains only a single node, _maybe_ a couple, alongside a whole heap of data that you don't care about. I did however think that the CPU only requests a single cache line, which on x86_64 is only 64 bytes, rather than an entire page which is 4096 bytes. The latter would make the "truckload" analogy even more fitting.
@@panjak323 But the list is O(n) just to reach the place you want to insert or delete from, and because of low level details like the cache and locality, that O(n) has a larger coefficient than the O(n) for inserting and removing from a dynamic array. Overlapping/unaligned read/writes at least allows for slower vectorization. Traversing a limited list doesn't have _any_ opportunity for vectorization.
Overall, great overview. 99% of the time, dynamic arrays are better than linked lists. Even for queues, we can use circular arrays to implement deques which would usuall be better. However, it’s worth noting that when storing very large elements, it could be more performant to use linkedlists as they never have to reallocate and copy a bunch of elements over to the new buffer. The reallocation is obviously quite cheap for small types but for large structs with lots of data, it’s worth considering this cost. Additionally, some types disallow copying entirely, and so it would not be possible to store them in a vector. Finally, it’s worth mentioning that it’s often not too difficult to “magically” get to the correct linked list node because we usually return iterators/pointers to the new nodes as we insert them, which do
Damn, I was just going to reply with this exact thing. There are pros and cons for everything in computer science. It's important not to be dogmatic, less you miss a more efficient solution because it doesn't fit within your mental framework. Remember when we all first started learning? Everything was possible at that point. Then we started listening to the nay sayers - oh, that's not efficient, oh don't ever use X, use Y instead, oh Y is very inefficient, you should use Z instead. Pretty soon you start developing dogma around all of that. It's important to always try to push the envelope. Current standards are important to know as well - mostly so you can get hired :P - but current standards change. I have been in this business professionally since the mid 90s (I was coding when I was 13 in the mid 80s when I taught myself assembler using MSDOS) and I can tell you with certainty that current standards have changed and they will change again.
> it’s worth noting that when storing very large elements, it could be more performant to use linkedlists as they never have to reallocate and copy And that's why Unix-style filesystems (i-node, indirect block, higher-order indirect block, all that...) essentially use linked lists. 'Aha' moment for me; thanks
@@smorrow Right, if you're going to store big arrays of bytes, you want to store them either in a linked list, or as an array of pointers to the big arrays. Or both at the same time, as in B+ trees
The most common usage for lined lists are hashtables. If you implement a hashtable and you get a collision, the easiest, yet still efficient way for handling it is to replace the value with a linked list of values. Of course, that will get slow as your linked list grows but if that happens, you have too many collisions anyway and then either your hashing is bad or your hashtable is too small ("too loaded"). The alternatives to a linked list would be using an array but that will buy you little if you plan to have 2 at most 3 collisions before you decide to resize and rehash the table or use an alternative storage location but that leads to a high probability for collisions in the future and slows down the entire lookup for values not in the table as to tell a value is not in the table, you must look for it at all possible alternative storage locations, instead of usually just one.
The most common use for linked lists is when used as an intrusive linked list instead of as a data structure imo, where you have a procedure that recurses on the next item and does quite a bit of work at each level. Or when each node is large compared to cache anyway so that the cache misses is never an issue, but allowing inserts is. Inheritance hierarchies in dynamically typed languages are basically always a linked list of classes, but you rarely think of it as one. Same for chain maps, leaf nodes of B+ trees, and plenty of other things.
the main use case i have for single-linked lists is for immutable data structures. with a linked list you can immutably change the head of the list without having to copy the rest of the list. for example, in Haskell, linked lists is the default data structure because of these reasons. because of laziness in haskell a list is not always actually instantiated memory and can instead be an abstraction for loops, which eliminates many of the downsides. that said, if you want high performance in haskell it’s often worthwhile to replace lists with a more specialized and less flexible data structure, like immutable arrays (or sometimes even mutable arrays, but that’s more dangerous)
Right, usually you don't want a "list", you want actually a tree/split stack where several heads can share a parent, which is something arrays can't do.
I cannot remember when was the last time I used a linked list, I think C# contains a LinkedList but I am not sure and I have been using C# for 15+ years. I usually use arrays if known size and List if variable size or HashSet/Dictionary for indexed access. Linked lists are mostly used internally in other structures like the Dictionary.
That's a good rule of thumb, guessing List is a dynamic array underneath? Like I mention in the video, I rarely use linked lists. A few super specific optimizations, some memory allocators, some intrusive lists.
Wow, that table placement metaphor is excellent. I will be using that one forever now when explaining vector size vs capacity and why it's so much faster to allocate up front when size is known! Thank you
@@wonkothesane13 That's equivalent to the allocator having no sufficiently large free blocks, and needing to defragment the heap. Except the allocator, to save time, pushes all the tables together in advance, rather than just the table you need. This is fine for software, but in real life, paying customers would complain if you did that.
7:06 When you need a datastructure with insertion/removal on both ends circular buffers work pretty good. They also half the copied data on random insertion/deletion.
That's totally true, I often forget about circular buffers until I'm in a specific situation like the last time I used them was for an in-memory profiling thing.
In my experience, you hardly ever need to maintain order. Generally it'll be on output that you need the data sorted and sorting it once at the end is not only more than adequate, but the longer your program is processing for the more you'd be better off not maintaining order. One of the tricks I use for various data sets is to delete by swapping the element I want deleted with the last element and just decrementing the count.
Maintaining order is not too expensive as long as you use a data structure actually intended for it, like a BTree or an LSM tree. Sorting by inserting in a BTree has perfectly adequate performance in most languages, you just usually need a third party library for it for some reason
@@BosonCollider If we're talking about C, then I don't need a third party library. I'm perfectly fine using the one I made myself. As for using a tree at all, it depends on what you're doing with your data, and as always you have to consider locality of reference. If you need it accessed sequentially a lot and to allow lots of insertions and deletions, then you might actually be better off with a sparse array. It won't be perfect, but it'll be faster than a flat array and give better locality than a tree. I've just found that you rarely need sequential access outside of printing the data out, and running a sort function once at that time is perfectly acceptable.
I tend to think of Linked Lists as the fundamental unit of graph data structures. The usefulness isn't always apparent but you can build on the fundamentals they introduce and hybridize with other data structures to make very useful tailor-made graphs.
One thing that doesn't get brought up often enough is combining both: linked blocks of contiguous-in-memory arrays. Brodnik et al in 1999 uses this to provide list-like structures with worst case constant-time for all operations with the minimal amount of unused space that afaik should still have good cache locality (not considered in the paper iirc) for large enough arrays due to increasing block sizes.
Linked lists are nice for large structures that may take up an entire cache line with one element. There's no point preserving locality in that scenario, and it gives the allocator a bit more breathing room (although idk what magic modern allocators do so maybe not anymore). I find them helpful for embedded programming where cache isn't much of a thing. They also make pretty good message queues, although a circular buffer is arguably better for that.
@@simondev758 Oh yeah I forgot about prefetching. I guess linked lists really are hard to justify for userspace programs. With some application specific exceptions, at least. That's too bad, I'm quite fond of linked lists. Especially circular linked lists, which I think are an excellent example of how some clever thinking can eliminate basically all edge cases.
Another useful one is having a linked list of arrays. That way you can keep your old pointers, and you don't need to copy over the values if you need more space, and you might get more cache hits since more of it is bundled together than just one element. Also, if all the sections are the same size, or you store the size for each array in each node, you can more quickly traverse to a specific index than you can with a linked list.
For all the schooling and interview questions I have had about linked lists, I have NEVER in my 15 year career every had to use one. Array/List/Vector 100% of the time.
I think the most value that a linked list has to the vast majority of programmers is as a stepping stone for understanding trees and graphs, which are often represented the same way as linked lists, but with multiple "next" nodes.
One situation where I find linked lists very useful is for spatial partitioning in an environment where heap allocations are undesirable. With a linked list I could simply preallocate the linked list nodes and link them into the correct spatial nodes without having to worry about allocations from dynamic list expansions. The preallocation also helps with the cache locality to a certain degree.
one common pattern in low level code is to have objects which are part of many data structures, and in which some form of linking node element (list, tree, etc) can be very useful and where its very often the case that you need to track some objects membership of a set but also need to have that object made available in other structures. This can lead to an array-based method not really being that useful. I find that its usually pretty obvious which structure to use for a given problem.
I think the current convention is to create array lists. You allocate a contiguous block of memory of some size N, you create an interface which acts like a linked list, and behind the scenes it's just an array. If you fill up your array with data and still need more, you have to do the array copy, but each time you allocate more memory to increase the array capacity, you just double the size of the array. A neat thing with arrays is that you can implement linked lists, trees, and graphs using just arrays. The first array contains the data itself, and subsequent arrays which would be the "next" pointer to another element would really just be array indices. This lets you have cache coherency for complex data structures without having objects scattered all over heap memory.
@@simondev758 I like the way you're presenting it. It's not boring like most of the articles I've read on the topics. Edit: you're very pragmatic. I like that.
Linked Lists are so situational. It’s nice to be able to have the option to keep a node variable, for more inter-list operations. but I think the default for many languages keep the nodes private. *The example I’m thinking of is the game Snake- using the nodes as body links, and being able to slice up the snake body from a particular segment. Is so specific.
I have never used a link list before in practice. But I can think of a way, at least in old videos games. linking game objects together in something like C. Like if someone picks up object in game and on that object there is accessories. You could link them all together in a linked list. The depth and size of the list would not be that big so not much of a performance hit and its super dynamic so you can switch out variable memory sized objects out with ease.
Some other things that might be good to know: If you want to find some element (be it a direct comparison or via some particular predicate), with random access data like an array it's trivial to parallelize (you can just divide the contiguous data into N chunks and have multiple threads or whatever search their corresponding chunks). Likewise, if it's sorted data it's trivial to do a binary search to find the element with O(log n) complexity instead of the O(n) complexity a linked list traversal would entail. IMO, things like linked lists are almost only ever worth using in "intermediate" stages of processing in certain algorithms, during which reordering, insertions, removals, etc are frequent; then at the end the resulting data can be finalized by storing it in some contiguous block of memory (array or vector).
I wish I had started my career with you as a mentor. Your explanations are crystal clear and your presentation is entertaining. Thanks for taking the time to teach.
You can speed up linked lists by allocating space for each node in one chunk of memory and allocating new nodes in that chunk of memory, until it's full. Then it would be roughly equivalent to an array until it gets fragmented.
Inserting into some linked lists is very often slower than inserting into arrays because it has to allocate everytime. Arrays will most of the time have the memory allocated. You can preallocate linked lists but many implementation don't do that like STL. Tlr: insert is most often slower for a linked list as well except with large arrays where copy becomes more expensive than allocation. In those cases consider a deque.
I like your clear, very good explanation of a linked list without going into anything complex. As previous posters have pointed out, cache on modern CPUs tends not to work as well with linked lists these days. Another channel Computerphile, has a video that shows some of the computers back in the day without cache (a 68000 based Atari ST) performing better on a linked list. I think i recall the reason as, the execution time of the different instructions and... no cache on the CPU, all memory accesses are equal.
if you have a linked list allocated by an arena allocator, you may be able to get more cache hits, though you would get the disadvantage of having limited space.
5:00 > _"change previous nodes next, _*_THEN_*_ change your new node to next"_ little nitpicks here, the order is actually the reverse, first the new node is set to next using previous node, then previous node is changed to new one.
In my limited experience, I've never had a situation where you insert so much that you need to use that, so that's encouraging. Lots of those data structures out there, but I barely used any of them.
For me, they've really only popped up in very specific circumstances. I'm betting a lot of people can go through their entire careers without needing one over an array.
One point not mentioned: if your data elements represent items in a shop or restaurants on a map, you can easily reorder the elements to directly control in which order they will appear on the front end or be processed in some other order-sensitive operation. In an array, you can swap two primitives pretty easily, but if you want to move larger groups of elements around, you need temporary memory and some costly delete/insert operations, or it will be faster to replace the array entirely.
Linked lists can be very useful in specific scenarios, for some algorithms like Huffman code calculation and pathfinding. In the pathfinding example, it's obvious why linked lists are better, as you're constantly allocating and marking new sections as "verified" and you will eventually need to backtrack since you want a path. The same goes when you're calculating the Huffman code for something, as each node could have a "left" and a "right" pointer, and again you're only allocating until the algorithm finishes. But other than that, yeah linked lists aren't very useful in general.
Thanks for the demonstrating the code for traversing a linked list in all those languages. Python is my preference and I really appreciate you taking the time to include it!
there are different pros and cons for linked lists vs arrays - for example on a banked memory system where there is lots of non-contiguous memory blocks, then a linked list or even hybrid solution is really a must - there are so many videos and websites that make incorrect assumptions that all computers have the same architecture.
the main application is for functional languages. linked lists are the simplest and most efficient way of working with recursive functions operating on immutable data. They are the most basic data structure in lisp and haskell
As someone stated, on x86 arch it is not a good design pattern compared to arrays in terms of performance. It can be very useful though for some specific node manipulation, extendable to any generic node (not necessarily an array element). Then you can extend the pattern to have N vertices, and it gets really interesting.
I don't think you mentioned it in the video but another benefit of linked list arrays is that you aren't allocating a bunch of memory in advance "just in case" as one would do with arrays. Linked lists can dynamically grow and shrink with the number of entries in the list, where an array is practically immutable and once allocated and you need more items in it you have to grow it somehow. And you can't just blindly grow it, you have to make sure there's enough free room in memory to grow it, else you have to move the whole array and its contents to a free section of memory large enough. Another thing not mentioned is when each element in an array needs to be a size between X and Y bytes. Such as strings holding names. Do you want to brutishly limit the end user to only allow strings of length Y? What if their name is really long, unusually long? Wouldn't it be rude to not allow such a user to use his/her full name? ... On a side note, i've seen sites that PROHIBIT me from using passwords LONGER than a certain number of characters ... Seems secure and legit! ... Or do you want to be inclusive and allow names of say 512 characters long to cover any and all cases? You are now allocating half a kB per entry where most entries are no longer than 8-10 characters long. Such a waste of memory, such a waste of cache memory if the array is cached in L1 etc... Linked lists especially shine when the data they hold are of indeterminate size. Such as that can start off at ANY size and grow/shrink as they are used and abused. Linked lists CAN be coerced into working with hash maps in an efficient manner, negating many of the downsides to using linked lists in the first place. And object oriented languages simply don't work without lists of some sort. You simply can't do OOP well with fixed arrays... And much of their power comes from the fact they can allocate anything anytime on the heap and have built in garbage collection for when you really would struggle to keep track of all possible use cases. Programmers that insist on using arrays for are also the kind of programmers that are likely to unintentionally and ignorantly/obliviously create memory leaks. Whenever someone says "I made it in C because performance" i think to myself... But will it stand up to the test of time?
7:04 i'd like to mention that a circle buffer, which is just a vector with some extra logic, performs insertions and deletions at the end and start extremely fast, while retaining all the upsides of a normal vector
One place I found linked lists useful was in a C# app I had a situation where many threads needed to frequently read the list (always in-order reads) and a one thread would occasionally add or remove a node from the list. I couldn't afford the time to use a read/write lock or similar. So I used a simple linked list and just wrote the insertion/deletion logic so that a node being added was always fully initialized before modifying its parent to insert it into the list. Removing nodes wasn't a concern because that was a simple update of the parent's reference to point at the child of the node being removed. Ran like greased lightning compared to the old code that used locking. And I think that's the only time I've used linked lists in over a decade.
I love everyone chiming in with their "once in a decade" use of a pure linked list. I remember straining pretty hard to remember when I needed one for the video, glad to see that I'm not alone.
@@simondev758 In the "old days" when a C compiler came on two 5 1/4" floppies I did a lot more with writing linked lists, tree structures, etc. But these days there are so many good data structures that come with the language and its libraries it's a rare case when you need to roll your own. But still good to know how to because once in awhile...
Linked Lists are suited when you are tight on memory. An array/vector needs M+N contiguous memory when it grows: It needs to original memory and it needs memory thats bigger than the original memory for reallocation. When you have 2GB of memory for an array, you need 2GB+4GB (grow Factor of 2.0) of contiguous addresses when it needs to reallocate. A Linked List just allocates a node (with a bit more overhead per value) wherever it fits. The sweet spot is supposed to be a deque - it allocates small chunks of values like an array, but each chunk is linked via a linked list.
For 2 dimensional arrays - this is exactly what I do - dimension the array with spare space, if taken up, resize. This creates a super fast access and write, with exception of the ocassional resize. I have yested against lists and other methods, and this was by far the fastest method, especially for random access reading.
Allocating larger numbers of elements (usually called an unrolled linked list) makes this less of a problem. Essentially, you're linking arrays together, getting some of the benefits of both. Of course, it's always a tradeoff.
Seriously hardly someone talks about under the hood working of data structures, i request you please uncover all the abstraction which are present in programing language like cache friendliness (you've made a video on it), short circuits, sequence points, seriously knowing "how programing language and data structures works?" is very very interesting, and with your explanation it becomes more interesting.
@@GioRob I agree. I have watched some of his "game" logs and he is straight out brilliant. I love this low level stuff, myself coming from Assembly and Pascal in the early days (some Delphi stuff today) and Pascal where Record's with Procedural variables (pointers) used in linked lists with some help of arrays as for sorting on "properties" (before object's in Pascal)
@@bjarnieinarsson3472 brilliant stuff...I come at it from a completely different perspective...I mostly program games and ML models so generally use a mixture of Python, JS and C#...currently I've been doing a lot of three.js stuff (which a lot of his videos seem to focus on) but I find his low-level explanations truly fascinating...so much so that I've been considering giving Rust and WebAssembly a go 😂
@@simondev758 Hey Simon, I've sent you a message on Patreon asking for some advice - or maybe also a future video? Also looking forward to you adding things to your new website!
at the beginning I was mostly curious about who crabman is, but at the end I am just so grateful for real-life examples and real deep dive in the topic. I am constantly rewatching your videos, and putting the pieces together. thank you! and the "far away from the bathroom" joke was brilliant :D
One should note that long enough sequences are not going to fit in cache anyway, so in that situation it can be a good idea to use a linked list of vectors. Then you can, for example, insert at the beginning without re-writing the whole thing while getting similar cache benefits.
Another consideration: what is the lifetime of the average element in the list? How long until it is deleted or a new element inserted. In an array that can involve moving other elements around, which is not necessary in a linked list. Also consider when the order of insertion is important.
There is also the child of both -- I've seen them called b-buffers? -- where you have a linked list of chunks of an array. This is a lot better than a linked list but still only supports linear seek. Even better than this is a b-tree, an ordered tree of array chunks, which gives you logarithmic seek. That data structure is the foundation of almost all respectable databases :)
I remember once during a major embedded project a senior dev just basically implemented a linked list after trying to memory optimize out linked lists while trying to keep the same functionality, reliability, and maintainability he managed to save a single byte per entry and at the cost of quite a lot of program space and 140 extra clock cycles when navigating the list normally not a problem but we had 256k of flash and 48k of RAM on a 75 MHz clock on an already not super powerful cortex M3 core and RAM could have been (and was) saved elsewhere
Thank you for providing multiple code examples. I’m just starting out with CS and python is the only language I know really well. It’s such a small thing but it really helps a ton! :)
I wonder if anyone's made a linked list which keeps track of waypoints in the middle to speed up awkwardly late accesses. Like, upon adding a 25th element, you make a separate list indicating waypoint 1 is here and it's 25 elements after the last waypoint. Then if you want to access item 26, you just see that your waypoint list's first element is 25, so you start there and walk forward 1. Or if you want element 60, you walk up that list, see that the first waypoint is 25 after the beginning, and second waypoint is 30 after the second one, so you know that second one is 55, then you switch back to the main list and walk it from there. Upon insertion or deletion you need to update the waypoint list, but usually only one element (if you need to insert or delete an element from the waypoint list it'll be a bit more expensive) I think the ideal size of the waypoint list would be something like the square root of half the length of the list (counting the head of the list as a waypoint), so you'd get your first waypoint at the 8th element?
What i feel is that linked lists should be mostly avoided if possible in real life if someone is looking for performance. And here is is the reason- you want linked list to get that seet o(1) for insertion and deletion. But the important thing that we often ignore is that to insert or delete you first need to search. And at that point array just dominates. However i do feel that an linked list of fixed lenght arrays (preferably of cache line size)might be better than a vector to avoid the whole reallocation and copy. I will not go into details as it will turn out to be a big document. But the idea makes me think. My only personal problem with normal linked lists is that i feel storing a single value and keeping the datastruture too much fragmented in momory may not be suitable for a high performance application. That being said, for higher level languages that depend on garbage collection and reference for everything, it simply doesn't matter. I may be wrong though.
For insertion 5:02, when you cut the 1st node's next to point to the new 2nd node, you lose reference to the 3rd node (at least in the diagram, though ofc you can use a temp variable to keep reference). Ideally the 2nd node's next points to the 3rd node, and then the 1st node's next points to the new 2nd node so you don't have to do that, and you don't lose references on the way
The video just illustrates what needs to happen for insertion to occur, it doesn't explicitly spell out which temp vars you need to declare, etc. I generally assume that everyone can figure that out themselves.
Link lists have a lot of drawbacks. But moving everything from an array to a bigger array is also a pain. Can't we have a hybrid between the two? Eg. Fixed sized partitions of an array. You can have the first element to point to the previous partition and the last element to point to the next partition. You could also have a pointer table. It would be somewhat similar to a hash map. Unless you have a huge amount of insertion/deletion, it should be pretty optimal
Immutable singly linked lists have another advantage: They can share their tails. So if you find yourself getting a lot of lists with identical suffices, you can use linked lists to great effect, saving memory and copying. This happens for example with dynamic programming, where the answer to a partial problem is constructed from a smaller subproblem by appending something to the front.
Oh my god, this is AMAZING. You made such an advanced university topic into an enjoyable 10 minutes video. Incredible work, I can't wait for you to get into Binary Trees.
It is a very real choice when you have a parallel program or a distributed system. Cache locality takes a backseat and all that big-O gobbledygook is what matters. Cache misses into main memory are cheap compared to network overhead.
Linked lists are great for data structures which always grow but for which you don't have a clearly defined maximum size. They are very useful at low levels (ie assembly).
I ended up creating an expandable circular queue for my project over a linked list even before watching this video. Still, though, a linked list is a valid choice for elementary coding tests where time constraints on development are even more harsh than anything practical.
Another thing: If you have enough memory for a doubly linked list, you have enough memory for a tree structure like a map. And those are one of the most useful structures available.
Thanks for this video. I thought I knew all there’s to know about lists but now I understand that I have been overusing them quite a bit! I could have used static arrays with variable length to make my circles faster but I prioritized cleanliness(arbitrary I must say) of code to its effectiveness!
@@simondev758 I’m making a game with procedural generation. There are a lot of times I had to use different types of path finding algorithms and those definitely need lists unless I start using recursion… But other than those algorithms I’m sure nothing else specifically needs lists so I’m refactoring my code right now!^_^
Only time I've used a linked list, for my own projects, was for a scanline renderer once, back in the 90s, breaking up triangles into the lines, storing them on the scanline, sorting them etc etc etc. Was just playing around trying to make my own renderer on an Acorn.
Your videos are just such a blast to watch, i can feel the knowledge pouring into my brain and I would not have been as invested in things like LinkedList as much had I been tasked to read up on the topic in documentations
Were making a LInked LIst ADT in my CS class right now and it makes me feel better about the fact I was thinking I dont really know when this would be useful especially when C++ has the vector library and other languages have dynamic arrays by default.
Great video. Suggestion for thread safety at 5:04... Set the new node's "next" variable *before* insertion. Otherwise there is a brief moment where the linked list is unintentionally truncated.
People always forget the overhead of the memory allocator itself, which is on top of the sum of all nodes. Arrays can be broken up too, instead of allocating one big one, allocate several smaller ones for example and still have no real allocator overhead. Still almost no overhead. Then there are free lists, which work for both types then. There are so many variations that still have little overhead and are prefetcher friendly. All based on arrays obviously :)
In C# there are LinkLists, and then there are Lists, which is what everyone uses. I've never actually seen a LinkedList used, but they're there. I ran into an issue with Lists storing large amounts of ValueTypes. Every time a C# list runs out of space, it doubles the allocation. This is fine(?) for referenced objects, since those are much bigger anyway, but for an int? The end result is that is wastes possibly gigabytes of data for no good reason. Also, brutal massive lag spikes while gigabytes of memory are allocated in a single Add(). I ended up creating a custom List class that added an array of a fixed size when running out of space. This vastly improved both speed and memory consumption. I did run into the issue with removing values causing every other array needing to be modified. I still think I can improve that by changing how the data is indexed. This was for a web server that handled data analysis, btw. It may be a sin, but I generally avoid arrays like the plague unless it's very important.
This is still depending on the implementation of the linked list.. a linked list is an abstraction and the next pointers can be represented in so many ways that depend on what you need it for.. you can implement linked list such that it all nodes are local to the next nodes.. but it require some assumptions on the usage and some underlying preallocated size of memory to store the nodes in and an allocation/freeing scheme to fetch the placement of a new node.. it could implement a sorting of the node on freeing/allocation which is the same as sorting an array since all nodes are of fix size.. but then again this would depend on usage and implementation..
With a linked list you can keep a reference to a particular node that's stable across insertions/deletions. Also regarding the allocation thing, with an intrusive linked list the next pointer is stored within the object itself, so there's no allocation issue. Rather than having an array of pointers to the objects, you just have the objects that are themselves the nodes in the list. Going back to the first point, the objects won't move around as the list is modified, which isn't necessarily even possible for some objects.
"intrusive linked list" I think it's called "unrolled linked list". There's another video from a few days ago on the PrimeGen channel from one of the inventors of C++ that in practice, deletion of a node in a linked list is actually in practice (rather than in theory) slower than for an array (goes to @6:40 in the video here) despite the theoretical disadvantage of moving lots of elements in an array, due to caching.
@@raylopez99 The benefits of intrusive lists are the lack of memory to manage and no question of how to find the list element pointers given the object.
Back in my college days, I wasn't in C++ but C+ and Java+. Well I disilked linked lists mainly because my code for them never really worked properly and arrays were just so much easier to program. My instructor didn't like my code because he would comment I'm wasting too much memory allocation (reserving too much at a time). But then again my code executed faster once it was running. So I wonder, Arrays just seem to execute faster when you don't need to change the order of the information and just need to recall it. Also it helped me insert new variables far easier as long as I didn't go over the memory allocation. Though of course I could get overflow problems if I tried to put in a variable that needed more memory than what was reserved. xD I love receiving garbage output (sarcasm). but oh well I just changed the code to make the array bigger. Though I admit if my code was for someone else i wouldn't be there to dynamically change it.
The use I see to linked lists is not really for iterative and/or predictable vector size cases, the main asset of linked lists is that they can potentially reduce memory allocation time when several not known to preallocate insertions are made into a dynamic array. In the case of a dynamic array that has not enough space to insert one new item, it makes necessary to reserve an entirely new block of memory where every element, including the new one can be placed, copy the entire old block of memory into the new one, make the insertion, delete the old block of memory and reload it as possible into the cache memory. Not to talk about promoting memory fragmentation that will be a system’s performance issue. For small arrays it could be affordable but with large data sets it will require a lot of CPU cycles just for the system’s heap manager to look for such a big block of memory available to finish the new allocation. In this specific case, the performance given by linked lists is far better than dynamic arrays. To insert a new element you just need a small block of memory that can potentially be filled with memory fragmented blocks that have been probably been freed by another application. Overall, linked lists are perfectly avoidable at some cases, but cannot be ignored because will depend on the case of use.
A lot of this was a great rehash of college lectures I had back many years ago. One thing I wish you'd go more into detail is more on the graphics side as some of us web programmers never got the full whammy of how graphics pipelines work, specifically with either opengl or directx. I feel like programmers that were trained with that were highly specialized and optimized, similar to database programmers that are really good at writing complicated joins that isnt your standard run of the mill programming. Highlighting things like what gl.createprogram, or gl.bind and things like this, what they mean, and how all that boiler plate in your other example with the colored sphere lights I tried to watch but when examining your code I just didnt understand from a higher level what or why you were doing what you were doing. And to also reiterate, I think I can count on one hand how many linked lists I've ever used in programming, and in the 15 years in tech I've worked, I've worked primarily with javascript but also some c++, c#, and python. Bjarn Stroustrups book I recall him saying in it to default to vector as your first container of choice and if optimization is required, switch to a hash or linked list later on after testing.
@@simondev758 Hey thanks for replying! I know you're a new channel but your content is fantastic btw! (forgot to mention). I too tried your idea of a massive mmo using node, although my engine I made was a 2d one instead of 3d. Check it out if ya got time! :) th-cam.com/video/Kj0y_0F_JrY/w-d-xo.html
i really dont know why they are forcing us to use linked lists over and over again in university. i really dont like to use them, seems to me like a premature optimization before your project has even started. i once asked on unity-discord-server if anyone would recommend linked list for a faster computation and everyone aggreed, that linkedlist are basically useless in unity. ive learned alot from the channel. if you wanna gain performance: use async tasks, mulithreading and entities... but this doesnt go for the build pipeline of course.
An amazing series, Simon, big thanks! The visualizations you make while explaining things helps a lot. P.S, I think, the patreon link is missing from the description.
Array: access at index - O(1) Insert/delete at start - O(n) Insert/delete at end - O(1) Insert/delete from middle- O(n) Linked List: access at index - O(n) Insert/delete at start - O(1) Insert/delete at end - O(n) Insert/delete from middle - O(n)
Kinda, although a small hack for arrays gets faster deletes. Array delete at any index is O(1) if you don't care about preserving order, which in many gamedev situations is true. And O(n) for an array of contiguous memory vs O(n) for a standard linked list have very different performance characteristics on modern hardware.
If you enjoyed this, help support me: www.patreon.com/simondevyt
Want to see more videos like this. ❤️
Why did you thumbnail "Always use THIS"?
@@climatechangedoesntbargain9140 I don't remember what I was thinking, but full disclosure, I SUCK at making thumbnails. This one has an awful click through rate, so I gotta change it anyway.
You literally dont say why linked lists vs arrays is not a real choice.
On Modern x86, the most important thing for code optimization is cache. A cache miss is more expensive than a floating point divide. Arrays offer significantly better cache locality than linked lists. This means that they are almost always the better option on modern x86
100%
modern allocators will also store their memory on the heap sequentially, and the cpu doesn't cache just the bytes you need at a time, it caches the bytes ahead of it too. So when you're working with a linked list and you allocate nodes on the heap its likely that that memory is cached since its near so much other data.
@@minneelyyyy Possibly, but that'd only be true if you allocated the nodes up front.
@@minneelyyyy having to store a pointer as well makes them less cache friendly even if the nodes were to be stored sequentially
Well, at other end linked list guarantees you O(1) time complexity at each append operation instead of amortized O(1) in case of array list. This could be critical in some applications
I think in many ways linked lists are of pedagogical interest in computer science, partly because implementing them is often simple. It's a decent example for teaching recursion, it helps you understand other "node"-based structures like trees and graphs. In OS class or something with assembly, you might implement a free list, for which remembering linked lists comes in handy.
But again, that's all part of the conceptual background. Sometimes it helps to know some other option exists, if only to be confident that the option you're using is the better choice.
Or just bad teachers torturing students. Most CS programs don't teach anything useful to students. My 4-year programming degree was about as useful as if I'd done a "hello world" and then hopped onto one day at a real job. Any decent internship is way, way, way better than most 4-year degrees.
I had a CS prof, head of the department, IBM vet of 30 years. Loved his pointers. Whole exams were one code problem, and pages of pointer questions.
We had to use some weird compiler because our school got sold some garbage. When I tried to do linked lists I was doing "something" (prof could never explain) that was technically correct but unusual. This wasn't handled by our weird compiler, so it caused issues. The prof dug into it. 48 hours before my semester-long project was due, the prof handed me 12 pages of documentation he'd written. He was proposing a fix for C++ itself as I'd found an undocumented bug. He basically gave me high-level instructions to personally re-code the C++ language by hand to fix the error. All I had to do was re-code C++ itself. Implement my new language in the weird compiler. Then re-run my code which would definitely have more errors. And submit that in under 48 hours.
I'm glad I didn't own a gun.
I've worked in programming for a decade and literally never had to know what a pointer is in my whole career. And I'm a web developer, full-stack e-commerce, which is a very popular role covering many technologies.
@@KevinJDildonik I have to disagree with you, a CS major does not prepare you fully for a web development role, web dev is just a small fraction of CS. You're better off taking a software engineering major if you want it to be relevant to what you're working as.
Linked lists are optimal for some algorithms. Talking about data structures outside the context of an algorithm using them is nonsense. The video here might confuse, as without context or the right circumstances as he says, it's hard to understand data structure choice. Linked lists are a fundamental concept learned everywhere in the world.
@Jeffris (Suspicious Manifold) sorry, I replied to the wrong comment. It obviously doesn't even make sense I context to what you wrote which I agree with...
@@gregorymorse8423 All good.
From what I understand, memory is often pretty slow, especially compared with the processor. So rather than just fetching the data needed for the current operation, it instead gets a whole truckload of data at once including both the request and the data around it. Arrays exploit this to its full potential making data insertion and deletion much faster than it could be otherwise since it's moving entire blocks of the array rather than single elements. This alone often makes up for the theoretical savings of using a linked list.
Mostly yeah, insertion/deletion can be fast in an array, if you do an element swap rather than actually maintaining order. The rest is 100% right.
Yes, that's roughly right. The CPU has L1, L2, and L3 caches on the chip itself, and if you need to do a memory access, first it queries the L1 cache for the data. L1 is smallest in capacity, but fastest access time. If the data isn't in L1, it queries L2. L2 is a bit bigger capacity, but access time is slower than L1. Same with L3. If the data in question isn't in any of the L1-3 caches, then the CPU has to go out to main memory to fetch a "page" of memory. This is orders of magnitude slower than accessing data in the CPU cache. When this happens, you have a "cache miss". Linked lists are a series of nodes scattered all over the heap, so accessing each element in a linked list could, in the worst case, mean a cache miss for each element in the list. With an array, it's stored as a contiguous block of memory, so it's more likely that you'll load a page of memory into the cache and you won't have as many cache misses. Your array could still be larger than a page, or the array boundaries might overlap a page of memory, but at least your cache misses will be significantly lower and you'll get much better performance.
@@slayemin Exactly, the "truckload" in the array context basically includes most if not all of the array in the same delivery, while for a linked list, the delivery contains only a single node, _maybe_ a couple, alongside a whole heap of data that you don't care about.
I did however think that the CPU only requests a single cache line, which on x86_64 is only 64 bytes, rather than an entire page which is 4096 bytes. The latter would make the "truckload" analogy even more fitting.
This comment was so confusing at first, until you understand the context and the implied knowledge you need to have to understand this.
@@panjak323 But the list is O(n) just to reach the place you want to insert or delete from, and because of low level details like the cache and locality, that O(n) has a larger coefficient than the O(n) for inserting and removing from a dynamic array.
Overlapping/unaligned read/writes at least allows for slower vectorization. Traversing a limited list doesn't have _any_ opportunity for vectorization.
Overall, great overview. 99% of the time, dynamic arrays are better than linked lists. Even for queues, we can use circular arrays to implement deques which would usuall be better. However, it’s worth noting that when storing very large elements, it could be more performant to use linkedlists as they never have to reallocate and copy a bunch of elements over to the new buffer. The reallocation is obviously quite cheap for small types but for large structs with lots of data, it’s worth considering this cost. Additionally, some types disallow copying entirely, and so it would not be possible to store them in a vector. Finally, it’s worth mentioning that it’s often not too difficult to “magically” get to the correct linked list node because we usually return iterators/pointers to the new nodes as we insert them, which do
Definitely, there's a lot of nuance there that can't really be covered in a quickie video. I feel like a follow-up at some point is warranted.
Damn, I was just going to reply with this exact thing. There are pros and cons for everything in computer science. It's important not to be dogmatic, less you miss a more efficient solution because it doesn't fit within your mental framework. Remember when we all first started learning? Everything was possible at that point. Then we started listening to the nay sayers - oh, that's not efficient, oh don't ever use X, use Y instead, oh Y is very inefficient, you should use Z instead. Pretty soon you start developing dogma around all of that. It's important to always try to push the envelope. Current standards are important to know as well - mostly so you can get hired :P - but current standards change. I have been in this business professionally since the mid 90s (I was coding when I was 13 in the mid 80s when I taught myself assembler using MSDOS) and I can tell you with certainty that current standards have changed and they will change again.
In c++ you can still use vectors for non-copyable types, by making them “moveable”
> it’s worth noting that when storing very large elements, it could be more performant to use linkedlists as they never have to reallocate and copy
And that's why Unix-style filesystems (i-node, indirect block, higher-order indirect block, all that...) essentially use linked lists. 'Aha' moment for me; thanks
@@smorrow Right, if you're going to store big arrays of bytes, you want to store them either in a linked list, or as an array of pointers to the big arrays. Or both at the same time, as in B+ trees
The most common usage for lined lists are hashtables. If you implement a hashtable and you get a collision, the easiest, yet still efficient way for handling it is to replace the value with a linked list of values. Of course, that will get slow as your linked list grows but if that happens, you have too many collisions anyway and then either your hashing is bad or your hashtable is too small ("too loaded"). The alternatives to a linked list would be using an array but that will buy you little if you plan to have 2 at most 3 collisions before you decide to resize and rehash the table or use an alternative storage location but that leads to a high probability for collisions in the future and slows down the entire lookup for values not in the table as to tell a value is not in the table, you must look for it at all possible alternative storage locations, instead of usually just one.
I have a video on hash tables if you're interested
The most common use for linked lists is when used as an intrusive linked list instead of as a data structure imo, where you have a procedure that recurses on the next item and does quite a bit of work at each level. Or when each node is large compared to cache anyway so that the cache misses is never an issue, but allowing inserts is.
Inheritance hierarchies in dynamically typed languages are basically always a linked list of classes, but you rarely think of it as one. Same for chain maps, leaf nodes of B+ trees, and plenty of other things.
the main use case i have for single-linked lists is for immutable data structures. with a linked list you can immutably change the head of the list without having to copy the rest of the list.
for example, in Haskell, linked lists is the default data structure because of these reasons. because of laziness in haskell a list is not always actually instantiated memory and can instead be an abstraction for loops, which eliminates many of the downsides. that said, if you want high performance in haskell it’s often worthwhile to replace lists with a more specialized and less flexible data structure, like immutable arrays (or sometimes even mutable arrays, but that’s more dangerous)
Right, usually you don't want a "list", you want actually a tree/split stack where several heads can share a parent, which is something arrays can't do.
I cannot remember when was the last time I used a linked list, I think C# contains a LinkedList but I am not sure and I have been using C# for 15+ years. I usually use arrays if known size and List if variable size or HashSet/Dictionary for indexed access.
Linked lists are mostly used internally in other structures like the Dictionary.
That's a good rule of thumb, guessing List is a dynamic array underneath?
Like I mention in the video, I rarely use linked lists. A few super specific optimizations, some memory allocators, some intrusive lists.
Wow, that table placement metaphor is excellent. I will be using that one forever now when explaining vector size vs capacity and why it's so much faster to allocate up front when size is known!
Thank you
The restaurant tables analogy has got to be the best analogy for arrays in memory I've ever heard.
The only flaw is that it ignores the most common scenario (in restaurants): the host just grabs a nearby table and pushes it next to yours
@wonkothesane13 what trashy places are you eating at? Jk lol, but seriously, that's kinda stretching it. I think the point was very clear.
@@rl6382 *working at, and nowhere fancy that's for sure
@wonkothesane13 awww 😅😔 It's okay you are a good person so I hope you are atleast treated well. Customer service is TERRIBLE.
@@wonkothesane13 That's equivalent to the allocator having no sufficiently large free blocks, and needing to defragment the heap. Except the allocator, to save time, pushes all the tables together in advance, rather than just the table you need. This is fine for software, but in real life, paying customers would complain if you did that.
7:06
When you need a datastructure with insertion/removal on both ends circular buffers work pretty good.
They also half the copied data on random insertion/deletion.
That's totally true, I often forget about circular buffers until I'm in a specific situation like the last time I used them was for an in-memory profiling thing.
In my experience, you hardly ever need to maintain order. Generally it'll be on output that you need the data sorted and sorting it once at the end is not only more than adequate, but the longer your program is processing for the more you'd be better off not maintaining order. One of the tricks I use for various data sets is to delete by swapping the element I want deleted with the last element and just decrementing the count.
Maintaining order is not too expensive as long as you use a data structure actually intended for it, like a BTree or an LSM tree. Sorting by inserting in a BTree has perfectly adequate performance in most languages, you just usually need a third party library for it for some reason
@@BosonCollider If we're talking about C, then I don't need a third party library. I'm perfectly fine using the one I made myself. As for using a tree at all, it depends on what you're doing with your data, and as always you have to consider locality of reference. If you need it accessed sequentially a lot and to allow lots of insertions and deletions, then you might actually be better off with a sparse array. It won't be perfect, but it'll be faster than a flat array and give better locality than a tree. I've just found that you rarely need sequential access outside of printing the data out, and running a sort function once at that time is perfectly acceptable.
I tend to think of Linked Lists as the fundamental unit of graph data structures. The usefulness isn't always apparent but you can build on the fundamentals they introduce and hybridize with other data structures to make very useful tailor-made graphs.
Absolutely
One thing that doesn't get brought up often enough is combining both: linked blocks of contiguous-in-memory arrays. Brodnik et al in 1999 uses this to provide list-like structures with worst case constant-time for all operations with the minimal amount of unused space that afaik should still have good cache locality (not considered in the paper iirc) for large enough arrays due to increasing block sizes.
Linked lists are nice for large structures that may take up an entire cache line with one element. There's no point preserving locality in that scenario, and it gives the allocator a bit more breathing room (although idk what magic modern allocators do so maybe not anymore). I find them helpful for embedded programming where cache isn't much of a thing. They also make pretty good message queues, although a circular buffer is arguably better for that.
They can still trip up the prefetcher for subsequent requests if you're iterating the array
@@simondev758 Oh yeah I forgot about prefetching. I guess linked lists really are hard to justify for userspace programs. With some application specific exceptions, at least.
That's too bad, I'm quite fond of linked lists. Especially circular linked lists, which I think are an excellent example of how some clever thinking can eliminate basically all edge cases.
Another useful one is having a linked list of arrays. That way you can keep your old pointers, and you don't need to copy over the values if you need more space, and you might get more cache hits since more of it is bundled together than just one element. Also, if all the sections are the same size, or you store the size for each array in each node, you can more quickly traverse to a specific index than you can with a linked list.
For all the schooling and interview questions I have had about linked lists, I have NEVER in my 15 year career every had to use one. Array/List/Vector 100% of the time.
It would be very interesting to hear your backstory. You seem like someone with a lot of experience and knowledge in different areas of software.
I'll do a video on that, it's on my TODO list. Summary is: Graphics/optimization in gamedev, small indie company owner, Google
@@simondev758 Thanks for taking your time to reply. Looking forward to hear it !
@@simondev758 Thats a lot, more or less the career path I have in mind, maybe not in that order =P
I'm not so sure about it. 5:02 the guy just lost half of his linked list....
@@rukasuigh5683 It's not like he's not saving the next address.
I think the most value that a linked list has to the vast majority of programmers is as a stepping stone for understanding trees and graphs, which are often represented the same way as linked lists, but with multiple "next" nodes.
Agreed, the concept of a "node" is fundamental for understanding so many data strutures.
One situation where I find linked lists very useful is for spatial partitioning in an environment where heap allocations are undesirable. With a linked list I could simply preallocate the linked list nodes and link them into the correct spatial nodes without having to worry about allocations from dynamic list expansions. The preallocation also helps with the cache locality to a certain degree.
one common pattern in low level code is to have objects which are part of many data structures, and in which some form of linking node element (list, tree, etc) can be very useful and where its very often the case that you need to track some objects membership of a set but also need to have that object made available in other structures. This can lead to an array-based method not really being that useful. I find that its usually pretty obvious which structure to use for a given problem.
Totally want to make a video on intrusive linked lists, kinda the except to my "just use an array" rule.
I think the current convention is to create array lists. You allocate a contiguous block of memory of some size N, you create an interface which acts like a linked list, and behind the scenes it's just an array. If you fill up your array with data and still need more, you have to do the array copy, but each time you allocate more memory to increase the array capacity, you just double the size of the array.
A neat thing with arrays is that you can implement linked lists, trees, and graphs using just arrays. The first array contains the data itself, and subsequent arrays which would be the "next" pointer to another element would really just be array indices. This lets you have cache coherency for complex data structures without having objects scattered all over heap memory.
You absolutely should make a video with that interview question you can't ask anymore!
Heh maybe, honestly it's been covered 1000x on sites like leetcode at this point. I'm not sure I bring anything new to the table.
@@simondev758 I like the way you're presenting it. It's not boring like most of the articles I've read on the topics.
Edit: you're very pragmatic. I like that.
@@simondev758 I think it can still be interesting to hear your point of view.
@@simondev758 it’s DEF an LRU cache
@@simondev758 you must ,guide me as well ,
I am 2nd year college student ,
Learning from here n there
Linked Lists are so situational. It’s nice to be able to have the option to keep a node variable, for more inter-list operations.
but I think the default for many languages keep the nodes private.
*The example I’m thinking of is the game Snake- using the nodes as body links, and being able to slice up the snake body from a particular segment. Is so specific.
I have never used a link list before in practice. But I can think of a way, at least in old videos games. linking game objects together in something like C. Like if someone picks up object in game and on that object there is accessories. You could link them all together in a linked list. The depth and size of the list would not be that big so not much of a performance hit and its super dynamic so you can switch out variable memory sized objects out with ease.
I wrote a similar game once, and used actual class objects, with a "bag" of pointers to those objects.
Some other things that might be good to know: If you want to find some element (be it a direct comparison or via some particular predicate), with random access data like an array it's trivial to parallelize (you can just divide the contiguous data into N chunks and have multiple threads or whatever search their corresponding chunks). Likewise, if it's sorted data it's trivial to do a binary search to find the element with O(log n) complexity instead of the O(n) complexity a linked list traversal would entail. IMO, things like linked lists are almost only ever worth using in "intermediate" stages of processing in certain algorithms, during which reordering, insertions, removals, etc are frequent; then at the end the resulting data can be finalized by storing it in some contiguous block of memory (array or vector).
Very good points, I feel like I need a follow-up on this video one day with more nuanced use of each like this.
@@simondev758 Looking forward to it. Keep up the excellent content!
Perfect timing! I have exam on this in 3 days. Good repetition.
Good luck!
I wish I had started my career with you as a mentor. Your explanations are crystal clear and your presentation is entertaining. Thanks for taking the time to teach.
Let me know if there are other subjects you want me to cover!
You can speed up linked lists by allocating space for each node in one chunk of memory and allocating new nodes in that chunk of memory, until it's full. Then it would be roughly equivalent to an array until it gets fragmented.
Inserting into some linked lists is very often slower than inserting into arrays because it has to allocate everytime. Arrays will most of the time have the memory allocated. You can preallocate linked lists but many implementation don't do that like STL. Tlr: insert is most often slower for a linked list as well except with large arrays where copy becomes more expensive than allocation. In those cases consider a deque.
I like your clear, very good explanation of a linked list without going into anything complex. As previous posters have pointed out, cache on modern CPUs tends not to work as well with linked lists these days.
Another channel Computerphile, has a video that shows some of the computers back in the day without cache (a 68000 based Atari ST) performing better on a linked list. I think i recall the reason as, the execution time of the different instructions and... no cache on the CPU, all memory accesses are equal.
if you have a linked list allocated by an arena allocator, you may be able to get more cache hits, though you would get the disadvantage of having limited space.
Memory optimization is definitely an area that you target when doing real world stuff
5:00 > _"change previous nodes next, _*_THEN_*_ change your new node to next"_
little nitpicks here, the order is actually the reverse, first the new node is set to next using previous node, then previous node is changed to new one.
In my limited experience, I've never had a situation where you insert so much that you need to use that, so that's encouraging. Lots of those data structures out there, but I barely used any of them.
For me, they've really only popped up in very specific circumstances. I'm betting a lot of people can go through their entire careers without needing one over an array.
One point not mentioned: if your data elements represent items in a shop or restaurants on a map, you can easily reorder the elements to directly control in which order they will appear on the front end or be processed in some other order-sensitive operation. In an array, you can swap two primitives pretty easily, but if you want to move larger groups of elements around, you need temporary memory and some costly delete/insert operations, or it will be faster to replace the array entirely.
Linked lists can be very useful in specific scenarios, for some algorithms like Huffman code calculation and pathfinding.
In the pathfinding example, it's obvious why linked lists are better, as you're constantly allocating and marking new sections as "verified" and you will eventually need to backtrack since you want a path.
The same goes when you're calculating the Huffman code for something, as each node could have a "left" and a "right" pointer, and again you're only allocating until the algorithm finishes.
But other than that, yeah linked lists aren't very useful in general.
Thanks for the demonstrating the code for traversing a linked list in all those languages. Python is my preference and I really appreciate you taking the time to include it!
there are different pros and cons for linked lists vs arrays - for example on a banked memory system where there is lots of non-contiguous memory blocks, then a linked list or even hybrid solution is really a must - there are so many videos and websites that make incorrect assumptions that all computers have the same architecture.
the main application is for functional languages. linked lists are the simplest and most efficient way of working with recursive functions operating on immutable data. They are the most basic data structure in lisp and haskell
As someone stated, on x86 arch it is not a good design pattern compared to arrays in terms of performance. It can be very useful though for some specific node manipulation, extendable to any generic node (not necessarily an array element). Then you can extend the pattern to have N vertices, and it gets really interesting.
I don't think you mentioned it in the video but another benefit of linked list arrays is that you aren't allocating a bunch of memory in advance "just in case" as one would do with arrays.
Linked lists can dynamically grow and shrink with the number of entries in the list, where an array is practically immutable and once allocated and you need more items in it you have to grow it somehow. And you can't just blindly grow it, you have to make sure there's enough free room in memory to grow it, else you have to move the whole array and its contents to a free section of memory large enough.
Another thing not mentioned is when each element in an array needs to be a size between X and Y bytes. Such as strings holding names.
Do you want to brutishly limit the end user to only allow strings of length Y? What if their name is really long, unusually long? Wouldn't it be rude to not allow such a user to use his/her full name?
... On a side note, i've seen sites that PROHIBIT me from using passwords LONGER than a certain number of characters ... Seems secure and legit! ...
Or do you want to be inclusive and allow names of say 512 characters long to cover any and all cases? You are now allocating half a kB per entry where most entries are no longer than 8-10 characters long. Such a waste of memory, such a waste of cache memory if the array is cached in L1 etc...
Linked lists especially shine when the data they hold are of indeterminate size. Such as that can start off at ANY size and grow/shrink as they are used and abused.
Linked lists CAN be coerced into working with hash maps in an efficient manner, negating many of the downsides to using linked lists in the first place.
And object oriented languages simply don't work without lists of some sort. You simply can't do OOP well with fixed arrays...
And much of their power comes from the fact they can allocate anything anytime on the heap and have built in garbage collection for when you really would struggle to keep track of all possible use cases.
Programmers that insist on using arrays for are also the kind of programmers that are likely to unintentionally and ignorantly/obliviously create memory leaks.
Whenever someone says "I made it in C because performance" i think to myself... But will it stand up to the test of time?
7:04 i'd like to mention that a circle buffer, which is just a vector with some extra logic, performs insertions and deletions at the end and start extremely fast, while retaining all the upsides of a normal vector
A tree of linked lists of arrays !
The best data structure ever, or as they call it, the dictionary, or bucket-list.
I am an aspiring game developer from Nigeria and I really learn alot from this channel...
One place I found linked lists useful was in a C# app I had a situation where many threads needed to frequently read the list (always in-order reads) and a one thread would occasionally add or remove a node from the list. I couldn't afford the time to use a read/write lock or similar. So I used a simple linked list and just wrote the insertion/deletion logic so that a node being added was always fully initialized before modifying its parent to insert it into the list. Removing nodes wasn't a concern because that was a simple update of the parent's reference to point at the child of the node being removed. Ran like greased lightning compared to the old code that used locking. And I think that's the only time I've used linked lists in over a decade.
I love everyone chiming in with their "once in a decade" use of a pure linked list. I remember straining pretty hard to remember when I needed one for the video, glad to see that I'm not alone.
@@simondev758 In the "old days" when a C compiler came on two 5 1/4" floppies I did a lot more with writing linked lists, tree structures, etc. But these days there are so many good data structures that come with the language and its libraries it's a rare case when you need to roll your own. But still good to know how to because once in awhile...
i hope you will continue this series
Linked Lists are suited when you are tight on memory.
An array/vector needs M+N contiguous memory when it grows: It needs to original memory and it needs memory thats bigger than the original memory for reallocation.
When you have 2GB of memory for an array, you need 2GB+4GB (grow Factor of 2.0) of contiguous addresses when it needs to reallocate.
A Linked List just allocates a node (with a bit more overhead per value) wherever it fits.
The sweet spot is supposed to be a deque - it allocates small chunks of values like an array, but each chunk is linked via a linked list.
arrays are fixed length tho
For 2 dimensional arrays - this is exactly what I do - dimension the array with spare space, if taken up, resize. This creates a super fast access and write, with exception of the ocassional resize. I have yested against lists and other methods, and this was by far the fastest method, especially for random access reading.
Allocating larger numbers of elements (usually called an unrolled linked list) makes this less of a problem.
Essentially, you're linking arrays together, getting some of the benefits of both. Of course, it's always a tradeoff.
Seriously hardly someone talks about under the hood working of data structures, i request you please uncover all the abstraction which are present in programing language like cache friendliness (you've made a video on it), short circuits, sequence points, seriously knowing "how programing language and data structures works?" is very very interesting, and with your explanation it becomes more interesting.
Great author.. with real knowledge! Not a copycat as most of YT's are..
underrated comment
@@GioRob I agree. I have watched some of his "game" logs and he is straight out brilliant. I love this low level stuff, myself coming from Assembly and Pascal in the early days (some Delphi stuff today) and Pascal where Record's with Procedural variables (pointers) used in linked lists with some help of arrays as for sorting on "properties" (before object's in Pascal)
@@bjarnieinarsson3472 brilliant stuff...I come at it from a completely different perspective...I mostly program games and ML models so generally use a mixture of Python, JS and C#...currently I've been doing a lot of three.js stuff (which a lot of his videos seem to focus on) but I find his low-level explanations truly fascinating...so much so that I've been considering giving Rust and WebAssembly a go 😂
Thanks! I try to inject a bit extra, cover more ground, or add more concrete examples and reasoning, that I don't see covered in other videos.
@@simondev758 Hey Simon, I've sent you a message on Patreon asking for some advice - or maybe also a future video?
Also looking forward to you adding things to your new website!
So glad I came across this channel. Such a good pool of knowledge and experience!! 👍👍👍
at the beginning I was mostly curious about who crabman is, but at the end I am just so grateful for real-life examples and real deep dive in the topic. I am constantly rewatching your videos, and putting the pieces together. thank you! and the "far away from the bathroom" joke was brilliant :D
Hah that name is like a weird mishmash of a show I kinda liked a while back "My Name is Earl", and a comic strip I liked "Red Meat"
One should note that long enough sequences are not going to fit in cache anyway, so in that situation it can be a good idea to use a linked list of vectors. Then you can, for example, insert at the beginning without re-writing the whole thing while getting similar cache benefits.
Another consideration: what is the lifetime of the average element in the list? How long until it is deleted or a new element inserted. In an array that can involve moving other elements around, which is not necessary in a linked list. Also consider when the order of insertion is important.
You are the first person I've seen recommending someone to learn about modern processor cache shenanigans before learning about linked lists lol
I know all this allready but I still watch because your voice and explaination is so good
There is also the child of both -- I've seen them called b-buffers? -- where you have a linked list of chunks of an array. This is a lot better than a linked list but still only supports linear seek.
Even better than this is a b-tree, an ordered tree of array chunks, which gives you logarithmic seek. That data structure is the foundation of almost all respectable databases :)
so basically java's ArrayList?
I remember once during a major embedded project a senior dev just basically implemented a linked list after trying to memory optimize out linked lists while trying to keep the same functionality, reliability, and maintainability
he managed to save a single byte per entry and at the cost of quite a lot of program space and 140 extra clock cycles when navigating the list
normally not a problem but we had 256k of flash and 48k of RAM on a 75 MHz clock on an already not super powerful cortex M3 core and RAM could have been (and was) saved elsewhere
Hah, which is why I took the "probably" not needed, instead of a blanket statement.
One thing should be noted, that you need the bidirectional nodes for fast insertion and deletion.
Here I am looking at this video again after 1 year and still enjoying it
Thank you for providing multiple code examples. I’m just starting out with CS and python is the only language I know really well. It’s such a small thing but it really helps a ton! :)
I didn't know needed more CS videos narrated by someone with the voice of a grizzled artist who paints with oil but here I am.
I wonder if anyone's made a linked list which keeps track of waypoints in the middle to speed up awkwardly late accesses. Like, upon adding a 25th element, you make a separate list indicating waypoint 1 is here and it's 25 elements after the last waypoint. Then if you want to access item 26, you just see that your waypoint list's first element is 25, so you start there and walk forward 1. Or if you want element 60, you walk up that list, see that the first waypoint is 25 after the beginning, and second waypoint is 30 after the second one, so you know that second one is 55, then you switch back to the main list and walk it from there.
Upon insertion or deletion you need to update the waypoint list, but usually only one element (if you need to insert or delete an element from the waypoint list it'll be a bit more expensive)
I think the ideal size of the waypoint list would be something like the square root of half the length of the list (counting the head of the list as a waypoint), so you'd get your first waypoint at the 8th element?
What i feel is that linked lists should be mostly avoided if possible in real life if someone is looking for performance. And here is is the reason- you want linked list to get that seet o(1) for insertion and deletion. But the important thing that we often ignore is that to insert or delete you first need to search. And at that point array just dominates. However i do feel that an linked list of fixed lenght arrays (preferably of cache line size)might be better than a vector to avoid the whole reallocation and copy. I will not go into details as it will turn out to be a big document. But the idea makes me think. My only personal problem with normal linked lists is that i feel storing a single value and keeping the datastruture too much fragmented in momory may not be suitable for a high performance application. That being said, for higher level languages that depend on garbage collection and reference for everything, it simply doesn't matter.
I may be wrong though.
For insertion 5:02, when you cut the 1st node's next to point to the new 2nd node, you lose reference to the 3rd node (at least in the diagram, though ofc you can use a temp variable to keep reference). Ideally the 2nd node's next points to the 3rd node, and then the 1st node's next points to the new 2nd node so you don't have to do that, and you don't lose references on the way
The video just illustrates what needs to happen for insertion to occur, it doesn't explicitly spell out which temp vars you need to declare, etc. I generally assume that everyone can figure that out themselves.
@@simondev758 No, it's a programming error.
Youre literally a king amongst men keep up the awesome content
Link lists have a lot of drawbacks. But moving everything from an array to a bigger array is also a pain. Can't we have a hybrid between the two? Eg. Fixed sized partitions of an array. You can have the first element to point to the previous partition and the last element to point to the next partition. You could also have a pointer table. It would be somewhat similar to a hash map. Unless you have a huge amount of insertion/deletion, it should be pretty optimal
Immutable singly linked lists have another advantage: They can share their tails. So if you find yourself getting a lot of lists with identical suffices, you can use linked lists to great effect, saving memory and copying. This happens for example with dynamic programming, where the answer to a partial problem is constructed from a smaller subproblem by appending something to the front.
Oh my god, this is AMAZING. You made such an advanced university topic into an enjoyable 10 minutes video. Incredible work, I can't wait for you to get into Binary Trees.
I'll probably take a run at algorithmic analysis next before moving too far into more data structures.
This is advanced? It's one of the first things I learned about when learning cpp. Although nobody can seem to explain things properly like Simon can
This is something I learned in my first CS class in college...
IDK what they're doing where your at but i learnt this at 16 in the UK
I quite literally knew this since I was 12
It is a very real choice when you have a parallel program or a distributed system. Cache locality takes a backseat and all that big-O gobbledygook is what matters. Cache misses into main memory are cheap compared to network overhead.
Linked lists are great for data structures which always grow but for which you don't have a clearly defined maximum size. They are very useful at low levels (ie assembly).
This video is excellent. Thanks for the quality content!
This series is seriously underrated!
I ended up creating an expandable circular queue for my project over a linked list even before watching this video. Still, though, a linked list is a valid choice for elementary coding tests where time constraints on development are even more harsh than anything practical.
please make more. This content is really good
Another thing: If you have enough memory for a doubly linked list, you have enough memory for a tree structure like a map. And those are one of the most useful structures available.
Thanks for this video. I thought I knew all there’s to know about lists but now I understand that I have been overusing them quite a bit!
I could have used static arrays with variable length to make my circles faster but I prioritized cleanliness(arbitrary I must say) of code to its effectiveness!
Dynamic arrays probably cover most use cases. I've legit needed linked lists a few times, in 20 years.
@@simondev758
I’m making a game with procedural generation. There are a lot of times I had to use different types of path finding algorithms and those definitely need lists unless I start using recursion… But other than those algorithms I’m sure nothing else specifically needs lists so I’m refactoring my code right now!^_^
Only time I've used a linked list, for my own projects, was for a scanline renderer once, back in the 90s, breaking up triangles into the lines, storing them on the scanline, sorting them etc etc etc. Was just playing around trying to make my own renderer on an Acorn.
Great teaching style...would love to see a video on faang interviews and how to solve and prepare for the questions.
Your videos are just such a blast to watch, i can feel the knowledge pouring into my brain and I would not have been as invested in things like LinkedList as much had I been tasked to read up on the topic in documentations
Sweet, let me know if you have suggestions too!
Were making a LInked LIst ADT in my CS class right now and it makes me feel better about the fact I was thinking I dont really know when this would be useful especially when C++ has the vector library and other languages have dynamic arrays by default.
Hopefully this answered it :)
Great video. Suggestion for thread safety at 5:04... Set the new node's "next" variable *before* insertion. Otherwise there is a brief moment where the linked list is unintentionally truncated.
True, although if multiple threads are accessing the list simultaneously, it's not going to be threadsafe either way.
People always forget the overhead of the memory allocator itself, which is on top of the sum of all nodes. Arrays can be broken up too, instead of allocating one big one, allocate several smaller ones for example and still have no real allocator overhead.
Still almost no overhead.
Then there are free lists, which work for both types then.
There are so many variations that still have little overhead and are prefetcher friendly.
All based on arrays obviously :)
In C# there are LinkLists, and then there are Lists, which is what everyone uses. I've never actually seen a LinkedList used, but they're there.
I ran into an issue with Lists storing large amounts of ValueTypes. Every time a C# list runs out of space, it doubles the allocation. This is fine(?) for referenced objects, since those are much bigger anyway, but for an int? The end result is that is wastes possibly gigabytes of data for no good reason. Also, brutal massive lag spikes while gigabytes of memory are allocated in a single Add().
I ended up creating a custom List class that added an array of a fixed size when running out of space. This vastly improved both speed and memory consumption. I did run into the issue with removing values causing every other array needing to be modified. I still think I can improve that by changing how the data is indexed.
This was for a web server that handled data analysis, btw. It may be a sin, but I generally avoid arrays like the plague unless it's very important.
This is still depending on the implementation of the linked list.. a linked list is an abstraction and the next pointers can be represented in so many ways that depend on what you need it for.. you can implement linked list such that it all nodes are local to the next nodes.. but it require some assumptions on the usage and some underlying preallocated size of memory to store the nodes in and an allocation/freeing scheme to fetch the placement of a new node.. it could implement a sorting of the node on freeing/allocation which is the same as sorting an array since all nodes are of fix size.. but then again this would depend on usage and implementation..
With a linked list you can keep a reference to a particular node that's stable across insertions/deletions. Also regarding the allocation thing, with an intrusive linked list the next pointer is stored within the object itself, so there's no allocation issue. Rather than having an array of pointers to the objects, you just have the objects that are themselves the nodes in the list. Going back to the first point, the objects won't move around as the list is modified, which isn't necessarily even possible for some objects.
"intrusive linked list" I think it's called "unrolled linked list". There's another video from a few days ago on the PrimeGen channel from one of the inventors of C++ that in practice, deletion of a node in a linked list is actually in practice (rather than in theory) slower than for an array (goes to @6:40 in the video here) despite the theoretical disadvantage of moving lots of elements in an array, due to caching.
@@raylopez99 The benefits of intrusive lists are the lack of memory to manage and no question of how to find the list element pointers given the object.
If I needed stable pointers to array elements I'd use indirect indexing with an array.
Back in my college days, I wasn't in C++ but C+ and Java+.
Well I disilked linked lists mainly because my code for them never really worked properly and arrays were just so much easier to program.
My instructor didn't like my code because he would comment I'm wasting too much memory allocation (reserving too much at a time).
But then again my code executed faster once it was running. So I wonder, Arrays just seem to execute faster when you don't need to change the order of the information and just need to recall it.
Also it helped me insert new variables far easier as long as I didn't go over the memory allocation. Though of course I could get overflow problems if I tried to put in a variable that needed more memory than what was reserved. xD I love receiving garbage output (sarcasm).
but oh well I just changed the code to make the array bigger. Though I admit if my code was for someone else i wouldn't be there to dynamically change it.
The use I see to linked lists is not really for iterative and/or predictable vector size cases, the main asset of linked lists is that they can potentially reduce memory allocation time when several not known to preallocate insertions are made into a dynamic array.
In the case of a dynamic array that has not enough space to insert one new item, it makes necessary to reserve an entirely new block of memory where every element, including the new one can be placed, copy the entire old block of memory into the new one, make the insertion, delete the old block of memory and reload it as possible into the cache memory. Not to talk about promoting memory fragmentation that will be a system’s performance issue.
For small arrays it could be affordable but with large data sets it will require a lot of CPU cycles just for the system’s heap manager to look for such a big block of memory available to finish the new allocation.
In this specific case, the performance given by linked lists is far better than dynamic arrays. To insert a new element you just need a small block of memory that can potentially be filled with memory fragmented blocks that have been probably been freed by another application.
Overall, linked lists are perfectly avoidable at some cases, but cannot be ignored because will depend on the case of use.
Great explanation! I love how you compared it to tables at a restaurant.
A lot of this was a great rehash of college lectures I had back many years ago.
One thing I wish you'd go more into detail is more on the graphics side as some of us web programmers never got the full whammy of how graphics pipelines work, specifically with either opengl or directx. I feel like programmers that were trained with that were highly specialized and optimized, similar to database programmers that are really good at writing complicated joins that isnt your standard run of the mill programming. Highlighting things like what gl.createprogram, or gl.bind and things like this, what they mean, and how all that boiler plate in your other example with the colored sphere lights I tried to watch but when examining your code I just didnt understand from a higher level what or why you were doing what you were doing.
And to also reiterate, I think I can count on one hand how many linked lists I've ever used in programming, and in the 15 years in tech I've worked, I've worked primarily with javascript but also some c++, c#, and python. Bjarn Stroustrups book I recall him saying in it to default to vector as your first container of choice and if optimization is required, switch to a hash or linked list later on after testing.
Ooh that could be fun for a video, I'll see how it fits in with everything else.
That's good advice, it's generally my default container too.
@@simondev758 Hey thanks for replying! I know you're a new channel but your content is fantastic btw! (forgot to mention).
I too tried your idea of a massive mmo using node, although my engine I made was a 2d one instead of 3d.
Check it out if ya got time! :)
th-cam.com/video/Kj0y_0F_JrY/w-d-xo.html
i really dont know why they are forcing us to use linked lists over and over again in university. i really dont like to use them, seems to me like a premature optimization before your project has even started. i once asked on unity-discord-server if anyone would recommend linked list for a faster computation and everyone aggreed, that linkedlist are basically useless in unity. ive learned alot from the channel. if you wanna gain performance: use async tasks, mulithreading and entities... but this doesnt go for the build pipeline of course.
So if you want to add or remove data frequently use linked lists and if not use arrays? Are arrays easier to sort?
I would like to add that linked lists are like a way to start to learn more complex data structures, e.g. binary trees and graphs.
Definitely, along with the concept of a pointer, they're a great intro in general.
An amazing series, Simon, big thanks!
The visualizations you make while explaining things helps a lot.
P.S, I think, the patreon link is missing from the description.
Oops, fixed!
I feel like its only a matter of time before your channel blows up! Great information and the way you present it is very engaging
Your voice makes this video much more interesting !!
Thx yt for recommending me this! I’ll watch more of your videos. You definitely deserve more subs
Array:
access at index - O(1)
Insert/delete at start - O(n)
Insert/delete at end - O(1)
Insert/delete from middle- O(n)
Linked List:
access at index - O(n)
Insert/delete at start - O(1)
Insert/delete at end - O(n)
Insert/delete from middle - O(n)
Kinda, although a small hack for arrays gets faster deletes. Array delete at any index is O(1) if you don't care about preserving order, which in many gamedev situations is true.
And O(n) for an array of contiguous memory vs O(n) for a standard linked list have very different performance characteristics on modern hardware.
Another excellent video! I’ve recently been trying to make a hash-indexed linked list. Works, but I’m having trouble resizing the table though.