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

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy