Why Linked Lists vs Arrays isn’t a real choice
Вставка
- Опубліковано 23 бер 2021
- 🛒 Recommended books (on Amazon): www.amazon.com/hz/wishlist/ls...
❤️ Support me on Patreon: / simondevyt
🌍 My Gamedev Courses: simondev.teachable.com/
Disclaimer: Commission is earned from qualifying purchases on Amazon links.
Follow me on:
Twitter: / iced_coffee_dev
Instagram: / beer_and_code
Github: github.com/simondevyoutube/
In this video we talk a bit more about data structures and optimizations, specifically we'll get into linked lists vs arrays, how to do common operations on them, and what happens to the underlying memory. These all have impacts on how they perform, it's not solely about big-O, cache locality effects come into play and we can understand in what situations an array or a linked list is expected to perform better. We'll work through some real world examples to bring the point home and get a solid understanding of these data structures.
What's covered:
* What are linked lists
* The importance of contiguous memory, and CPU caches
* Linked list vs arrays, what each operation does and roughly which one is faster
* Memory implications vs arrays
* Closing thoughts, and when I've personally found linked lists useful in my career
If you enjoyed this, help support me:
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
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.
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.
The restaurant tables analogy has got to be the best analogy for arrays in memory I've ever heard.
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
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.
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.
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.
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.
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
You absolutely should make a video with that interview question you can't ask anymore!
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.
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!
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.
7:06
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.
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.
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 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.