Java is the most efficient way to remove a set of elements from an array []

Question

I have something like this

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

What is the most efficient way to remove index position elements 3,4,6,8 ... from myObjects?

I would like to implement an efficient Utility method with a signature like

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

The returned object [] must be a new object of size myObjects.length - elemToRemove.length

Answer 1

You will need to create a new array, since the arrays do not change in size (you cannot “delete” elements by keeping the same array, it will create holes somewhere). I suggest the following:

 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 already sorted without duplicates and contains only the indices valid in the original array. The call to Arrays.copyOf() used only to ensure that the runtime type of the new array is identical to the type of the original array.

If you often have to “delete” data from arrays, which requires the creation of new arrays, then Java arrays may not be the most efficient data structure for you. LinkedList or ArrayList might be more appropriate.

Answer 2

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

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

Answer 3

I would suggest you use LinkedList instead of an array if you want to delete its elements quite often.

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

I think the most efficient way (if you still want to work with arrays) is to create a new array with only the necessary elements from the 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 did not show shouldRemove . I think you should create a set of indexes instead of the elemToRemove array (indexes are unique, so this is the preferred option anyway). Then shouldRemove can be changed to elemToRemove.contains(i) .

---

May offer you another way with Google Collections (I'm not sure if it is effective, but it looks elegant to 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 4

Java arrays are immutable; you cannot just delete elements without allowing holes in the middle.

What you can do is first delete all the events of the elements and then compile the array by filling all the holes; By the way, this is pretty inefficient. Otherwise, you can create a new array only for the right elements, but you need to know the size a priori.

The best you can do is use LinkedList , which has a good opportunity to allow the removal of objects by simply excluding them without generating a single hole, they just disappear from the structure. Then you can use Collection.toArray(..) to get a new array.

Answer 5

If you have arrays that you want to modify, I recommend using various Collections classes such as LinkedList or ArrayList . Regular arrays cannot be changed, so you cannot just add / remove elements.

However, assuming you have two arrays Object[] myObjects and Object[] toRemove , and you needed a function that returned a new array with elements from toRemove removed 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(); }