Следующая структура данных - динамический массив или как часто его называют в Android разработке -
ArrayList.ArrayList - это самый обычный массив, который при переполнении просто удаляется, а его значения тупо копируются в новый, более вместительный массив, выше на картинке это наглядно продемонстрировано, вообще это очень крутая структура данных, так как сохраняется преимущество массивов - произвольный доступ.Но и есть недостаток связанный с удалением, к примеру надо удалить значение в самом начале, в
ArrayList это реализовано через сдвиг массива на позицию удаляемого значения, то есть чтобы удалить первое значение надо сдвинуть все остальные на одну позицию влево, а это не очень эффективно когда массив имеет приличный размер.Как альтернативный вариант можно вместо сдвига заменять удаляемое значение каким нибудь пустым, например
null, но здесь появляется другой недостаток - при большом количестве удалений пустых мест может быть очень много, а это неэффективный расход памяти. P.S. Если у вас появилось желание прям досконально разобраться во всей внутрянке
ArrayList рекомендую глянуть исходники java.util.ArrayList, там можно найти много интересного.Всем не хорошего, а замечательного кода!