CircularArrayList for Java

Java applications sometimes need a “sliding window” view on a stream/sequence of data. This can be provided by a List with

  • fast element insertion and removal at opposite ends (like a queue)
  • fast access to random elements in the list (like an array)

Unfortunately, no existing implementation of the List interface in the Java Collections Framework satisfies both of these requirements. ArrayList is slow at inserting/removing at the list’s head, while LinkedList is slow at accessing elements in the list’s interior.

(ArrayDeque in the Java Collections Framework almost works, but its designers did not implement the List interface, thereby (perhaps intentionally) hiding its interior elements.)

This problem can be solved by using a circular array (also called a circular buffer, cyclic buffer, or ring buffer) as the underlying data structure.

So here is the solution: a fully-fledged, ready-to-use implementation supporting generic element type and everything else you would expect from a standard implementation in the Java Collections Framework. By extending AbstractList and wrapping ArrayList, the full implementation is accomplished in under 100 lines of code!

package com.dukamatic.util;
 
import java.util.*;
 
/**
 * If you use this code, please retain this comment block.
 * @author Isak du Preez
 * isak at du-preez dot com
 * www.du-preez.com
 */
public class CircularArrayList<E>
        extends AbstractList<E> implements RandomAccess {
 
    private final int n; // buffer length
    private final List<E> buf; // a List implementing RandomAccess
    private int head = 0;
    private int tail = 0;
 
    public CircularArrayList(int capacity) {
        n = capacity + 1;
        buf = new ArrayList<E>(Collections.nCopies(n, (E) null));
    }
 
    public int capacity() {
        return n - 1;
    }
 
    private int wrapIndex(int i) {
        int m = i % n;
        if (m < 0) { // java modulus can be negative
            m += n;
        }
        return m;
    }
 
    // This method is O(n) but will never be called if the
    // CircularArrayList is used in its typical/intended role.
    private void shiftBlock(int startIndex, int endIndex) {
        assert (endIndex > startIndex);
        for (int i = endIndex - 1; i >= startIndex; i--) {
            set(i + 1, get(i));
        }
    }
 
    @Override
    public int size() {
        return tail - head + (tail < head ? n : 0);
    }
 
    @Override
    public E get(int i) {
        if (i < 0 || i >= size()) {
            throw new IndexOutOfBoundsException();
        }
        return buf.get(wrapIndex(head + i));
    }
 
    @Override
    public E set(int i, E e) {
        if (i < 0 || i >= size()) {
            throw new IndexOutOfBoundsException();
        }
        return buf.set(wrapIndex(head + i), e);
    }
 
    @Override
    public void add(int i, E e) {
        int s = size();
        if (s == n - 1) {
            throw new IllegalStateException("Cannot add element."
                    + " CircularArrayList is filled to capacity.");
        }
        if (i < 0 || i > s) {
            throw new IndexOutOfBoundsException();
        }
        tail = wrapIndex(tail + 1);
        if (i < s) {
            shiftBlock(i, s);
        }
        set(i, e);
    }
 
    @Override
    public E remove(int i) {
        int s = size();
        if (i < 0 || i >= s) {
            throw new IndexOutOfBoundsException();
        }
        E e = get(i);
        if (i > 0) {
            shiftBlock(0, i);
        }
        head = wrapIndex(head + 1);
        return e;
    }
}

Note:

  • Unlike List implementations in the Java Collections Framework, the capacity of this CircularArrayList cannot be changed after creation. This constraint keeps the implementation simple, and is in the spirit of circular buffers anyway.
  • Elements should be inserted at the tail (with add(e)) and removed at the head (with remove(0)), to exploit the O(1) efficiency of this CircularArrayList. With some modification, the reverse direction could also be made efficient. However I prefer, when it is necessary, to instead reverse the indexing (like this: get(size() – i – 1)), so that CircularArrayList can be used as it stands above.

7 Responses to “CircularArrayList for Java”

  • I was led to your site from stack overflow. Your implementation CircularArrayList looks exactly like what I need, so I thought I would ask you to add an explicit mention of the license.

    It is nice to find code that already does what you need, but unfortunate if I cannot use it due to license considerations.

    Best regards from Finland.

    • admin says:

      Thanks for your comment, and sorry for the holidelay. I wrote it for myself originally and you’re free to use it for whatever purpose.

      Unfortunately I’m not so familiar with licensing. If you advise me on what exactly “an explicit mention of the license” entails, I’ll try to add such. (Does it just mean saying “You can use this code for any purpose whatsoever as long as you retain this comment block”?)

      • A few years back it was easier to find information on licenses. Somehow things seem to be less clear now :/

        From a coders perspective, the best situation is to encounter a well-know license which you already know to be okay. Launcpad previously had a list of well known licenses to choose from. For example, when I put my NMEA parser on launchpad hosting, I chose the Simplified BSD license

        https://launchpad.net/nmeatools

        In general any of the ‘free permissive license’ should work http://en.wikipedia.org/wiki/Permissive_free_software_licence

        However, your comment block approach looks pretty good. I would expect that to be sufficient for the occasional coder that wanders in :)

  • Rosendo says:

    Thanks very useful. :D

  • Andrea says:

    This piece of source code is pure piece of CRAP.
    Circular buffer and you write:

    Cannot add element. CircularArrayList is filled to capacity.

    • admin says:

      Assuming you want to emulate silent data overrun like in c-style circular buffers, you should do this:

        if(buf.size()==buf.capacity()){
          buf.remove(0);
        }
        buf.add(e);

      which removes the oldest element to make space for the newest, and runs in O(1).

      It would be a violation of the List contract (which means many JCF features implemented in base classes would break) if elements were to simply start disappearing without being remove()’d explicitly.

  • m4x says:

    Awesome work. Implementation of this saves me a lot of time and effort. Thanks!


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>