5 ms·

When are linked lists actually good? Everything I read about them suggests they have rotten performance, yet I see them employed in various places all the time

• superdimwit 4y ago
  One nice property is their stable addressing. A linked list element won't move once allocated.
  • chii 4y ago
    > A linked list element won't move once allocated. only pertains to languages like C. In a virtual machine language like java, this isn't a property that can exist (there's no such thing as an address - at least as far as the language is concerned).
    • ziml77 4y ago
      A reference in Java can essentially be thought of as a pointer into a virtual address space. The JVM can move around the location of an object in the system's actual memory, but as far as anything holding reference is concerned nothing has changed.
      • recursive 4y ago
        And a reference to an object that's in an array won't be invalidated if that object is moving around the array or even removed entirely. It's still a C concern.
• di4na 4y ago
  Anytime you do something that is immutable with probable change somewhere inside that is not easy to handle with far mor complex datastructure. In particular linked list are great for heterogeneous cells type. Vectors and arrays have the problem of needing contiguous memory. If an inner cell can have different size, or worse change it mid work, things get ugly really fast.
  • MontyCarloHall 4y ago
    Why not just implement this as an array of constant width pointers to the heterogeneous data types?
    • LorenPechtel 4y ago
      Which is what happens in most modern languages. The items in your list are objects--which internally are just pointers to the data. There's no performance penalty for having variable-sized objects in the list.
    • di4na 4y ago
      you just defined how memory work, you are welcome :)
• deleted 4y ago
  [deleted]
• Ono-Sendai 4y ago
  Linked lists are great for free lists in memory allocators.
• SAI_Peregrinus 4y ago
  Writing a system allocator (malloc). They're also more useful on microcontrollers where there's no cache, no prefetcher, etc. Less code needed for the data structure means more free space for business logic, and there's no performance penalty for bad cache locality on a system without any cache. Also a hash table has to hash each input, which is a significant amount of work for many microcontrollers.
• marginalia_nu 4y ago
  I think the problem is that we're thinking about linked lists like they are taught in intro to algorithms. Like ListNode* a = new ListNode('A'); ListNode* b = new ListNode('B'); ListNode* c = new ListNode('C'); a.next = b; b.next = c; That's a dumb way of implementing a linked list with no redeeming features outside of explaining the concept. This is a linked list with the same shape as the list above, but with completely different performance characteristics: int* data = new int[3]; data[0] = 'A'; data[1] = 'B'; data[2] = 'C'; int* links = new int[3]; links[0] = 1; links[1] = 2; links[2] = -1; With some elaboration (say exchange the arrays for a mmap-call, turn it into a tree instead of a list) and you're basically looking at the guts of a DMBS or a file system.
  • ziml77 4y ago
    Is there a reason the keep the data and the indices in different arrays? Unless you're navigating to an item by its position in the linked list, you're going to be checking the data at each node and then reading the next index to traverse forward. Since you're reading both, wouldn't it be better to make the index of the next node intrusive?
    • marginalia_nu 4y ago
      The design is mostly to provide a clear enough example, you can of course interlace them. It depends on the use case. If you're doing a lot of navigating over links before you reach the destination, maybe you want them separate. Could also be the data is large, even maybe stored on disk while the links are in memory, or whatever. There's a thousand different scenarios with different optimal arrangements.
    • magicalhippo 4y ago
      It allows you to reorder the data, say sorting it, without moving the actual data. If the element type is say a struct, this can be a huge performance win. It also allows you to keep multiple different lists to the same data, say sorted by different fields in the struct.
  • MontyCarloHall 4y ago
• dudul 4y ago
  I believe they can also be useful to share data between instances in the case of immutable structure. Prepending to an immutable linked list is quasi-free in terms of memory usage.
• MontyCarloHall 4y ago
  >One case that seems to make sense is any time you want to do constant-time pops/appends… maybe? Yes, and constant time insertions/deletions in the middle of the list, assuming you know the address ahead of time. This makes them great as backing queues in an LRU cache: given some key/value pairs, have a linked list whose nodes map to each key. Additions to the K/V store gets appended to the LL. This lets you easily remove the oldest n elements in the K/V store, by traversing from the head of the LL. It also lets you efficiently remove arbitrary elements from the K/V store, if you store the addresses of each LL node as values in the K/V, since deletions in the middle of the LL are constant time. >yet I see them employed in various places all the time I agree, however, that most LL applications (like the one I just mentioned) are fairly niche. LLs are overused because they’re dead simple to implement and commonly taught in intro CS classes.
• leeter 4y ago
  Operating systems where you need to be able to atomically insert or remove from a list. Because the links are just pointers and the memory can be managed after the swap you can use atomics to compare and swap pointers. This allows for the RCW mechanisms the linux and NT kernels depend on to work. This also technically applies to lockless data structures for some high performance code too. But those tend to be much much more tightly tuned for performance and the specific CPU they are intended to run on.
• deleted 4y ago
  [deleted]
• alex_smart 4y ago
  I have seen highly successful proprietary trading firms implement their order books using linked lists (more like a linked list for each level of the order book, with the levels themselves arranged in a linked list). Obviously they use a custom allocator or an object pool to make sure that the cache performance isn't completely atrocious.
• shultays 4y ago
  They are sometimes used as intrusive lists but a generic one rarely used. Inserting an element in middle is probably only legit use but it is kinda rare to have large enough data that you frequently insert in mid
• deathanatos 4y ago
  > 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)
• jerf 4y ago
  "When are linked lists actually good?" Your question is more accurate than you realize! Because the answer is... the past. Up until about the 486/50MHz era, CPUs and memory were attached to each other; one CPU cycle was approximately equal to one memory access. I don't mean that you could reach out to RAM in exactly one cycle and get a value, there were still some CPU caches and other considerations, but it was much closer to that ideal than on modern systems. And if you go back in time even farther, that actually was the case (Commodore 64, for instance). (I don't know if there was ever a "true" 486/66 system, but I remember that as the CPU/clock speed where the CPU finally and definitively detached from RAM speed because that was generally a double-clocked 486/33 from the RAM's perspective. I can't quite remember the marketing term that was used. It's a dead term now because everything works that way.) In those circumstances, traversing a linked list was not necessarily that much more expensive than a vector, and you could win on the other things a linked list can do faster than a vector, like insert in the middle, especially an insert in the middle when you were traversing the list anyhow. You could also win on a linked list containing a relatively large value organized just by pointers; a sort on the linked list manipulating just the pointers could win versus a sort that was trying to move around larger values constantly during the sort. And so on. When memory accesses aren't hundreds and hundreds of CPU cycles, when your hardware doesn't have prefecting implemented, when your pointers aren't 64bits wide, when you aren't on modern systems essentially designed to make vector-based access go zoom, linked lists make a lot more sense. This is how they got embedded in curricula so hard that they are taught to this day. They used to be a very important data structure. Now they're an antipattern. It happened gradually, though, and it doesn't help that linked lists are just about the easiest non-trivial data structure to teach and I'm not sure they could get removed from the standard curriculum for that reason alone. "One case that seems to make sense is any time you want to do constant-time pops/appends… maybe?" Another problem linked lists have is that if you know that's what you're going to do, you can build vector-based solutions to that problem that work just fine. Vector-based stacks, for instance, are trivial, and O(1)-amortized for push and pop, which is good enough in practice. (A bit more care is needed than an only-growing vector but IIRC it can be done.) You need not just something linked lists are better at, but some bizarre cocktail of all the things they're just barely better at, and you still need to construct a win out of the combo. It's nearly impossible. Not quite impossible. I assume without looking that the Linux kernel still has some linked lists for good reason, as I'm sure if they could win on performance by removing them they would. But very hard.