Circular Array Technique

labuladongOriginalAbout 3598 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 may notice that when there is no space at the head to add a new element, it circles around and adds the new element to the tail.

Core Principle

The above example provides an intuitive understanding of a circular array. The key to a circular array is maintaining two pointers: start and end. The start pointer indicates the index of the first valid element, while the end pointer points to the index of the next position after the last valid element.

This setup allows us to add or remove elements at the head of the array by simply moving the start index, and at the tail of the array by moving the end index.

When start or end moves beyond the array boundaries (< 0 or >= arr.length), we can use the modulo operation % to loop them back to the head or tail of the array, thus achieving the effect of a circular array.

Hands-On Section

Theory alone is never enough; true understanding comes from practice.

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

Code Implementation

Key Points: Open and Closed Intervals

In my code, the circular array interval 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 and right-open interval.

Some readers might wonder why it is necessary to use a left-closed and right-open interval, and whether it's possible to have both ends open or closed.

When defining the boundaries of a sliding window in Sliding Window Algorithm Core Framework, similar questions arise. Let me explain here as well.

In theory, you can design the intervals' openness and closeness as you wish, but generally, designing it as a left-closed and right-open interval is the most convenient.

This is because when you initialize start = end = 0, the interval [0, 0) contains no elements. However, by moving end one position to the right, the interval [0, 1) then includes one element 0.

If you set the interval as both open, moving end to the right by one position would still result in an open interval (0, 1) with no elements; if you set the interval as both closed, the initial interval [0, 0] already contains one element. Both situations would cause unnecessary complications in handling boundaries. If you insist on using these setups, special handling in the code would be required.

Finally, I provide a Java implementation supporting generics 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 or removing elements from the head of an array really limited to $O(N)$ ?

It is often said that the time complexity for adding or removing elements from the head of an array is $O(N)$ due to the need to shift elements. However, by using a circular array, it is actually possible to achieve these operations in $O(1)$ time complexity.

Of course, the circular array implementation mentioned above only provides methods like addFirst, removeFirst, addLast, and removeLast. It does not offer certain methods found in the dynamic array we implemented earlier, such as deleting an element at a specified index, accessing an element at a specified index, or inserting an element at a specified index.

But consider this: is it really impossible for a circular array to implement these methods? If a circular array can implement these methods, is there any degradation in time complexity compared to a regular array?

It seems there isn't.

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

A circular array can access an element at a specified index (random access), though instead of directly accessing the corresponding index, it calculates the real index using start, but the computation and access time complexity remains $O(1)$ ;

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

Consider whether this is the case. If so, why do the dynamic array containers provided by the standard libraries of programming languages not utilize the circular array technique under the hood?