Get a sublist from an ArrayList efficiently

Question

My Problem

---

I have a fixed-size ArrayList which contains custom variables. Despite of the ArrayList having a fixed size, sometimes a lot of them will actually be null. The thing is that I need to return the ArrayList without the null variables inside it. One important thing to note: the ArrayList will have all of its non-null items first, and then all of the nulls below them, e.g., the elements are not mixed. Example: [non-null, non-null, .... null, null, null]

My workaround

---

I though of creating a for-loop that checked (from last to first index) each of the elements inside the ArrayList to determine if it's null or not. If is null, then I'd call this code:

for (i = size-1; i >=0 ; i--) {
    groupList = new ArrayList<>(groupList.subList(0, i));
}

My question

---

If the ArrayList is too big, this method might me particularly slow (or not?). I was wondering if there exists a better, more performance-friendly solution. AFAIK the .subList method is expensive.

Answer 1

You can have a variant of binary search, where your custom comparator is:

• Both elements are null/not null? They are equal
• Only one element is null? The none null is "smaller".

You are looking for the first null element.

This will take O(logn) time, where n is the size of the array.

However, taking the sublist of the ArrayList that is none null (assuming you are going to copy it to a new list object), is going to be linear time of the elements copied, since you must "touch" each of them.

This gives you total time complexity of O(logn + k), where k is number of non null elements, and n is the size of the array.

Answer 2

Following all of your outstanding advices, I modified the original method so that I can take the last (first) ever null item position and call the .subList method just once. And here it is:

int lastNullIndex = size - 1;

for (i = lastNullIndex; i >= 0; i--) {
    if (null == groupList.get(i)) {
        lastNullIndex = i;
    } else {
        break;
    }
}

groupList = new ArrayList<>(groupList.subList(0, lastNullIndex));
return groupList;

If you think it can be further modified so as to allow for a better performance, let us know.