Java - What's the most efficient way of removing a set of elements from an Array[]

Question

I've something like this

Object[] myObjects = ...(initialized in some way)...
int[] elemToRemove = new int[]{3,4,6,8,...}

What's the most efficient way of removing the elements of index position 3,4,6,8... from myObjects ?

I'd like to implement an efficient Utility method with a signature like

public Object[] removeElements(Object[] object, int[] elementsToRemove) {...}

The Object[] that is returned should be a new Object of size myObjects.length - elemToRemove.length

Answer 1

I'd suggest you to use LinkedList instead of array if you want to remove its elements frequently enough.

It's also easy to implement it with array (array->linked list->remove elements->array) but it's not very efficient:

I think, the most efficient way (if you still want to work with arrays) is to create new array with only necessary elements from old array:

Object[] filteredObjects = new Object[myObjects.length - elemToRemove.length];
int j = 0;
for (int i = 0; i < myObjects.length; i++) {
   if (!shouldRemove(i)) {
      filteredObjects[j++] = myObjects[i];
   }
}
myObjects = filteredObjects;

I didn't show shouldRemove. I think you should create a set of indexes instead of elemToRemove array (indexes are unique, so it's a preferred way in any case). Then shouldRemove can be changed to elemToRemove.contains(i).

---

Can suggest you one more way with Google Collections (I'm not sure that it's efficient but it looks elegant for me):

for (int index : elemToRemove) {
    myObjects[i] = null;
}
myObjects = Collections2.filter(Arrays.asList(myObjects), new Predicate<Object>() {
    @Override
    public boolean apply(Object obj) {
        return obj!= null;
    }
}).toArray();

Answer 2

You cannot remove elements from a Java array. What you can do is:

• Create a new array that only has the elements that you want to retain.
• Use Collections instead.

Answer 3

You will need to create a new array, since arrays do not change in size (you cannot "remove" elements while keeping the same array, it would create holes somewhere). I suggest this:

Object[] nobjs = Arrays.copyOf(myObjects, myObjects.length - elemToRemove.length);
for (int i = 0, j = 0, k = 0; i < myObjects.length; i ++) {
    if (j < elemToRemove.length && i == elemToRemove[j]) {
        j ++;
    } else {
        nobjs[k ++] = myObjects[i];
    }
}

This assumes that elemToRemove is already sorted, with no duplicates, and contains only indices valid within the source array. The Arrays.copyOf() call is used only to make sure that the runtime type of the new array is identical to that of the source array.

If you often have to "remove" data from arrays, thus requiring the creation of new arrays, then Java arrays might not be the most efficient data structure for you. LinkedList or ArrayList may be more appropriate.

Answer 4

Java arrays are immutable, you can't just remove items without letting holes in the middle.

What you can do is to first remove all the occurencies of the elements, then compact the array by filling all the holes; this is quite inefficient by the way. Otherwise you can create a new array just for right elements, but you'll need to know the size a priori..

The best thing you can do is to use a LinkedList that has the good thing of allowing removal of objects by just excluding them without generating any hole, they just disappear from the structure. You can then use Collection.toArray(..) to obtain your new array.

Answer 5

If you have arrays that you want to be modifying, then I recommend using various Collections classes, such as LinkedList or ArrayList. Regular arrays can't be resized, so you can't simply add/remove elements.

However, assuming that you had two arrays Object[] myObjects and Object[] toRemove and you needed a function that returned a new array with the elements in toRemove taken away from myObjects:

public static Object[] remove(Object[] myObjects, Object[] toRemove)
{
    HashSet<Object> tr = new HashSet<Object>();
    tr.addAll( Arrays.asList(toRemove) );
    List<Object> removed = new ArrayList<Object>();
    for(Object o : myObjects)
        if( !tr.contains(o) )
            removed.add(o);
    return removed.toArray();
}