Get a Subscription from ArrayList Effectively

Question

My problem

---

I have a fixed size ArrayList that contains user variables. Despite the fact that ArrayList has a fixed size, sometimes many of them will be practically null. The thing is, I need to return an ArrayList without null variables inside it. It is important to note: ArrayList will first have all its non-zero elements, and then all zeros under them, for example, the elements will not be mixed. Example: [non-null, non-null, .... null, null, null]

My workaround

---

I would like to create a for loop that checks (from the last to the first index) each of the elements inside an ArrayList to determine if it is null or not. If it is null, I would call this code:

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

My question

---

If the ArrayList is too large, this method can be especially slow (or not?). I was wondering if there is a better, more efficient solution. AFAIK .subList method is expensive.

Answer 1

You might have a binary search option where your custom comparator is:

• Are both elements null / not null? They are equal.
• Only one element is null? No null is "lesser".

You are looking for the first null element.

It takes O (logn) time, where n is the size of the array.

However, taking an ArrayList sublist, which is not null (provided that you are going to copy it to a new list object), the linear time of the elements being copied will be executed, since you must “touch” each of them.

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

Answer 2

Following all your outstanding tips, I modified the original method so that I can take the last (first) position with a zero element and call the .subList method only once. And here he 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 that it can be further modified to provide better performance, let us know.