Circular Array Technique

labuladongOriginalAbout 3565 words

Prerequisite Knowledge

Before reading this article, you should first learn:

Basics of Arrays (Sequential Storage)

Summary in One Sentence

The circular array technique uses modulus (remainder) operations to transform a regular array into a logical circular array, allowing us to add or remove elements at the array's head in $O(1)$ time.

Principle of Circular Arrays

Can an array be circular? Not physically. An array is a block of linear, contiguous memory, so the concept of a circle does not apply.

However, we can "logically" transform an array into a circular one, as shown in the following code snippet:

java 🟢

// array of length 5
int[] arr = new int[]{1, 2, 3, 4, 5};
int i = 0;
// simulate a circular array, this loop will never end
while (i < arr.length) {
    System.out.println(arr[i]);
    i = (i + 1) % arr.length;
}

cpp 🤖

#include <iostream>
#include <vector>
using namespace std;

// array with length 5
vector<int> arr = {1, 2, 3, 4, 5};
int i = 0;
// simulate a circular array, this loop will never end
while (i < arr.size()) {
    cout << arr[i] << endl;
    i = (i + 1) % arr.size();
}

python 🤖

# array of length 5
arr = [1, 2, 3, 4, 5]
i = 0
# simulate a circular array, this loop will never end
while i < len(arr):
    print(arr[i])
    i = (i + 1) % len(arr)

go 🤖

import "fmt"

func main() {
    // array of length 5
    arr := []int{1, 2, 3, 4, 5}
    i := 0
    // simulate a circular array, this loop will never end
    for i < len(arr) {
        fmt.Println(arr[i])
        i = (i + 1) % len(arr)
    }
}

javascript 🤖

// an array of length 5
var arr = [1, 2, 3, 4, 5];
var i = 0;
// simulate a circular array, this loop will never end
while (i < arr.length) {
    console.log(arr[i]);
    i = (i + 1) % arr.length;
}

The key to this code is the modulus operation %, which calculates the remainder. When i reaches the last element of the array, taking the remainder of i + 1 and arr.length becomes 0, bringing it back to the start of the array. This logically creates a circular array, allowing endless traversal.

This is the circular array technique. How does this help us add or remove elements at the head of an array in $O(1)$ time?

Consider this: suppose we have an array of length 6, currently holding only 3 elements, as shown below (unused positions are marked with _):

[1, 2, 3, _, _, _]

Now we need to remove the element 1 from the head of the array. We can transform the array like this:

[_, 2, 3, _, _, _]

That is, we only mark the position of element 1 as empty without moving any data.

At this point, if we want to add elements 4 and 5 to the head of the array, we can transform the array like this:

[4, 2, 3, _, _, 5]

You can see that when there is no space at the head to add a new element, it circles around and adds the new element at the end.

Core Principle

The example above provides an intuitive understanding of circular arrays. The key to a circular array is that it maintains two pointers, start and end. The start pointer indicates the index of the first valid element, while the end pointer points to the index following the last valid element.

This means that when we add or remove elements at the head of the array, we simply move the start index, and when we do so at the tail, we move the end index.

When start or end moves beyond the array boundaries (< 0 or >= arr.length), we use modular arithmetic % to circle them back to the start or end of the array, achieving the effect of a circular array.

Hands-On Session

The knowledge we gain from books can be shallow; true understanding comes from practice.

I have implemented a simple circular array in the visualization panel. You can click arr.addLast or arr.addFirst in the code below and observe the changes in the start, end pointers, and elements within the arr array:

Code Implementation

Key Points: Note the Open and Closed Intervals

In my code, the interval for the circular array is defined as left-closed and right-open, i.e., the interval [start, end) includes the array elements. All other methods are implemented based on this left-closed, right-open interval.

Some readers might ask why not define both ends as open or closed?

In the Sliding Window Algorithm Core Framework, a similar question arises when defining the boundaries of a sliding window. Here's my explanation:

Theoretically, you can randomly design the open and closed nature of intervals, but typically, a left-closed, right-open interval is the most convenient to handle.

This is because when initializing with start = end = 0, the interval [0, 0) contains no elements, but moving end one step to the right (expanding) makes the interval [0, 1) include the element 0.

If you set both ends as open, moving end one step to the right results in an open interval (0, 1) that still contains no elements; if both ends are closed, the initial interval [0, 0] already contains an element. Both these cases add unnecessary complexity to boundary handling, and if you insist on using them, special handling in the code will be necessary.

Finally, I provide a generic Java implementation for your reference:

java 🟢

public class CycleArray<T> {
    private T[] arr;
    private int start;
    private int end;
    private int count;
    private int size;

    public CycleArray() {
        this(1);
    }

    @SuppressWarnings("unchecked")
    public CycleArray(int size) {
        this.size = size;
        // Since Java does not support direct
        // creation of generic arrays, type casting
        this.arr = (T[]) new Object[size];
        // start points to the index of the first valid element, closed interval
        this.start = 0;
        // remember that end is an open interval,
        // that is, end points to the next position index of the last valid element
        this.end = 0;
        this.count = 0;
    }

    // Helper function for automatic resizing
    @SuppressWarnings("unchecked")
    private void resize(int newSize) {
        // Create a new array
        T[] newArr = (T[]) new Object[newSize];
        // Copy elements from the old array to the new array
        for (int i = 0; i < count; i++) {
            newArr[i] = arr[(start + i) % size];
        }
        arr = newArr;
        // Reset start and end pointers
        start = 0;
        end = count;
        size = newSize;
    }

    // Add element to the start of the array, time complexity O(1)
    public void addFirst(T val) {
        // When the array is full, expand to twice its original size
        if (isFull()) {
            resize(size * 2);
        }
        // Since start is a closed interval, move left first, then assign value
        start = (start - 1 + size) % size;
        arr[start] = val;
        count++;
    }

    // Remove element from the start of the array, time complexity O(1)
    public void removeFirst() {
        if (isEmpty()) {
            throw new IllegalStateException("Array is empty");
        }
        // Since start is a closed interval, assign value first, then move right
        arr[start] = null;
        start = (start + 1) % size;
        count--;
        // If the number of elements in the array is reduced to
        // one-fourth of the original size, reduce the array size
        if (count > 0 && count == size / 4) {
            resize(size / 2);
        }
    }

    // Add element to the end of the array, time complexity O(1)
    public void addLast(T val) {
        if (isFull()) {
            resize(size * 2);
        }
        // Since end is an open interval, assign value first, then move right
        arr[end] = val;
        end = (end + 1) % size;
        count++;
    }

    // Remove element from the end of the array, time complexity O(1)
    public void removeLast() {
        if (isEmpty()) {
            throw new IllegalStateException("Array is empty");
        }
        // Since end is an open interval, move left first, then assign value
        end = (end - 1 + size) % size;
        arr[end] = null;
        count--;
        // Shrink
        if (count > 0 && count == size / 4) {
            resize(size / 2);
        }
    }

    // Get the first element of the array, time complexity O(1)
    public T getFirst() {
        if (isEmpty()) {
            throw new IllegalStateException("Array is empty");
        }
        return arr[start];
    }

    // Get the last element of the array, time complexity O(1)
    public T getLast() {
        if (isEmpty()) {
            throw new IllegalStateException("Array is empty");
        }
        // end is an open interval, pointing to the next element's position, so subtract 1
        return arr[(end - 1 + size) % size];
    }

    public boolean isFull() {
        return count == size;
    }
    
    public int size() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }
}

cpp 🤖

#include <iostream>
#include <stdexcept>
#include <ostream>

template<typename T>
class CycleArray {
    std::unique_ptr<T[]> arr;
    int start;
    int end;
    int count;
    int size;

    // helper function for automatic resizing
    void resize(int newSize) {
        // create a new array
        std::unique_ptr<T[]> newArr = std::make_unique<T[]>(newSize);
        // copy elements from the old array to the new array
        for (int i = 0; i < count; ++i) {
            newArr[i] = arr[(start + i) % size];
        }
        arr = std::move(newArr);
        // reset the start and end pointers
        start = 0;
        end = count;
        size = newSize;
    }

public:
    CycleArray() : CycleArray(1) {
    }

    explicit CycleArray(int size) : start(0), end(0), count(0), size(size) {
        arr = std::make_unique<T[]>(size);
    }

    // add an element to the front of the array, time complexity O(1)
    void addFirst(const T &val) {
        // if the array is full, double its size
        if (isFull()) {
            resize(size * 2);
        }
        // since start is a closed interval, move left first, then assign
        start = (start - 1 + size) % size;
        arr[start] = val;
        count++;
    }

    // remove an element from the front of the array, time complexity O(1)
    void removeFirst() {
        if (isEmpty()) {
            throw std::runtime_error("Array is empty");
        }
        // since start is a closed interval, assign first, then move right
        arr[start] = T();
        start = (start + 1) % size;
        count--;
        // if the number of elements in the array decreases to
        // a quarter of the original size, halve the size of the
        if (count > 0 && count == size / 4) {
            resize(size / 2);
        }
    }

    // add an element to the end of the array, time complexity O(1)
    void addLast(const T &val) {
        if (isFull()) {
            resize(size * 2);
        }
        // since end is an open interval, assign first, then move right
        arr[end] = val;
        end = (end + 1) % size;
        count++;
    }

    // remove an element from the end of the array, time complexity O(1)
    void removeLast() {
        if (isEmpty()) {
            throw std::runtime_error("Array is empty");
        }
        // since end is an open interval, move left first, then assign
        end = (end - 1 + size) % size;
        arr[end] = T();
        count--;
        // reduce the size
        if (count > 0 && count == size / 4) {
            resize(size / 2);
        }
    }

    // get the first element of the array, time complexity O(1)
    T getFirst() const {
        if (isEmpty()) {
            throw std::runtime_error("Array is empty");
        }
        return arr[start];
    }

    // get the last element of the array, time complexity O(1)
    T getLast() const {
        if (isEmpty()) {
            throw std::runtime_error("Array is empty");
        }
        // end is an open interval, pointing to the next element's position, so subtract 1
        return arr[(end - 1 + size) % size];
    }

    bool isFull() const {
        return count == size;
    }

    int getSize() const {
        return count;
    }

    bool isEmpty() const {
        return count == 0;
    }
};

python 🤖

class CycleArray:
    def __init__(self, size=1):
        self.size = size
        # Since Python supports directly creating generic arrays, no type conversion is needed
        self.arr = [None] * size
        # start points to the index of the first valid element, inclusive interval
        self.start = 0
        # remember that end is an open interval,
        # that is, end points to the index of the position after the last valid element
        self.end = 0
        self.count = 0

    # automatic resize helper function
    def resize(self, newSize):
        # create a new array
        new_arr = [None] * newSize
        # copy the elements of the old array to the new array
        for i in range(self.count):
            new_arr[i] = self.arr[(self.start + i) % self.size]
        self.arr = new_arr
        # reset start and end pointers
        self.start = 0
        self.end = self.count
        self.size = newSize

    # add an element to the head of the array, time complexity O(1)
    def add_first(self, val):
        # when the array is full, double the size
        if self.is_full():
            self.resize(self.size * 2)
        # since start is an inclusive interval, move left first, then assign value
        self.start = (self.start - 1 + self.size) % self.size
        self.arr[self.start] = val
        self.count += 1

    # remove an element from the head of the array, time complexity O(1)
    def remove_first(self):
        if self.is_empty():
            raise Exception("Array is empty")
        # since start is an inclusive interval, assign value first, then move right
        self.arr[self.start] = None
        self.start = (self.start + 1) % self.size
        self.count -= 1
        # if the number of elements decreases to
        # one-fourth of the original size, halve the
        if self.count > 0 and self.count == self.size // 4:
            self.resize(self.size // 2)

    # add an element to the tail of the array, time complexity O(1)
    def add_last(self, val):
        if self.is_full():
            self.resize(self.size * 2)
        # since end is an open interval, assign value first, then move right
        self.arr[self.end] = val
        self.end = (self.end + 1) % self.size
        self.count += 1

    # remove an element from the tail of the array, time complexity O(1)
    def remove_last(self):
        if self.is_empty():
            raise Exception("Array is empty")
        # since end is an open interval, move left first, then assign value
        self.end = (self.end - 1 + self.size) % self.size
        self.arr[self.end] = None
        self.count -= 1
        # shrink size
        if self.count > 0 and self.count == self.size // 4:
            self.resize(self.size // 2)

    # get the head element of the array, time complexity O(1)
    def get_first(self):
        if self.is_empty():
            raise Exception("Array is empty")
        return self.arr[self.start]

    # get the tail element of the array, time complexity O(1)
    def get_last(self):
        if self.is_empty():
            raise Exception("Array is empty")
        # end is an open interval, pointing to the next position, so subtract 1
        return self.arr[(self.end - 1 + self.size) % self.size]

    def is_full(self):
        return self.count == self.size

    def size(self):
        return self.count

    def is_empty(self):
        return self.count == 0

go 🤖

import "errors"

// CycleArray is a cyclic array data structure
type CycleArray[T any] struct {
    arr   []T
    start int
    end   int
    count int
    size  int
}

func NewCycleArray[T any]() *CycleArray[T] {
    return NewCycleArrayWithSize[T](1)
}

func NewCycleArrayWithSize[T any](size int) *CycleArray[T] {
    return &CycleArray[T]{
        arr:   make([]T, size),
        start: 0,
        end:   0,
        count: 0,
        size:  size,
    }
}

// automatic resize helper function
func (ca *CycleArray[T]) resize(newSize int) {
    // create a new array
    newArr := make([]T, newSize)
    // copy elements from the old array to the new array
    for i := 0; i < ca.count; i++ {
        newArr[i] = ca.arr[(ca.start+i)%ca.size]
    }
    ca.arr = newArr
    // reset start and end pointers
    ca.start = 0
    ca.end = ca.count
    ca.size = newSize
}

// add an element at the head of the array, time complexity O(1)
func (ca *CycleArray[T]) AddFirst(val T) {
    // when the array is full, double its size
    if ca.isFull() {
        ca.resize(ca.size * 2)
    }
    // since start is a closed interval, move left first, then assign
    ca.start = (ca.start - 1 + ca.size) % ca.size
    ca.arr[ca.start] = val
    ca.count++
}

// remove an element from the head of the array, time complexity O(1)
func (ca *CycleArray[T]) RemoveFirst() error {
    if ca.isEmpty() {
        return errors.New("array is empty")
    }
    // since start is a closed interval, assign first, then move right
    ca.arr[ca.start] = *new(T)
    ca.start = (ca.start + 1) % ca.size
    ca.count--
    // if the number of elements in the array is reduced to
    // one-fourth of the original size, halve the array size
    if ca.count > 0 && ca.count == ca.size/4 {
        ca.resize(ca.size / 2)
    }
    return nil
}

// add an element at the tail of the array, time complexity O(1)
func (ca *CycleArray[T]) AddLast(val T) {
    if ca.isFull() {
        ca.resize(ca.size * 2)
    }
    // since end is an open interval, assign first, then move right
    ca.arr[ca.end] = val
    ca.end = (ca.end + 1) % ca.size
    ca.count++
}

// remove an element from the tail of the array, time complexity O(1)
func (ca *CycleArray[T]) RemoveLast() error {
    if ca.isEmpty() {
        return errors.New("array is empty")
    }
    // since end is an open interval, move left first, then assign
    ca.end = (ca.end - 1 + ca.size) % ca.size
    ca.arr[ca.end] = *new(T)
    ca.count--
    // shrink size
    if ca.count > 0 && ca.count == ca.size/4 {
        ca.resize(ca.size / 2)
    }
    return nil
}

// get the element at the head of the array, time complexity O(1)
func (ca *CycleArray[T]) GetFirst() (T, error) {
    if ca.isEmpty() {
        return *new(T), errors.New("array is empty")
    }
    return ca.arr[ca.start], nil
}

// get the element at the tail of the array, time complexity O(1)
func (ca *CycleArray[T]) GetLast() (T, error) {
    if ca.isEmpty() {
        return *new(T), errors.New("array is empty")
    }
    // end is an open interval, pointing to the next element's position, so subtract 1
    return ca.arr[(ca.end-1+ca.size)%ca.size], nil
}

func (ca *CycleArray[T]) isFull() bool {
    return ca.count == ca.size
}

func (ca *CycleArray[T]) Size() int {
    return ca.count
}

func (ca *CycleArray[T]) isEmpty() bool {
    return ca.count == 0
}

javascript 🤖

class CycleArray {
    constructor(size = 1) {
        this.size = size;
        this.arr = new Array(size);
        // start points to the index of the first valid element, closed interval
        this.start = 0;
        // Note that end is an open interval,
        // which means end points to the next position index after the last valid element
        this.end = 0;
        this.count = 0;
    }

    resize(newSize) {
        // Create a new array
        var newArr = new Array(newSize);
        // Copy the elements from the old array to the new array
        for (var i = 0; i < this.count; i++) {
            newArr[i] = this.arr[(this.start + i) % this.size];
        }
        this.arr = newArr;
        // Reset the start and end pointers
        this.start = 0;
        this.end = this.count;
        this.size = newSize;
    }

    // Add an element at the head of the array, time complexity O(1)
    addFirst(val) {
        // Double the size of the array if it is full
        if (this.isFull()) {
            this.resize(this.size * 2);
        }
        // Since start is a closed interval, decrement first, then assign
        this.start = (this.start - 1 + this.size) % this.size;
        this.arr[this.start] = val;
        this.count++;
    }

    // Remove an element from the head of the array, time complexity O(1)
    removeFirst() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        // Since start is a closed interval, assign first, then increment
        this.arr[this.start] = null;
        this.start = (this.start + 1) % this.size;
        this.count--;
        // Shrink the array size to half if the number of
        // elements reduces to one-fourth of the original
        if (this.count > 0 && this.count == this.size / 4) {
            this.resize(this.size / 2);
        }
    }

    // Add an element at the tail of the array, time complexity O(1)
    addLast(val) {
        if (this.isFull()) {
            this.resize(this.size * 2);
        }
        // Since end is an open interval, assign first, then increment
        this.arr[this.end] = val;
        this.end = (this.end + 1) % this.size;
        this.count++;
    }

    // Remove an element from the tail of the array, time complexity O(1)
    removeLast() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        // Since end is an open interval, decrement first, then assign
        this.end = (this.end - 1 + this.size) % this.size;
        this.arr[this.end] = null;
        this.count--;
        // Shrink the array size
        if (this.count > 0 && this.count == this.size / 4) {
            this.resize(this.size / 2);
        }
    }

    // Get the element at the head of the array, time complexity O(1)
    getFirst() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        return this.arr[this.start];
    }

    // Get the element at the tail of the array, time complexity O(1)
    getLast() {
        if (this.isEmpty()) {
            throw new Error("Array is empty");
        }
        // end is an open interval pointing to the next element's position, so subtract 1
        return this.arr[(this.end - 1 + this.size) % this.size];
    }

    isFull() {
        return this.count === this.size;
    }

    size() {
        return this.count;
    }

    isEmpty() {
        return this.count === 0;
    }
}

Thought Exercise

Is the efficiency of adding and removing elements at the head of an array really limited to $O(N)$?

We often say that the time complexity for adding and removing elements at the head of an array is $O(N)$ because it requires shifting elements. However, if we use a circular array, we can actually achieve adding and removing elements at the head with a time complexity of $O(1)$ .

Of course, this implementation of a circular array only provides methods like addFirst, removeFirst, addLast, removeLast, and does not include some methods found in the dynamic array we implemented earlier, such as deleting an element at a specific index, retrieving an element at a specific index, inserting an element at a specific index, etc.

But consider this: is it really impossible for a circular array to implement these methods? When implementing these methods with a circular array, does the time complexity degrade compared to a normal array?

It seems not.

A circular array can also delete an element at a specified index, which requires shifting data, just like a regular array, with a complexity of $O(N)$ ;

A circular array can also access an element at a specified index (random access), although it requires calculating the actual index using start, but the calculation and access time complexity remain $O(1)$ ;

A circular array can also insert an element at a specified index, which also requires shifting data, just like a regular array, with a complexity of $O(N)$ .

Consider whether this is the case. If it is, why don't the standard libraries of programming languages use the circular array technique for their dynamic array containers?