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 consider notifying isak at du-preez dot com
 *  with a brief description of your application.
 * This is free and unencumbered software released into the public domain.
 *  Anyone is free to copy, modify, publish, use, compile, sell, or
 *  distribute this software, either in source code form or as a compiled
 *  binary, for any purpose, commercial or non-commercial, and by any
 *  means.

public class CircularArrayList
		extends AbstractList implements RandomAccess {

	private final int n; // buffer length
	private final List buf; // a List implementing RandomAccess
	private int head = 0;
	private int tail = 0;

	public CircularArrayList(int capacity) {
		n = capacity + 1;
		buf = new ArrayList(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));

	public int size() {
		return tail - head + (tail < head ? n : 0);

	public E get(int i) {
		if (i < 0 || i >= size()) {
			throw new IndexOutOfBoundsException();
		return buf.get(wrapIndex(head + i));
	public E set(int i, E e) {
		if (i < 0 || i >= size()) {
			throw new IndexOutOfBoundsException();
		return buf.set(wrapIndex(head + i), e);
	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);

	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;


  • 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.

9 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

        In general any of the ‘free permissive license’ should work

        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. 😀

  • 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:


      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!

  • Jeffrey Blattman says:

    This isn’t a circular buffer. By definition, a circular buffer is one that doesn’t require shifting. It looks like it’ll work as described, but O(n) insert makes this impractical.

    • admin says:

      No! The shift only happens if you insert into the middle of the queue.

      No shifting will ever happen as long as you only do operations supported by circular buffers (i.e. inserting at the back (appending) and removing from the front (consuming)).

      (The reason for supporting interior-insert and interior-remove operations is just to comply with the JCF List contract.)

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=""> <s> <strike> <strong>

Cheap NFL Jerseys Cheap NFL Jerseys goedkope air max online Basket Air Jordan 11 Christian Louboutin Outlet Cheap Jerseys Wholesale Jerseys Michael Kors Outlet Online Ray Ban Sunglasses Jerseys Wholesale Coach Outlet Store michael jordan air jordan 11 Coach Outlet Cheap NFL Jerseys Kate Spade Outlet Sale air max 90 pas cher junior Wholesale Jerseys Jerseys Cheap nba jerseys vegas Jerseys Wholesale China