Topic

Dynamic array

Problem

Assume that for a dynamic array of size 22 and capacity 44 we perform the following sequence of operations:

add 5
add 7
add 9
insert 3 1
insert 6 2

提示

Here, add x*x* means that we append an element to the array, insert x*x* ii means that we insert xx to the array at the ii-th index (assuming zero-based indexing).

How many copy operations of an individual array element will we perform when doing the required operations with the array?

Note that elements are copied in the following cases:

• When the array capacity increases, all elements from the old array are copied.
• When we insert an element into the middle of the array. In this case, all elements from the right half of the array are copied after the inserted element, starting at the index of the inserted element.

Write down the total number of times any individual element will be copied assuming that the scaling factor is 2.

Enter a number:

12

Correct.

Hint & Explain

Saying our dynamic array is initially: | * | * | | |

• adding 5 and 7: | * | * | add(5) | add(7) |
• a resize while adding 9, will copy 4 elements | copy () | copy () | copy (5) | copy (7) | add(9) | | | |
• the first insertion moves all elements that will follow 3 after inserting it at index 1 ( that means 4 copies starting from the old index 1 before insertion) | * | insert (3) | copy (*) | copy (5) | copy (7) | copy (9) | | |
• then the same with the second insertion, moves all elements that will follow 6 after inserting it at index 2 (that means 4 copies starting from the old index 2 before insertion) | * | 3 | insert (6) | copy (*) | copy (5) | copy (7) | copy (9) | |

Diagrammatize