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 ...