How to clear a circular array queue in constant time O(1)

Question

I'm trying to find a way to implement an efficient clear to clear a circular array queue in constant time.

I've tried Array.fill() and filled the array with null values but it still has to go through the array which means O(n).

Consider the fact that you don't really need to care what's in any given location in your queue if it's outside of the bounds of your `head` and `tail` pointers. So if you just move both pointers back to the first element of the array and null out that element, that's indistinguishable from clearing out the values in the queue as far as actual functionality is concerned. — Jordan, Oct 28 '19 at 20:53
@Jordan I wouldn't say that. If you really want to clear your array so the (perhaps heavyweight) objects can be garbage collected, then the behavior you described is not what you want. — Alex R, Oct 28 '19 at 21:02
@Jordan In fact, if you don´t null out references in the array, this could be a memory leak. Imagine an object keeping references to large objects, it will remain in the array and prevent referenced objects from being collected by GC. — Glains, Oct 28 '19 at 21:06

Alex R · Answer 1 · 2019-10-29T08:09:13.087

I would say the answer to this question depends a bit on your requirements and what counts as a constant operation.

One way of doing it is to create a new array with a fixed size (which is O(1)) and discard the reference to the old one, resetting the pointers to their initial value afterwards. Using this approach subsequent insert operations would need to increase the size of the array.
Another way might be to initialize a new array with the same size as the one currently storing the elements and discard the reference to the old one. This might be a constant time operation.
The third approach would be the one suggested by user Jordan in the comment section of your question. Just move the head and tail pointers around. However, be aware that this doesn't clean out the references to the (perhaps heavyweight) objects in the array, which might result in a memory leak in your application, because the objects still stored in there can't be garbage collected.

Looking at the implementation of the clear operation of ArrayDeque (which basically is just a circular array queue), you can see that it uses an O(n) approach through the following two operations: (1) nulling the elements, (2) resetting the pointers.

/**
 * Removes all of the elements from this deque.
 * The deque will be empty after this call returns.
 */
public void clear() {
    circularClear(elements, head, tail);
    head = tail = 0;
}

/**
 * Nulls out slots starting at array index i, upto index end.
 * Condition i == end means "empty" - nothing to do.
 */
private static void circularClear(Object[] es, int i, int end) {
    // assert 0 <= i && i < es.length;
    // assert 0 <= end && end < es.length;
    for (int to = (i <= end) ? end : es.length;
         ; i = 0, to = end) {
        for (; i < to; i++) es[i] = null;
        if (to == end) break;
    }
}

How to clear a circular array queue in constant time O(1)

1 Answers1