Solution: Array-Based Lists
Review the solution to a more efficient implementation of the addAll() method in array-based lists.
We'll cover the following...
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 ...