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 endO(n)
insertion/removal into some arbitrary indexO(1)
lookup of the start and endAdvantages of circular buffer:
O(1)
lookup instead of O(n)
of some arbitrary indexmemmove
) to fill the gapAdvantages of linked list:
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 complicatedO(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?
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.