我多次读到，链表充其量只是一种小众数据结构，由于其缓存局部性较差，不适合一般用途。然而，我所见过的几乎所有无锁数据结构示例都使用链表。 C++ 并发实践 和 The 例如，多处理器编程艺术在其无锁堆栈和队列的实现中使用链表。
在设计堆栈和队列等无锁容器时，是否有更好的链表替代方案？
最佳答案
Are there better alternatives to linked lists when designing lock-free containers
是的，可能出于某些目的。链表只是最简单的东西，可以很好地推广到许多应用程序。
如果你使用单向链表(在最简单的情况下)，你可以填充一个节点而完全没有同步问题(=多个线程可以同时填充节点)，并且唯一同步的操作是头指针交换。
因此，虽然链表没有针对性能提出其他建议，但您可以看到这可以推广到任意大和复杂的节点，以及任意数量的生产者和消费者。
比较循环缓冲区:如果你有多个生产者，你需要一些方法来标记缓冲区的一部分在可供读取之前保留(防止其他写入)。这是因为所有生产者都共享同一个缓冲区，而不是在他们自己的节点上工作。它是可行的，但本质上是非原子的，只是因为您无法像准备一个单独的节点那样准备共享缓冲区的一部分以避开其他线程的窥探。
如果您有一个生产者，这很容易，而且它确实比链表具有更好的局部性，但显然不太通用。
关于c++ - 无链表的无锁编程，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41044417/