Solution: Array-Based Lists

Task

Here is the task that implement the List method addAll(i,c) inserts all elements of the Collection, c, into the list at position i. (The add(i, x) method is a special case where c = {x}.) Explain why, for the data structures in this chapter, it is not efficient to implement addAll(i,c) by repeated calls to add(i,x). Design and implement a more efficient implementation.

Solution

The solution to the task we just solved is as follows:

Let’s look at the reason why implementing addAll(i, c) by repeated calls to add(i, x) is not efficient. If we consider an ArrayList as the underlying data structure, the add(i, x) operation has a time complexity of $O(n)$ because it requires shifting all the elements after the insertion point to make room for the new element. It also checks and calls the resize() operation that adds one more memory cell and copies the whole existing array on each call to add(i,x). Therefore, if we use add(i, x) in a loop to add each element from the collection c, the time complexity would be $O(n^2)$, as we would have to shift elements and copy the whole array multiple times for each insertion.

To design a more efficient implementation for addAll(i, c), we can add the efficiency in the following way: adding all needed cells in a single call to the modified resize() and allowing efficient insertion by inserting multiple elements at a specific position shifting all affected elements only once.

We have implemented the conventional addAll() as addAll1() and the efficient version as addAll2(). We have also implemented efficient resize2() to replace the conventional resize() to avoid multiple calls to the same method.