“Структура данных «Массив» имеет фиксированный размер”. Это всегда так?

#массивы #структуры_данных #динамические_массивы

В статье про структуру данных связанный список, автор пишет про недостатки массива:


  1) The size of the arrays is fixed: So we must know the upper limit on
  the number of elements in advance...


и тут же во втором пункте, как мне кажется, он это опровергает


  2) Inserting a new element in an array of elements is expensive...


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

Ответы

Ответ 1

Важно различать элемент и место под элемент. Массив не всегда весь заполнен, но даже
незаполненная часть занимает память1. Фиксировано в массиве число мест. Элементов в
массиве ненулевой длины может не быть.

Из-за особенностей хранимого типа может быть невозможно иметь в массиве ячейку без
значения, но это лишь техническая деталь — если значение не имеет смысла, для алгоритма
его всё равно что нет. И следить за такой ситуацией можно, храня где-то неподалёку
число "полезных элементов", если вы заполняете массив последовательно от начала (что
бывает не всегда).



Во втором пункте говорится о дороговизне вставки элемента в произвольное место с
сохранением существующих элементов массива и порядка их следования2.

Чтобы её осуществить когда место занято, нужно все элементы, начиная с запрашиваемого
места и вверх по индексам до конца заполненной части массива, переместить на одно место
вперёд. Худший случай — вставка в начало, когда необходимо сдвинуть вперёд всю заполненную
часть массива.

Для сравнения, для вставки элемента в связный список (с тем же требованием сохранить
порядок) необходимо лишь создать запись списка с элементом и прописать её в указывающего
на неё соседа (или двух, если список двусвязаный). Такая богатая на переходы по ссылкам
структура заметно замедляет обход, но в некоторых узких нишах она удобна.

Нет, динамические массивы тут ни при чём.



1 если не используется трюков вроде разрежения, но с ними это уже не тот примитивный
массив, о котором речь

2 в пределах двух частей, на которые вставляемный элемент этот массив разделяет