5 ms·

Thanks for the article, there should be a huge list of those type of classic C++ misconceptions/FAQ style. One of my favorite is "you don't need a linked list"

• quietbritishjim 6y ago
  I used one the other day because it had the interface I needed and the number of items was so small and so infrequently iterated over that performance didn't matter. (I guess that's not really what you meant though: you were probably interested in a use where it really was needed for performance reasons - splicing things around or the like.) Specifically I needed the guarantee that iterators weren't invalidated by other parts of the list changing. I could've used a vector and worked around it but it would've taken more effort and more code, and like I said the performance difference wouldn't have made an overall difference to the program.
• beaconstudios 6y ago
  Naively, I would assume that LLs are best used for long lists which are typically traversed incrementally, like a FILO-only job queue. That wouldn't perform better than a static array of statically-sized objects, but it could be better for eg. a list of structs with flexible array members (ie, variable-sized structs). They might be good for traversed lists with the possibility of partway insertion too, or performing insertion sort. Hell they might even be good for traversed lists in the general case, but I'm not a low level dev so I don't know without testing it. Fun exercise though! I'm guessing they're taught because they're taught, in that special inertial way that education propagates. Originally, I bet they were introduced when implementing your own data structures rather than pulling a library was normal industry practice. Of course there is tons of value in knowing about data structures and their characteristics, but probably not in knowing how to implement LLs.
  • gmueckl 6y ago
    Even if linked lists and double linked lists aren't all that universally useful by themselves, they teach all the basics about taversing data structures by references / pointers that more complex trees and graphs require. A linked list is just a degenerate tree with at most one child for each parent. So I think teaching that isn't a bad decision.
    • dmurray 6y ago
      I couldn't have said it better :)
    • beaconstudios 6y ago
      good point, they may still be useful as a pedagogical tool to introduce pointer-based structures.
  • dmurray 6y ago
    Everyone would probably agree it's good to teach trees in a CS data structures class. Linked lists make a nice introduction to this: what is a linked list except a tree with max branching factor 1? So you teach LLs on day one, and introduce in the simplest useful way the idea of a recursive data structure.
  • ywei3410 6y ago
    They're also an example of a data-structure which works pretty in a concurrent setting - you can get away with a single atomic reference for an unbounded FILO queue implemented with a linked list. Adding and removing items to it is then dirt-cheap - provided you don't go through the queue quickly and job running time > iteration time. But with all things in computer science, it really depends on your use-case.
• w0utert 6y ago
  >> Although I'm still genuinely interested when a linked list is best suited. I'm also curious why they were invented and why they're taught, maybe just for teaching purposes... It's not hard to come up with plenty of valid use cases for linked lists. Any time you need some algorithm that does a lot of non-predictable insertions/deletions, on a collection that is not regularly iterated in full or used to find elements (so pointer-chasing/cache effects are irrelevant). And/or when the elements are prohibitively expensive reorder/move on insertions/deletions, or some other piece of code is known to keep direct references to the elements that should not be invalidated when some unrelated element is inserted/removed and. Maintaining validity of iterators while an algorithm is operating on the list is another important benefit. Some people will come up with all kinds of clever workarounds or more complicated datastructures/bookkeeping so you can achieve the same thing without a linked list, but in most cases I don't see the point of it. Especially not in cases that are not performance-sensitive at all. In such cases you're just increasing code complexity and obfuscating intent because of some ideological objection to using linked lists.
  • MauranKilom 6y ago
    > Any time you need some algorithm that does a lot of non-predictable insertions/deletions, on a collection that is not regularly iterated in full or used to find elements (so pointer-chasing/cache effects are irrelevant). You still should at least consider a vector here. If lookups are infrequent, you can just sort it and binary search it on demand (and just add new items at the end). There are cases when this is not good enough, but they really are surprisingly rare. > And/or when the elements are prohibitively expensive reorder/move on insertions/deletions, or some other piece of code is known to keep direct references to the elements that should not be invalidated In that case, why not store the elements in a unique_ptr (and then everything in a vector)? > Especially not in cases that are not performance-sensitive at all. In such cases you're just increasing code complexity and obfuscating intent because of some ideological objection to using linked lists. Fully agreed - if you are sure that it cannot possibly become performance relevant and a list has the right interface, use it. For example, when the number of items is fundamentally tiny (e.g. one item per dimension of your 3D data) and the thing you'll do with the list item will be complex (or infrequent) anyway so that a few pointer indirections are negligible.
• 4fips 6y ago
  Linked lists become really powerful and performant when implemented as intrusive containers, such containers do not need to live on heap and can be embedded directly into another data structures, so an element can be linked into multiple containers at the same time, this gives great flexibility and compactness (especially when indices are used to form the links instead of pointers).
  • eru 6y ago
    Similarly, some data structure and algorithmic choices that don't make much sense when operating in RAM, can suddenly become appropriate in different environments. Eg when working on hard disks (eg think a file system or database with raw storage access). Or if you are working in a medium were you can only write once, and can't change what's already written, etc.
• lorenzhs 6y ago
  Several few decades ago, pointer chasing was much cheaper because the difference between an arithmetic operation and a memory access was far lower. CPUs in those times didn't even have caches (because they weren't needed). That made linked lists a reasonable choice. But CPU and memory speeds have been diverging -- both are growing at an exponential pace, but with different exponents, so the gap is also growing exponentially! So now we have a huge memory hierarchy and random accesses into memory are really slow and linked lists rarely make sense.
  • masklinn 6y ago
    > Several few decades ago, pointer chasing was much cheaper because the difference between an arithmetic operation and a memory access was far lower. Also allocation was just bumping the brk.
• creata 6y ago
  Linked lists are pretty nice. * Lazy linked lists are the same thing as iterators, a fact which is used pervasively in Haskell. * Intrusive or otherwise inline linked lists like are used everywhere, e.g. the DOM has a doubly linked list of children for each node, simple memory pools are often implemented as free lists, and tons of resources inside kernels are members of many linked lists. * Linked lists are guaranteed O(1) append, but dynamic arrays are only amortized O(1) append. Intrusive linked lists also never need to allocate. That makes them useful inside resource-constrained places.
  • jpcooper 6y ago
    Agreed on linked lists in Haskell if you’re doing forward iteration. You can have lazy byte strings under the bonnet while providing a ‘pure’ linked list interface. No worries about explicit iteration.
• lelanthran 6y ago
  > Although I'm still genuinely interested when a linked list is best suited. I can think of a few use-cases where I've opted for linked-lists over resizable arrays: 1. When you have enough memory for the set of all elements you want to store but not enough contiguous memory for the set of all elements you want to store (i.e. You have the available memory, but it's all fragmented). 2. When you have multiple threads adding to/removing from the container, a linked list lets each thread (in theory) insert/remove nodes at the same time. For example, one thread can be adding to the head of a queue while another thread is removing from the tail of the same queue; they don't need to both wait for the same lock to resize the container. 3. When you have large insertions/removals. For example, concatenating two lists into one is just reassigning two/four pointers in linked lists. With arrays or similar you have to have enough free memory to make of a copy of the smaller list, at least). Another example is "zipping" two lists together - you simply go through the lists and reassign pointers. With arrays you have to allocate enough memory for the final list before copying elements over. Same goes for splitting lists into two: for example, applying a predicate function to remove and return all elements that satisfies the predicate takes no extra memory using lists, but with arrays will need the destination to be allocated first). 4. Finally, you may want to store cycles in your container (perhaps the traversal maintains state so you can use the cycle to make traversal of some nodes repeat, or maybe you're simply insane and like to confuse readers of your code :-). Okay, fair enough, that last one is me stretching things a bit :-)
  • MauranKilom 6y ago
    Re 1. (memory fragmentation): I'm sort of on board with this (although you probably make it worse for the next person if you use linked lists). But it'll be a very special case where the performance hit from working with a huge list will be acceptable. Re 2. (threading): What happens when the list becomes empty? How do you keep track of the size to determine whether the list is empty? How do you know the size is still up-to-date when you go on to make a modification? I don't think this is as easy (even "in theory") as you make it sound. Re 3. (merging overhead): You say "takes no extra memory", but you use significant extra memory already: You incur an additional two pointers of (and possibly per-allocation) overhead. For the entire lifetime of the list, not just when you do some operations. If your elements are small, then your list might have double memory consumption the entire time instead of only when merging. And if they are large, you could store unique_ptrs to those elements in a vector. In which case the total memory overhead of merging two vectors (2 x total number of elements x pointer size) is exactly the same as a linked list has the entire time. And all the operations then turn into shuffling around pointers too, but probably fewer: You just have to move the unique_ptrs around, which is one pointer each instead of constantly unlinking and relinking lists. Sure, sometimes iterator invalidation is a thing, and maybe keeping pointers to (separately allocated) elements doesn't cut it. But even then you wouldn't want to use a list if performance is even remotely a concern.
• jpcooper 6y ago
  I remember the linked list being useful to solve Leetcode-style questions involving LRU (least recently used) caches.
• quotemstr 6y ago
  > Although I'm still genuinely interested when a linked list is best suited Maintaining an intrusive list of objects that you have around anyway is sometimes the simplest option, especially because objects can easily remove themselves from the list upon destruction.
• grogers 6y ago
  Use a linked list when you need to store iterators into a container while mutating it. E.g. if you are making a super naive LRU cache, you could use a map<K, list<pair<K,V>>::iterator> and a list<pair<K,V>>. This is something you can't do with vectors unless you can guarantee the capacity will never increase. This is the most useful case of removing from the middle of a container, which linked lists are good at. Intrusive lists are common for this type of thing, instead of actually storing a list iterator.
• eru 6y ago
  Linked lists are great when you want a fully persistent data structure version of a stack. (https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure) If you don't need persistence, you can often use a dynamic array to do basically everything a linked list can do for you, but most of it faster. Also, if you have a relocating garbage collector, or otherwise a smart enough compiler (or interpreter), linked lists can become sufficiently efficient.
• bzbarsky 6y ago
  One place where a (doubly, perhaps) linked list might be suitable is when you have a list that wants to provide the following features: 1. Multiple independent (not necessarily concurrent, but not coordinated) mutators. 2. Insertion and removal happen commonly and should be cheap. 3. Operations on the whole list typically happen in list order or close to it. Bonus points if the size of the relevant data structures is often such that you blow out caches anyway (e.g each thing in your list is larger than a cache line) and hence there are no strong locality benefits from an array. Thought prefetching _can_ sometimes help with arrays there. The above features _can_ be implemented on top of an array, but feature 1 means you can't use indices as long-lived handles to items, so you need either handles that get updated on mutations or some concept of identity and "find the current index of this thing" calls. For context here, Gecko used to store the children of a DOM node as an array of pointers and switched to a doubly-linked list because the DOM does have the above properties and it was faster and mostly simpler to have a linked list in practice. There is a bit of complexity to make node.childNodes iteration (as opposed to .nextSibling/.previousSibling iteration) not be O(N^2), but overall the switch was a win.