Search code examples
linked-listcircular-buffer

When would a linked list be preferred over a circular buffer?


In terms of big-O runtime, it seems that both data structures have in the "average" case:

  • O(1) insertion/removal into the start and end
  • O(n) insertion/removal into some arbitrary index
  • O(1) lookup of the start and end

Advantages of circular buffer:

  • O(1) lookup instead of O(n) of some arbitrary index
  • Doesn't need to create nodes, thus doesn't need a dynamic allocation on each insertion
  • Faster traversal due to better cache prediction
  • Faster removal due to vectorization (e.g. using memmove) to fill the gap
  • Typically needs less space (because in a linked list, for each node, you have to sort pointers to the next and/or previous node)

Advantages of linked list:

  • Easier to get O(1) insertion/removal to some specific place (e.g., could get it for midway through the linked list). Circular buffers can do it, but it's more complicated
  • O(1) insertion in the worst case, unlike circular buffers that are O(n) (when it needs to grow the buffer)

Based on this list, it seems to me that circular buffers are a far better choice in almost every case. Am I missing something?


Solution

  • The MCS lock is one of the most scalable lock designs there is. A thread uses an atomic compare and exchange to attempt to seize the lock. If it works it is done. If it doesn't work, the thread uses an atomic exchange to enqueue itself at the tail of the list of waiters.

    There is not way to do a similar thing with circular buffers without locks or more complicated use of atomic instructions.