Массивы переменной длины

В предыдущей лекции была затронута одна из реализаций массива переменной длины — реализация с помощью списка LinkedList<Type>. В этот раз мы рассмотрим альтернативную версию: ArrayList<Type>.

Для использования ArrayList<Type> в Java нужно импортировать класс ArrayList:

Import Java.util.ArrayList;

ArrayList<Type> — это класс, содержащий где-то в своих недрах массив из ссылок на элементы типа Type и поле, содержащее размер самого ArrayList<Type>. Операции для работы с ArrayList<Type> аналогичны операциям для работы с LinkedList<Type>. Отметим, что класс ArrayList<Type> не позволяет программисту доступаться непосредственно к массиву. Более того, программист может манипулировать лишь теми элементами массива, которые созданы им самим.

Пример.

ArrayList<Integer> list = new ArrayList<Integer>();

Этой строкой мы создали объект класса ArrayList<Integer>. В нём создался массив из десяти ссылок на Integer (10 — это длина массива внутри ArrayList<Type> по умолчанию). Однако ни одно из полей этого массива нам недоступно, и метод "list.isEmpty();" вернёт true. В нашем list пока нет ни одного элемента. На картинке это будет выглядеть примерно так:

(массив из десяти ссылок со значением NULL и одно поле, содержащее длину list).

После применения "list.add(5);" получим следующую картинку:

В случае, если мы проделаем добавление элемента десять раз подряд и захотим сделать это одиннадцатый раз, то у нас возникнет проблема. Проблема состоит в том, что наш массив в list закончился и нам больше некуда записывать данные. Поэтому нам необходимо расширить массив. Это происходит автоматически. Для этого создаётся новый массив большей длины, и в него копируются значения из прежнего массива. Это довольно дорогостоящая операция, она выполняется примерно O(N) итераций. В классе ArrayList<Type> длина нового массива превосходит длину прежнего массива в полтора раза. Итого, если проделать 11 раз подряд операцию "list.add(5);", то получится примерно следующая картинка:

Заметим также, что выполнение операции "list.remove(index);" не уменьшит реальную длину массива в list.

Таблица времени работы в среднем операций для ArrayList<Type>.

Рассмотрим теперь асимптотическое время выполнения операций над ArrayList<Type>:

Заметим, что для add(value) и add(index, value) время выполнения составляет O(1) и O(size - index) соответственно, хотя в худшем случае эти операции работают O(size). Покажем, почему же среднее время работы для операции add(value) получается O(1).

Оценка времени работы операции add(value).

Давайте, для начала, рассмотрим вариант, в котором увеличение массива происходит всего на один элемент. В таком случае при добавлении нового элемента нам каждый раз пришлось бы создавать новый массив и копировать в него все элементы старого. Таким образом время работы add(value) всегда (в том числе и в среднем) равнялось бы O(N). Даже в случае расширения \ нашего массива каждый раз на k элементов время работы в среднем всё равно составило бы O(N). Действительно. Каждый k-ый раз операция выполняется за O(N), а в остальных случаях за O(1). Если взять среднее арифметическое, то получим C * N, то есть O(N).

Рассмотрим теперь реальный случай, в котором удлиннение массива каждый раз происходит в полтора раза. Пускай мы заполняем объект типа LinkedList<Type> size элементами. Предположим также, что для добавления последнего элемента нашему массиву пришлось расширяться. Подсчитаем, сколько времени нам понадобилось на заполнение этого объекта. Последнее добавление элемента заняло порядка size операций. Несколько предыдущих вызовов заняли порядка одной операции каждый. Предпоследнее "долгое" добавление производилось примерно (2/3)*size операций (так как массив расширяется каждый раз в полтора раза). И так далее. Получим, что операций всего было произведено примерно:

size + (2/3) * size + (2/3)² * size + (2/3)³ * size + ... = size / (1 - 2/3) = 3 * size

То есть мы получили, что выполнение операции add(value) size раз происходит C * size времени, а это и означает, что время выполнения add(value) равно O(1).

Дополнительные методы в ArrayList<Type>.

В дополнение к уже изученным методам для ArrayList<Type> есть ещё пара методов, о которых полезно знать: trimToSize() и ensureCapacity(capacity). Первый метод сокращает массив до длины, которая хранится параметром в ArrayList<Type>. То есть при его использовании просто-напросто удаляются незначащие элементы массива. При использовании "list.ensureCapacity(capacity);" длина массива станет по крайней мере capacity. Эти методы стоит иметь в виду, но они не так часто бывают нужны. Обе эти операции позволяют экономить память, а ensureCapacity(capacity) при правильном использовании уменьшает время работы программы.

Также длину массива можно задавать при конструировании объекта класса ArrayList<Type>. Для задания массиву изначальной длины capacity достаточно написать:

ArrayList<Type> list = new ArrayList<Type>(capacity);

Заключение.

Обзор класса ArrayList<Type> мы закончим небольшим сравнением его с классом LinkedList<Type>.

В ArrayList<Type> произвольный доступ к элементам списка происходит за константное время, когда в LinkedList<Type> — за линейное. В этом плане лучше пользоваться объектом класса ArrayList<Type>. Но, предупреждаем ещё раз, нужно избегать применения таких операций как get(i). Если у Вас есть возможность обойти вызов get(i), то лучше этой возможностью воспользоваться.

В силу того, что Java — объектно-ориентированный язык программирования, значительных перевесов в борьбе за экономию памяти ни тот ни другой класс не получают. Хотя формально в этом плане выигрывает ArrayList<Type> (если учесть, что у него есть такие возможности, как trimToSize), этот выигрыш является незначительным.

LinkedList<Type> хорош тем, что мы всегда точно знаем, сколько времени займёт добавление нового элемента. В ArrayList<Type> мы можем говорить лишь о среднем значении времени добавления нового элемента.

Основной же недостаток ArrayList<Type> заключается в том, что возможность вызова спецфункций для этого класса входит в противоречие с идеалогией объектно-ориентированного программирования.