A circular buffer is a type of data structure which represents a fixed-size queue using contiguous memory. In this article, we'll introduce the data structure, its core concepts, time complexity, and show an implementation in multiple programming languages. Note: this structure is related to the queue data structure. If you are not familiar with queues or would like a refresher, please visit our introduction to queues.
A circular buffer, also known as a ring buffer or circular queue, is a data structure which uses a fixed-size buffer, or continuous region of memory, to efficiently store a queue of
0 <= n items. This is similar to a queue structure, but has the additional requirement that the number of elements has an upper bound. If the upper bound needs to be exceeded, the object will need to be converted to a queue or circular buffer of a larger size.
As items are removed, the start index will rotate through the array. This is what enables us to perform dequeue operations in O(1) time. The enqueue operation is also O(1) time, similar to normal queues and array operations. The use of an array also provides the ability to efficiently access any given index within the structure.
Note that the getNthElement is not strictly required for a circular buffer implementation, but it does provide an efficient lookup time, so it can be considered one of the advantages this data structure provides.
The table below outlines the time complexity for various operations using arrays, queues, and circular buffers:
|Add Item to End||O(1)||O(1)||O(1)|
|Remove Item from Beginning||O(1)||O(1)||O(n)|
|Arbitrarily Increase Number of Items||O(n)||O(1)||O(n)|
|Access Nth Item||O(1)||O(n)||O(1)|
Circular Buffer Implementation
In the implementation below, we provide functionality for adding, or enqueuing, removing, or dequeuing, accessing the nth element, and converting the entire structure to an array. Note that for the getNthElement and toArray methods, we will be converting input indices to their positions relative to the start index. Thus, even though the structure internally uses an array, the array returned in toArray will return an array with the elements in their proper order.