Solution: Array-Based Lists

Task

Here is the solution that implements 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 reason why implementing addAll(i, c) by repeated calls to add(i, x) is not efficient is the following:

If we consider an ArrayList as the underlying data structure, the add(i, x) operation has a time complexity of $O(n)$ ...