How to replace X items of ArrayList with Y items (X might be very large, and different from Y) , efficiently?

Question

Background

ArrayList is known to have bad performance in case you want to perform a lot of modifications on it (insert/remove), as it uses an array behind the scenes.

The reason is that for each insert/remove, cells are shifted aside, as ArrayList is using a simple array behind the scenes.

This means, for example, that if you have N items in the ArrayList, and you add M items into it (say, in the beginning), it might take at least O(N*M) to add them.

This is also written in the docs. About addition:

Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

and about removal:

Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).

This is why a simple loop of add operation is out of the question, as I might need to add a lot of items to an already large list of items.

The problem

I wish to be able to remove and optionally replace items of an ArrayList, even with items count that's different than the original one.

For example:

if the input is an array of {0,1,2,3,4,5}, I could replace the "1" item with 2 items "99","100" so that the output would be {0,99,100,2,3,4,5}

What I've tried

It is possible to remove multiple items as such:

    final ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i <= 5; ++i)
        list.add(i);
    // list is {0,1,2,3,4,5}
    list.subList(1, 2).clear();
    // list is now {0,2,3,4,5}

This is better than removing items one by one, as I think this won't shift the cells of the array within the ArrayList object.

What I really want, is to replace items, so this is what I've made :

public static void replaceItems(ArrayList<Integer> list, int fromIndex, int toIndexExcluding, ArrayList<Integer> deltaItems) {
    int indexToTakeItemFrom = 0;
    Log.d("AppLog", "sizeBefore:" + list.size());
    int minEnsuredCapacity = list.size() - (toIndexExcluding - fromIndex) + deltaItems.size();
    Log.d("AppLog", "minEnsuredCapacity:" + minEnsuredCapacity);
    list.ensureCapacity(minEnsuredCapacity);
    //replacing items:
    for (int i = fromIndex; i < toIndexExcluding && i < list.size(); ++i) {
        if (indexToTakeItemFrom >= deltaItems.size()) {
            list.subList(i, toIndexExcluding).clear();
            Log.d("AppLog", "size after:" + list.size());
            return;
        }
        list.set(i, deltaItems.get(indexToTakeItemFrom++));
    }
    //add remaining items
    list.addAll(fromIndex + indexToTakeItemFrom, deltaItems.subList(indexToTakeItemFrom, deltaItems.size()));
    Log.d("AppLog", "size after:" + list.size());
}

This seems to work well. Examples:

// list is {0,1,2,3,4,5}
replaceItems(list, 1, 1, deltaList); //nothing to replace, so just add {99,100} to index 1
//list is now {0,99,100,1,2,3,4,5}

// list is {0,1,2,3,4,5}
replaceItems(list, 1, 2, deltaList); //replace {1} with {99,100}
//list is now {0,99,100,2,3,4,5}

// list is {0,1,2,3,4,5}
replaceItems(list, 1, 3, deltaList); //replace {1,2} with {99,100}
//list is now {0,99,100,3,4,5}

// list is {0,1,2,3,4,5}
replaceItems(list, 1, 4, deltaList); //replace {1,2,3} with {99,100}
//list is now {0,99,100,4,5}

In terms of efficiency, since the shifting is done 1-2 times at most, it should be O(M+N), and not O(M*N), where M is the number of items to replace, and N is the number of current items in the list.

The questions

1. Is my code correct? Have I forgotten of some end cases? Maybe capacity calculation is wrong in some cases?

2. Does subList even create a new List object, copying items from the original? Or does it just have some basic pointers behind the scenes, which are constant in size, so I shouldn't worry about using it?

3. Is it the most efficient one I could make, given that I use ArrayList? Is there maybe a better API to use for this? Is there a way to simplify how this works? Does my code shift cells only when it really needs, and only max of a constant times (instead of based on input) ?

Answer 1

Since you already understand how you can do bulk removal and insertion efficiently using subList(), why don't you combine the two by first bulk removing the desired range by clear()ing the sublist, and then bulk adding the desired elements into the same subList?

I'm not sure what exactly you're trying to achieve, but if I understand it right then it should be possible efficiently via:

public static void replaceItems(ArrayList<Integer> list, int fromIndex, int toIndexExcluding, ArrayList<Integer> deltaItems) {
    List<Integer> subList = list.subList(fromIndex, toIndexExcluding);
    subList.clear();
    subList.addAll(deltaItems);
}

But maybe I misunderstand because I have no idea why your code contains a for loop; that doesn't look correct?

Answer 2

Do you have a particular reason to be using an ArrayList in this case?

If you're going to be manipulating the List a lot in this fashion, a LinkedList might be more appropriate as it will perform better on insertions and removals elements.

If that's not the case, ArrayList manipulation is certainly an option, however like mentioned by others, arrays (int[]) would be better suited.

Answer 3

I dont know why you need to do all this in this way ...

ArrayList<Integer> list
list.remove(indexNumber); //remove the index and shift all element
list.add(indexNumber, value); // add a value in indexNumber index and shift all element

Now if you want to remove multiple item, use a loop. If you want multiple items, then also use a loop.