Implementation of a dynamic list-like array

I needed to address an issue that I met with quite a bit, which has sort of a bag of data that I can easily add items and remove them, and iterate over them at any point without an issue.

First thing that came to mind was to use a linked list: easy to add, easy to remove, without having blank spaces in between, but the use of a linked list didn't look optimal to me.

I made a class in Java called BagArray that behaves like a list in terms of adding and removing items, and is easily iterated over with a for-each without having blank spaces.

It is a mix of a normal array to store the data, and a stack that stores indices of the normal array in which it is free to add an item without deleting another one.

```
import java.util.Iterator;

public class BagArray implements Iterable {

private final Object mItems[];
private final int mSlots[];
private int mSlotsTop = -1;

public final int size;

public BagArray(int size) {
this.size = size;
mItems = new Object[size];
mSlots = new int[size];
for (int i = 0; i = size)
throw new IndexOutOfBoundsException();
return (T) mItems[i];
}

public void remove(int i) {
if (i size)
return;
if (mItems[i] == null)
return;
mItems[i] = null;
pushSlot(i);
}

public void remove(T item) {
remove(indexOf(item));
}

public boolean isFull() {
return mSlotsTop == -1;
}

public boolean isEmpty() {
return mSlotsTop == size - 1;
}

public int numFreeSlots() {
return mSlotsTop + 1;
}

public int indexOf(T item) {
for (int i = 0; i iterator() {
return new Iterator() {
private int index = -1;

@Override
public boolean hasNext() {
do {
index++;
if (index >= size)
return false;
} while (mItems[inde

This is an interesting concept, a size-limited "bucket" of not-guaranteed-order items. You are right that the add and remove are O(1) operations, but there are a number of concerns I have.... some of them are severe.

• If someone adds a null value, you are broken in the iterator. You need to accommodate null, or throw an exception.

• The get(int) and remove(int) methods are useless - how does the user know what int to use? The first item added is placed at index size - 1, and so on, so how does that work?

Then, there's a trick with Collections that have a generic type. The general concensus in Java is that you should pass the class definition in to the constructor. The standard Java collections can't do that for backward compatibility reasons, but, consider this:

public class BagArray implements Iterable {

    private final T[] mItems;
    public BagArray(Class tClass, int size) {
        @SuppressWarnings("unchecked")
        mItems = (T[]) Array.newInstance(tClass, size);

Note two things there...

• In Java, by convention, you declare arrays as T[] mItems, and not T mItems[]

• The array now has the correct type, and there's only one place you need to cast the values, and that is in the array creation.

One last thing, in Java 8, a nice trick for creating an array populated with sequential numbers is:

int[] values = IntStream.range(startInclusive, endExclusive).toArray();

StackExchange Code Review Q#106302, answer score: 6