027Circular Array List

Author: Dr. Heinz M. KabutzDate: 2001-08-02Java Version: 1.2Category: Performance

Abstract: ArrayList can become slow when used as a FIFO queue. Whenever an element is removed from the head, the other elements need to be moved one space to the left. This is an O(n) operation and slows down the remove(0) operation the longer the list becomes. In this newsletter we describe a CircularArrayList that allows us to remove elements from the front in O(1).

Welcome to the 27th issue of The Java(tm) Specialists' Newsletter. Last week I was talking to a friend about keyboards and he mentioned what a pity it was that we had grown up on QWERTY, when Dvorak is sooo much better for the fingers. I'm sure you've heard the story that QWERTY was designed to slow you down? He also mentioned that some students he studied with removed all the keys from their keyboards and arranged them in Dvorak order. "What a good idea!", I thought, promptly removing all the keys from my notebook and dropping them down in Dvorak order. There are two problems, however:

1. I touch type QWERTY, so until I find the time to learn Dvorak I want to continue QWERTYing. Some Java applications (JBuilder4, JProbe, etc.) have the extremely annoying habit of changing my input locale to the bottom selection, in my case Dvorak.
2. Three of the keys are different sizes to the rest of the keys, so in order to remember what they are supposed to be, I stuck stickers on them and the places where they are supposed to be, and wrote on them the appropriate Dvorak keys. Whenever someone sees my notebook now, they ask: "Why do you have stickers on your keys?" They don't see that ALL the keys are in the wrong place! Sometimes we are like that too when it comes to Java. We say: "Java is slow!" In the meantime, we use the wrong collections, we create too many objects, we use += with Strings and print new java.util.Date() to the console in a tight loop. When people make statements like "Java is a memory hog" they are demonstrating that they are not looking at the whole picture.

One of the advantages in writing this newsletter is that I get some excellent feedback on some of the things I write about. In newsletter 24 I spoke about self-tuning FIFO queues, the purpose of which was to demonstrate some ideas on self-adapting code, rather than propose a good FIFO implementation. Ecce Jezuch from Poland suggested that I write a circular Array list instead of this self-adapting silly nonsense code, and while we were debating what it would take to give up his summer weather to write such a construct, I received sample code of a partial implementation from Allard Siemelink, an independent Java contractor in the Netherlands. It is quite simple writing a basic circular array FIFO queue, but I didn't think a basic solution would be acceptable to my readers.

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

Circular Array List

In this newsletter I present an implementation of java.util.List, which I call the CircularArrayList. It can be used exactly as an ArrayList, i.e. you can remove elements from anywhere in the list, you can add elements to the list, get the size, convert it to an array with the toArray method etc. Some of the methods I've left as an exercise to the reader.

So, the question I didn't answer in newsletter 24 was why java.util.ArrayList is so bad as a FIFO queue when the list contains a lot of elements. I assumed that anybody who had subscribed to an Advanced Java(tm) newsletter had at least read the source code of that class and already knew the answer. I think my assumption is probably correct, but here is the source of trouble anyway:

public Object remove(int index) {
  RangeCheck(index);

  modCount++;
  Object oldValue = elementData[index];

  int numMoved = size - index - 1;
  if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);
   elementData[--size] = null; // Let gc do its work
   return oldValue;
}

In a FIFO queue, we are adding to the back and removing from the front, so if we call remove(0) on a list of 100 elements, numMoved will equal 99, which will cause a call to System.arraycopy(elementData, 1, elementData, 0, 99);. This is the reason why the ArrayList deteriorates as a FIFO queue when it reaches a certain length.

What follows it a CircularArrayList that looks like the ArrayList except that it has a head and a tail that show the first and last elements in the Object element array. In the ArrayList, the head would always be 0. I've written some comments before each method so you can figure out what it does. I recommend that you read the source code of java.util.ArrayList before reading this code.

// CircularArrayList.java
import java.util.*;
import java.io.*;

public class CircularArrayList extends AbstractList
  implements List, Serializable
{
  private Object[] elementData;
  // head points to the first logical element in the array, and
  // tail points to the element following the last.  This means
  // that the list is empty when head == tail.  It also means
  // that the elementData array has to have an extra space in it.
  private int head=0, tail=0;
  // Strictly speaking, we don't need to keep a handle to size,
  // as it can be calculated programmatically, but keeping it
  // makes the algorithms faster.
  private int size=0;

  public CircularArrayList() {
    this(10);
  }

  public CircularArrayList(int size) {
    elementData = new Object[size];
  }

  public CircularArrayList(Collection c) {
    // we also have to set the size - bug discovered by
    // Jos van der Til from the Netherlands
    size = tail = c.size();
    elementData = new Object[c.size()];
    c.toArray(elementData);
  }

  // The convert() method takes a logical index (as if head was
  // always 0) and calculates the index within elementData
  private int convert(int index) {
    return (index + head) % elementData.length;
  }

  public boolean isEmpty() {
    return head == tail; // or size == 0
  }

  // We use this method to ensure that the capacity of the
  // list will suffice for the number of elements we want to
  // insert.  If it is too small, we make a new, bigger array
  // and copy the old elements in.
  public void ensureCapacity(int minCapacity) {
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
      int newCapacity = (oldCapacity * 3)/2 + 1;
      if (newCapacity < minCapacity)
          newCapacity = minCapacity;
      Object newData[] = new Object[newCapacity];
      toArray(newData);
      tail = size;
      head = 0;
      elementData = newData;
    }
  }

  public int size() {
    // the size can also be worked out each time as:
    // (tail + elementData.length - head) % elementData.length
    return size;
  }

  public boolean contains(Object elem) {
    return indexOf(elem) >= 0;
  }

  public int indexOf(Object elem) {
    if (elem == null) {
      for (int i = 0; i < size; i++)
        if (elementData[convert(i)]==null)
          return i;
    } else {
      for (int i = 0; i < size; i++)
        if (elem.equals(elementData[convert(i)]))
          return i;
    }
    return -1;
  }

  public int lastIndexOf(Object elem) {
    if (elem == null) {
      for (int i = size-1; i >= 0; i--)
        if (elementData[convert(i)]==null)
          return i;
    } else {
      for (int i = size-1; i >= 0; i--)
        if (elem.equals(elementData[convert(i)]))
          return i;
    }
    return -1;
  }

  public Object[] toArray() {
    return toArray(new Object[size]);
  }

  public Object[] toArray(Object a[]) {
    if (a.length < size)
      a = (Object[])java.lang.reflect.Array.newInstance(
        a.getClass().getComponentType(), size);
    if (head < tail) {
      System.arraycopy(elementData, head, a, 0, tail-head);
    } else {
      System.arraycopy(elementData, head, a, 0,
        elementData.length-head);
      System.arraycopy(elementData, 0, a, elementData.length-head,
        tail);
    }
    if (a.length > size)
      a[size] = null;
    return a;
  }

  private void rangeCheck(int index) {
    if (index >= size || index < 0)
      throw new IndexOutOfBoundsException(
        "Index: "+index+", Size: "+size);
  }

  public Object get(int index) {
    rangeCheck(index);
    return elementData[convert(index)];
  }

  public Object set(int index, Object element) {
    modCount++;
    rangeCheck(index);
    Object oldValue = elementData[convert(index)];
    elementData[convert(index)] = element;
    return oldValue;
  }

  public boolean add(Object o) {
    modCount++;
    // We have to have at least one empty space
    ensureCapacity(size + 1 + 1);
    elementData[tail] = o;
    tail = (tail+1)%elementData.length;
    size++;
    return true;
  }

  // This method is the main reason we re-wrote the class.
  // It is optimized for removing first and last elements
  // but also allows you to remove in the middle of the list.
  public Object remove(int index) {
    modCount++;
    rangeCheck(index);
    int pos = convert(index);
    // an interesting application of try/finally is to avoid
    // having to use local variables
    try {
      return elementData[pos];
    } finally {
      elementData[pos] = null; // Let gc do its work
      // optimized for FIFO access, i.e. adding to back and
      // removing from front
      if (pos == head) {
        head = (head+1)%elementData.length;
      } else if (pos == tail) {
        tail = (tail-1+elementData.length)%elementData.length;
      } else {
        if (pos > head && pos > tail) { // tail/head/pos
          System.arraycopy(elementData, head, elementData, head+1,
            pos-head);
          head = (head+1)%elementData.length;
        } else {
          System.arraycopy(elementData, pos+1, elementData, pos,
            tail-pos-1);
          tail = (tail-1+elementData.length)%elementData.length;
        }
      }
      size--;
    }
  }

  public void clear() {
    modCount++;
    // Let gc do its work
    for (int i=head; i!=tail; i=(i+1)%elementData.length)
      elementData[i] = null;
    head = tail = size = 0;
  }

  public boolean addAll(Collection c) {
    modCount++;
    int numNew = c.size();
    // We have to have at least one empty space
    ensureCapacity(size + numNew + 1);
    Iterator e = c.iterator();
    for (int i=0; i < numNew; i++) {
      elementData[tail] = e.next();
      tail = (tail+1)%elementData.length;
      size++;
    }
    return numNew != 0;
  }

  public void add(int index, Object element) {
    throw new UnsupportedOperationException(
      "This method left as an exercise to the reader ;-)");
  }

  public boolean addAll(int index, Collection c) {
    throw new UnsupportedOperationException(
      "This method left as an exercise to the reader ;-)");
  }

  private synchronized void writeObject(ObjectOutputStream s)
      throws IOException {
    s.writeInt(size);
    for (int i=head; i!=tail; i = (i+1)%elementData.length)
      s.writeObject(elementData[i]);
  }

  private synchronized void readObject(ObjectInputStream s)
      throws IOException, ClassNotFoundException {
    // Read in size of list and allocate array
    head = 0;
    size = tail = s.readInt();
    elementData = new Object[tail];
    // Read in all elements in the proper order.
    for (int i=0; i < tail; i++)
      elementData[i] = s.readObject();
  }
}

There are some bugs in the code above. Please don't ask me what they are; obviously I don't know what the bugs are, else they would not be there anymore. If you do find a bug, please tell me so that I can send an errata next week. I've tried to test the CircularArrayList against an ordinary ArrayList for correctness, and against an ArrayList and a LinkedList for performance.

// ArrayListTest.java
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

public class ArrayListTest {
  public static String testList(List list) {
    StringBuffer result = new StringBuffer(1024);
    list.add("ABCD");
    list.add("EFGH");
    list.add("IJKL");
    list.addAll(list);
    result.append(list);
    result.append(list.contains("IJKL"));
    result.append(list.containsAll(new ArrayList()
      {{add("ABCD");add("EFGH");}}));
    result.append(list.equals(new ArrayList(list)));
    for (int i=0; i<6; i++)
      result.append(list.get(i));
    result.append(list.indexOf("EFGH"));
    result.append(list.isEmpty());
    result.append(list.lastIndexOf("EFGH"));
    for (int i=0; i<3; i++) result.append(list.remove(3));
    for (int i=0; i<3; i++) result.append(list.remove(0));
    for (int i=0; i<6; i++) list.add(Integer.toString(i));
    for (int i=0; i<6; i++) result.append(list.get(i));
    Object[] els = list.toArray();
    for (int i=0; i<els.length; i++) result.append(els[i]);
    String[] strs = (String[])list.toArray(new String[0]);
    for (int i=0; i<strs.length; i++) result.append(strs[i]);
    for (int i=0; i<32; i++) {
      list.add(Integer.toHexString(i));
      result.append(list.remove(0));
    }
    result.append(list);
    return result.toString();
  }
  public static void testPerformance(List list, int length) {
    Object job = new Object();
    int iterations = 0;
    for (int j=0; j<length; j++) list.add(job);
    long time = -System.currentTimeMillis();
    while(time + System.currentTimeMillis() < 2000) {
      iterations++;
      for (int j=0; j<100; j++) {
        list.remove(0);
        list.add(job);
      }
    }
    time += System.currentTimeMillis();
    System.out.println(list.getClass() + " managed " +
      iterations + " iterations in " + time + "ms");
  }
  public static void testCorrectness() {
    String al = testList(new ArrayList(6));
    String cal = testList(new CircularArrayList(6));
    if (al.equals(cal)) System.out.println("Correctness Passed");
    else {
      System.out.println("Expected:");
      System.out.println(al);
      System.out.println("But got:");
      System.out.println(cal);
    }
  }
  public static void testPerformance(int length) {
    System.out.println("Performance with queue length = " + length);
    testPerformance(new ArrayList(), length);
    testPerformance(new LinkedList(), length);
    testPerformance(new CircularArrayList(), length);
  }
  public static void main(String[] args) {
    testCorrectness();
    testPerformance(1);
    testPerformance(10);
    testPerformance(100);
    testPerformance(1000);
    testPerformance(10000);
    testPerformance(100000);
  }
}

I've tried this out on my trusty notebook with the stickers on the keys. I again count iterations rather than amount of time it takes, as that gives me far more accurate figures. The ArrayList beats our CircularArrayList if there is only one element on the list, since ArrayList in that case does not have to do any copying of elements with System.arraycopy(). The CircularArrayList has a few overheads more than the ArrayList, which make it marginally slower in that one case. Besides that one case, CircularArrayList beats the stuffing out of the other lists for FIFO queue behaviour, AND it can behave as an ordinary ArrayList as well. This makes me wonder why Sun Microsystems didn't implement ArrayList as a CircularArrayList in the first place? I wish I knew the answer to that.

Correctness Passed
Performance with queue length = 1
class java.util.ArrayList managed 145246 iterations in 2003ms
class java.util.LinkedList managed 42385 iterations in 2003ms
class CircularArrayList managed 51058 iterations in 2013ms
Performance with queue length = 10
class java.util.ArrayList managed 51236 iterations in 2003ms
class java.util.LinkedList managed 41188 iterations in 2003ms
class CircularArrayList managed 54124 iterations in 2003ms
Performance with queue length = 100
class java.util.ArrayList managed 27019 iterations in 2003ms
class java.util.LinkedList managed 39529 iterations in 2003ms
class CircularArrayList managed 52938 iterations in 2004ms
Performance with queue length = 1000
class java.util.ArrayList managed 5300 iterations in 2003ms
class java.util.LinkedList managed 39132 iterations in 2003ms
class CircularArrayList managed 50893 iterations in 2003ms
Performance with queue length = 10000
class java.util.ArrayList managed 535 iterations in 2003ms
class java.util.LinkedList managed 13102 iterations in 2003ms
class CircularArrayList managed 52030 iterations in 2003ms
Performance with queue length = 100000
class java.util.ArrayList managed 9 iterations in 2063ms
class java.util.LinkedList managed 8002 iterations in 2003ms
class CircularArrayList managed 50803 iterations in 2003ms

There you go, I hope you bothered to read and try to understand my code. Please remember to forward this newsletter to interested parties.

Heinz

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive