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.
Circular Buffer
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.
Since this data structure gives us a guarantee that we will have at most n elements, we can store the entire collection of elements in a fixed-size array. This will enable us to take advantage of fast indexing as compared to linked lists. In normal circumstances, removing an item from a queue, or dequeueing, would take O(n) time when working with an array, but we can reduce this to O(1) by keeping pointers to start and end indices:
- When the circular buffer is created, initialize start and end to 0.
- When an item is added, set ar[end] to that item, then increment end.
- When an item is removed, set ar[start] to null, increment start, and return the removed item.
- If start or end = bufferSize, set it to 0. This is where the circular aspect comes into play.
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.
Time Complexity
The table below outlines the time complexity for various operations using arrays, queues, and circular buffers:
Operation | Circular Buffer | Queue | Array |
---|---|---|---|
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.