If you enjoyed this, help support me: www.patreon.com/simondevyt

@bukayo797

3 жыл бұрын

Want to see more videos like this. ❤️

@climatechangedoesntbargain9140

Жыл бұрын

Why did you thumbnail "Always use THIS"?

@simondev758

Жыл бұрын

@@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.

@budgetarms

3 ай бұрын

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

@simondev758

Жыл бұрын

100%

@minneelyyyy8923

Жыл бұрын

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.

@simondev758

Жыл бұрын

@@minneelyyyy8923 Possibly, but that'd only be true if you allocated the nodes up front.

@atiedebee1020

Жыл бұрын

@@minneelyyyy8923 having to store a pointer as well makes them less cache friendly even if the nodes were to be stored sequentially

@semurgx

Жыл бұрын

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.

@KevinJDildonik

Жыл бұрын

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.

@coolestboy6262

Жыл бұрын

​@@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.

@gregorymorse8423

Жыл бұрын

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.

@gregorymorse8423

Жыл бұрын

@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...

@stapler942

Жыл бұрын

@@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.

@simondev758

Жыл бұрын

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.

@slayemin

Жыл бұрын

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.

@angeldude101

Жыл бұрын

@@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.

@DominicVictoria

4 ай бұрын

This comment was so confusing at first, until you understand the context and the implied knowledge you need to have to understand this.

@angeldude101

4 ай бұрын

@@Antagon666 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

@simondev758

Жыл бұрын

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.

@BitwiseMobile

Жыл бұрын

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.

@ledi51

Жыл бұрын

In c++ you can still use vectors for non-copyable types, by making them “moveable”

@smorrow

11 ай бұрын

> 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

@BosonCollider

4 ай бұрын

@@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 restaurant tables analogy has got to be the best analogy for arrays in memory I've ever heard.

@wonkothesane13

Жыл бұрын

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

@rl6382

Жыл бұрын

​@wonkothesane13 what trashy places are you eating at? Jk lol, but seriously, that's kinda stretching it. I think the point was very clear.

@wonkothesane13

Жыл бұрын

@@rl6382 *working at, and nowhere fancy that's for sure

@rl6382

Жыл бұрын

@wonkothesane13 awww 😅😔 It's okay you are a good person so I hope you are atleast treated well. Customer service is TERRIBLE.

@NYKevin100

4 ай бұрын

@@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.

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.

@simondev758

Жыл бұрын

I have a video on hash tables if you're interested

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 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.

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.

@simondev758

3 жыл бұрын

I'll do a video on that, it's on my TODO list. Summary is: Graphics/optimization in gamedev, small indie company owner, Google

@devsauce

3 жыл бұрын

@@simondev758 Thanks for taking your time to reply. Looking forward to hear it !

@ExCyberino

3 жыл бұрын

@@simondev758 Thats a lot, more or less the career path I have in mind, maybe not in that order =P

@rukasuigh5683

Жыл бұрын

I'm not so sure about it. 5:02 the guy just lost half of his linked list....

@puppergump4117

Жыл бұрын

@@rukasuigh5683 It's not like he's not saving the next address.

So glad I came across this channel. Such a good pool of knowledge and experience!! 👍👍👍

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 feel like its only a matter of time before your channel blows up! Great information and the way you present it is very engaging

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.

@simondev758

3 жыл бұрын

Oops, fixed!

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.

@simondev758

3 жыл бұрын

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.

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

@simondev758

3 жыл бұрын

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"

Perfect timing! I have exam on this in 3 days. Good repetition.

@simondev758

3 жыл бұрын

Good luck!

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.

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!

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

@simondev758

3 жыл бұрын

Sweet, let me know if you have suggestions too!

You absolutely should make a video with that interview question you can't ask anymore!

@simondev758

3 жыл бұрын

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.

@Metruzanca

3 жыл бұрын

@@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.

@Speykious

3 жыл бұрын

@@simondev758 I think it can still be interesting to hear your point of view.

@cartersherman925

3 жыл бұрын

@@simondev758 it’s DEF an LRU cache

@BringMe_Back

3 жыл бұрын

@@simondev758 you must ,guide me as well , I am 2nd year college student , Learning from here n there

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

Жыл бұрын

They can still trip up the prefetcher for subsequent requests if you're iterating the array

@ttamttam1522

Жыл бұрын

@@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.

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)

@BosonCollider

4 ай бұрын

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.

Really cool video. All info is well explained and animations is very helpful. Thanks!

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.

@simondev758

3 жыл бұрын

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.

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.

@simondev758

Жыл бұрын

Absolutely

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.

This video is excellent. Thanks for the quality content!

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! :)

Always love hearing other people's thoughts on data structures and algorithms. This was really cool and well explained. Thanks Simon, you're the best

@simondev758

3 жыл бұрын

Glad it was helpful!

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.

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.

@simondev758

2 жыл бұрын

Let me know if there are other subjects you want me to cover!

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.

please make more. This content is really good

Great teaching style...would love to see a video on faang interviews and how to solve and prepare for the questions.

Thx yt for recommending me this! I’ll watch more of your videos. You definitely deserve more subs

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.

@rinzler9775

Жыл бұрын

I wrote a similar game once, and used actual class objects, with a "bag" of pointers to those objects.

I know all this allready but I still watch because your voice and explaination is so good

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.

@simondev758

3 жыл бұрын

I'll probably take a run at algorithmic analysis next before moving too far into more data structures.

@puppergump4117

Жыл бұрын

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

@rodbot

Жыл бұрын

This is something I learned in my first CS class in college...

@illford6921

Жыл бұрын

IDK what they're doing where your at but i learnt this at 16 in the UK

@ymndoseijin

Жыл бұрын

I quite literally knew this since I was 12

A tree of linked lists of arrays ! The best data structure ever, or as they call it, the dictionary, or bucket-list.

Love the content and I am currently binge watching your previous videos so forgive me if you have already covered it, but I would love to see a video on making a 'mini map' showing a bird's eye view of the current game area. I 'kinda' understand how this is done using a camera but would love to get your take on making one along with any gotcha's (e.g. CyberPunk mini map not zooming out when driving so becomes un-usable etc.) Thanks again for the awesome video's and I can't wait until you have enough code snippets to make your final game.

I am an aspiring game developer from Nigeria and I really learn alot from this channel...

Great explanation! I love how you compared it to tables at a restaurant.

You are the first person I've seen recommending someone to learn about modern processor cache shenanigans before learning about linked lists lol

Great author.. with real knowledge! Not a copycat as most of YT's are..

@GioRob

3 жыл бұрын

underrated comment

@bjarnieinarsson3472

3 жыл бұрын

@@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)

@GioRob

3 жыл бұрын

@@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

3 жыл бұрын

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.

@GioRob

3 жыл бұрын

@@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!

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.

@BosonCollider

4 ай бұрын

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

@anon_y_mousse

4 ай бұрын

@@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.

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.

@simondev758

Жыл бұрын

Totally want to make a video on intrusive linked lists, kinda the except to my "just use an array" rule.

Youre literally a king amongst men keep up the awesome content

Wow, im new to programming and i realy hope you continue making videos like this. It realy helps a lot

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.

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

Жыл бұрын

Dynamic arrays probably cover most use cases. I've legit needed linked lists a few times, in 20 years.

@Boris99999

Жыл бұрын

@@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!^_^

Please keep sharing your knowledge Senpai, I like your videos! Also, hello Futurama names :)

More of this. Awesome and super educational

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.

@simondev758

3 жыл бұрын

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.

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).

@simondev758

Жыл бұрын

Very good points, I feel like I need a follow-up on this video one day with more nuanced use of each like this.

@xarcaz

Жыл бұрын

@@simondev758 Looking forward to it. Keep up the excellent content!

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.

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.

@simondev758

Жыл бұрын

Agreed, the concept of a "node" is fundamental for understanding so many data strutures.

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.

Like ur videos and like how u present the information. Thanks a lot👍

This series is seriously underrated!

Incredible useful video, thank you! 👏

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.

@simondev758

4 ай бұрын

True, although if multiple threads are accessing the list simultaneously, it's not going to be threadsafe either way.

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

I just vaguely remember linked lists and arrays from some books I read, and was interested in seeing when linked lists were actually good, since I mostly only see arrays. So, for me, this was just entertainment. Next I'm gonna check out your video on JavaScript vs. C++ speed, even though I only ever tinker with JavaScript to locally customize webpages.

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.

Your voice makes this video much more interesting !!

Great stuff, thanks for sharing!

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?

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 hope you will continue this series

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.

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

3 жыл бұрын

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.

@aylictal

3 жыл бұрын

@@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! :) kzread.info/dash/bejne/fZ5k28FpdsKworw.html

@DommageCollateral

Жыл бұрын

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.

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.

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.

amazing video, im glad i found this channel

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.

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

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.

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.

@simondev758

4 ай бұрын

Memory optimization is definitely an area that you target when doing real world stuff

Here I am looking at this video again after 1 year and still enjoying it

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.

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.

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.

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.

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.

@simondev758

Жыл бұрын

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.

@xlerb2286

Жыл бұрын

@@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...

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.

@simondev758

3 жыл бұрын

Hopefully this answered it :)

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 :)

@thezipcreator

Жыл бұрын

so basically java's ArrayList?

keep up the good work love your vids

very nice overview

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.

@gavipk

4 ай бұрын

arrays are fixed length tho

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.

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.

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.

Great video!

Great video, thanks!

Great content!

Ya it explains a lot , ill keep coming back, coz i always forget the things , Hope in the interview ill do good 🙂

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..

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 :)

these videos are amazing!