4 ms·

> When are linked lists actually good? When the use case requires insertion/removal from the middle of the list. An LRU cache is about the most common use case

> When are linked lists actually good? When the use case requires insertion/removal from the middle of the list. An LRU cache is about the most common use case I've run across. (The "LRU" part requires it to often bump an item to the end of the list, so LL's excel here, as we can shift the element's position in the list in O(1) time. An LRU structure would normally pair the LL with a HashMap, which maps the cached item to its LL entry, so that we've also got a O(1) search into the LL, and don't hit the problem in the article.) > yet I see them employed in various places all the time, by competent engineers who are definitely aware of their limitations. I see them employed very, very rarely. Vectors¹ are by far more common in every codebase I've ever worked on. (And should be one's default, IMO, if all you need is a container of stuff that you're going to iterate over, which is the usual case, for the reasons in the article.) ¹ignoring cases where a hash(map|set) is required; then our codebase uses that, b/c that's what's needed.

verall 4y ago
This is exactly correct, since at least in C++, adding elements to any other data structure can invalidate the stored iterators/references in your hashmap. std::list will mean you pay a slight cost when adding new entries, which if your cache is working is hopefully not so often, or the malloc is already dominated by whatever is being cached.
- gpderetta 4y ago
  In c++, std::deque is better than std::list as an address preserving backing store as it requires less memory allocations, less space overhead and objects will be closer together.
  - deathanatos 4y ago
    > std::deque is better than std::list as an address preserving backing store std::deque will invalidate iterators in some cases. Since my example above was an LRU cache, the cache's removal of an item from the middle of the list (to shift it to the end) is one of those actions that would invalidate iterators in a std::deque. (Not to malign std::deque: it is a useful datastructure in its own right, and if you need queue-like semantics (e.g. cheap remove from front), it's a better choice than a LL, and both are better than vectors for that purpose. I find deque's internals to be a bit weird … my goto would normally be a ringbuffer, but the STL provides deque instead, so eh, it's good enough, if a bit odd IMO.) (Cf. https://en.cppreference.com/w/cpp/container/deque https://en.cppreference.com/w/cpp/container/deque)

verall 4y ago

This is exactly correct, since at least in C++, adding elements to any other data structure can invalidate the stored iterators/references in your hashmap. std::list will mean you pay a slight cost when adding new entries, which if your cache is working is hopefully not so often, or the malloc is already dominated by whatever is being cached.

gpderetta 4y ago
In c++, std::deque is better than std::list as an address preserving backing store as it requires less memory allocations, less space overhead and objects will be closer together.
- deathanatos 4y ago
  > std::deque is better than std::list as an address preserving backing store std::deque will invalidate iterators in some cases. Since my example above was an LRU cache, the cache's removal of an item from the middle of the list (to shift it to the end) is one of those actions that would invalidate iterators in a std::deque. (Not to malign std::deque: it is a useful datastructure in its own right, and if you need queue-like semantics (e.g. cheap remove from front), it's a better choice than a LL, and both are better than vectors for that purpose. I find deque's internals to be a bit weird … my goto would normally be a ringbuffer, but the STL provides deque instead, so eh, it's good enough, if a bit odd IMO.) (Cf. https://en.cppreference.com/w/cpp/container/deque https://en.cppreference.com/w/cpp/container/deque)