[simonask]

Most programmers can implement a linked list.

Extremely few can use one safely.

They're an elegant weapon for a more civilized age - namely one without multithreading, aliasing-based optimization, and a host of other nice things.

[tauoverpi]

Multithreading is exactly where linked lists are useful as in the implementation of MPSC, MPMC, SPMC, and so on it allows one to safely construct objects out of vire of other threads then use a CAS to append the new item to the list making it visible for other threads to consume even without needing to allocate additional memory.

They're also pretty useful for free-list structures which overwrite entries to be removed (they're scheduled for deletion thus assumptiong here is that the object is now dead) with linked list nodes that would fit in that space thus never needing to allocate any additional as you can reuse existing space.

[simonask]

Yeah, wait-free data structures often contain linked lists. That doesn’t cancel out all of the other problems.

Anecdotally, I’ve seen wait-free structures used incorrectly many more times than I’ve seen them used correctly. Some people think they are magically faster because “acquiring a mutex lock is expensive”, but that’s far from always the case.

[mgaunard]

a CAS-loop, as suggested in the message you're replying to, is certainly not wait-free, only lock-free.

[simonask]

Thanks, my mistake. :-)

[codr7]

I don't see a problem with their safety, even in C.

More the opposite, their simplicity makes them safer to deal with than the alternatives. And sometimes their unique features (mostly the intrusive variant) are exactly what you need.

Multi-threaded accesses to a vector would be just as bad?