Копируй меня, копируй меня полностью. java.util.ArrayList

Ненавязчивое описание устройства java.util.ArrayList. Как работает, нюансы и тонкости.  

Массив, как много в этом звуке. Массивы в Java не резиновые, их размер изменить нельзя. Сказано вам 10 элементов? Значит 10. Меньше можно, больше нельзя. Кладите 5, но платите все равно за 10. Таковы правила.

Но, по традиции, Java предоставляет структуру данных, которая ведет себя лояльнее и позволяет хранить больше элементов, чем планировалось. И меньше, разумеется, не нарушая при этом законов рынка "Кладите 5, но платите за 10".

 java.util.ArrayList

Структурой, в которой непосредственно хранятся элементы ArrayList является  массив объектов размером (длины) такой, как задано в конструкторе, если же размер не задан, то да, 10. Платите за 10, помните?

А если не задан:

А что будет делать ArrayList, если настырный покупатель кодер хочет добавить "лишний" элемент к уже хранящимся? Ничего особенного - просто создаст хранилище большего размера, перенесет туда хранящиеся элементы и добавит этот "лишний". Но сначала проведет инвентаризацию и по результатам примет решение:

Или вариант от Open JDK

Есть ретивые товарищи, которые пытаются дергать этот метод самостоятельно. И удивляются, что плоховато выходит. Причина проста - товарищи путают размер хранилища (его емкость) и размер самого ArrayList. Дело в том, что ensureCapacity() не модифицирует поле ArrayList.size,  которое отображает текущий размер ArrayList и которое меняется при манипуляциях с данными.

Но суть моего поста в том, что никаких чудовищ не существует. И магии. И ArrayList не может взять и просто добавить еще одну ячейку к хранилищу. Он заменяет хранилище целиком, на более емкое.

То же самое происходит и при добавлении в конец списка и при добавлении в середину. Добавление в середину вообще интересный механизм. Копируется участок хранилища "вправо" от указанного индекса, а потом переписывается элемент с указанным индексом. Если размера хранилища не хватает для копирования участка со сдвигом вправо, то происходит это... то самое, то что описано выше - замена на хранилище увеличенного объема. Любой каприз за ваши деньги! Но там видите формулу? Жава гуманна, она не добавляет 10 пустых ячеек:

Впрочем, посмотрим правде в глаза. Это не гуманность, это жадность. Жаба! Такие дела...

_{С уважением,
@antabis}