Reason: ArrayList implementation is based on an array, with a pointers to the start and end of the array.
(1) When you remove the first or last items, the pointers are moved. If you remove and items from the middle all the items after the removed location are shifted.
(2) After many removes/adds the start pointer is set so high the ArrayList is forced to shift all the items.
Solution: when removing item - swap the item with the last item, and remove the last item. Drawback - you lose the order of the items in the ArrayList.
import java.util.ArrayList;
import java.util.ArrayList;
import java.util.Collection;
public class SwapArrayListextends ArrayList {
private static final long serialVersionUID = 2995040970224168173L;
public SwapArrayList() {
this(0);
}
public SwapArrayList(int capacity) {
super(capacity);
}
public SwapArrayList(Collection collection) {
super(collection);
}
@Override
public boolean remove(Object object) {
int index = indexOf(object);
if (index >= 0) {
int size = this.size();
if (index < size - 1) {
// Swap the last item with the item to be removed
E tmp = this.get(size - 1);
this.set(size - 1, this.get(index));
this.set(index, tmp);
index = size - 1;
}
remove(index);
return true;
}
return false;
}
@Override
public E remove(int location) {
int size = this.size();
if (0 <= location && location < size) {
if (location < size - 1) {
// Swap the last item with the item to be removed
E tmp = this.get(size - 1);
this.set(size - 1, this.get(location));
this.set(location, tmp);
location = size - 1;
}
} else {
throw new IndexOutOfBoundsException();
}
return super.remove(location);
}
}
