Circular Array Technique and Implementation

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 lies in the modulo operation %, which calculates the remainder. When i reaches the last element of the array, i + 1 modulo arr.length becomes 0, effectively returning to the head of the array. This creates a logical circular array that can be traversed indefinitely.

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

Here's how: Suppose we have an array of length 6, currently containing only 3 elements, as shown below (empty positions are marked with _):

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

Now, if we want to remove the element 1 from the head of the array, we can modify the array as follows:

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

That is, we simply mark the position of element 1 as empty without performing any data shifting.

At this point, if we want to add elements 4 and 5 to the head of the array, we can modify the array as follows:

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

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

Core Principle

The above is just to give you an intuitive understanding of a circular array. The key to a circular array is that it maintains two pointers, start and end. start points to the index of the first valid element, and end points to the index of the next position after the last valid element.

This way, when we add or remove elements at the head of the array, we only need to move the start index. Similarly, when we add or remove elements at the tail, we only need to move 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, achieving the effect of a circular array.

Hands-On Section

Reading about it is not enough; you must practice to truly understand.

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 the elements in the arr array:

Code Implementation

Key Points, Pay Attention to Open and Closed Intervals

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

Some readers might ask, why left-closed and right-open? Can't I use both ends open or both ends closed?

Similar questions arise when defining the boundaries of a sliding window in the Sliding Window Algorithm Framework. Here, I will explain.

Theoretically, you can design the interval as you like, but a left-closed, right-open interval is generally the most convenient to handle.

This is because when you initialize start = end = 0, the interval [0, 0) contains no elements. However, as soon as you move end to the right (expanding it) by one position, the interval [0, 1) includes the element 0.

If you set the interval as both ends open, moving end to the right by one position would still leave the open interval (0, 1) with no elements. If you set the interval as both ends closed, the initial interval [0, 0] already includes one element. Both scenarios introduce unnecessary complications in boundary handling. If you insist on using them, you will need to add special handling in your code.

Finally, here is the code implementation:

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?