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

В статье про структуру данных связанный список, автор пишет про недостатки массива
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. Фиксировано в массиве число мест. Элементов в массиве ненулевой длины может не быть.
Из-за особенностей хранимого типа может быть невозможно иметь в массиве ячейку без значения, но это лишь техническая деталь — если значение не имеет смысла, для алгоритма его всё равно что нет. И следить за такой ситуацией можно, храня где-то неподалёку число "полезных элементов", если вы заполняете массив последовательно от начала (что бывает не всегда).

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

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