Динамический массив добавить в конце?

Question

Начиная с динамического массива с начальной длиной = 4 и numElements = 0, показать массив, когда мы добавим в конце следующие числа: 5, 19, 4, 6, -1.

Контрольная точка(ответ) Я получаю [5, 19, 4, 6, -1, X, X, X], где X обозначает записи, которые можно игнорировать.

У меня есть 2 глупых вопроса:

1. Я думал, что вставка в конце сделает его [X, X, X, 5, 19, 4, 6, -1] вместо того, как это выглядит прямо сейчас в ответе?

2. Первоначально, хотя каждый раз, когда мы добавляем что-либо в массив, массив автоматически удваивает его длину, поэтому у нас есть 3 X в конце, в результате чего общая длина окончания равна 8вместо начального размера 4. Это правильно?

Answer 1

Это работает следующим образом.

«Добавление в конец» означает добавление в конец массива. Давайте сначала сделаем это, не беспокоясь о внутренностях.

Сначала список пуст

[]

Затем вставьте 5

[5]

Затем 19

[5, 19]

Затем 4, затем 6, затем -1

[5, 19, 4]
[5, 19, 4, 6]
[5, 19, 4, 6, -1]

Теперь, как это выглядит, когда у нас есть массивы, емкость которых кратна 4. Как вы говорите, они удваиваются в размере, когда заполняются,Итак, это прогрессия:

X  X  X  X

5  X  X  X

5 19  X  X

5 19  4  X

5 19  4  6

5 19  4  6 -1  X  X  X

При вставке первых 4 элементов блок из 4 заполняется. При вставке 5-го у нас нет места, поэтому мы должны удвоить емкость до 8, а затем поместить 5-й элемент в первый доступный слот.

Так что да, вы правы в удвоении емкости. Но элементы массива всегда заполняются с самого начала неиспользуемыми слотами в конце. Если вы ставите значения в конце, вам придется сдвигать их влево при каждой вставке, что будет очень неэффективно.