Массивы переменной длины
В Java 5.0 существует две классические реализации массива переменной длины:
- LinkedList
- ArrayList
ArrayList
Для того, чтобы можно было использовать ArrayList, в начале файла должна быть строчка:
import java.util.ArrayList;
Для того, чтобы создать объект ArrayList, содержащий элементы типа Integer можно использовать конструктор:
ArrayList<Integer> list = new ArrayList<Integer>();
После создания ArrayList состоит из массива некоторой длины и числа, в котором записано количество элементов в массиве.
Операции ArrayList
| Операции ArrayList | Время работы в лучшем случае | Время работы в худшем случае |
| new ArrayList<Integer>() | O(1) | O(1) |
| add(element) | O(1) | O(size) |
| size() | O(1) | O(1) |
| isEmpty() | O(1) | O(1) |
| get(index) | O(1) | O(1) |
| set(index,element) | O(1) | O(1) |
| remove(index) | O(size-index) | O(size-index) |
| add(index,element) | O(size-index) | O(size) |
Рассмотрим операцию add(element) для ArrayList.
В лучшем случае в массиве еще есть место и метод add просто записывает элемент на первое свободное место. В таком случае метод работает за константное время (О(1)). В худшем случае свободного места нет и метод add создает новый массив большей длины, копирует в него содержимое старого и записывает добавляемый элемент, после чего уничтожает старый массив. Тогда метод работает за линейное время (О(size)). Теперь обсудим время работы этой операции в среднем. Оно зависит от того, на сколько элементов мы расширяем массив, когда не остается места.
Вариант №1. Увеличиваем массив на 1 элемент каждый раз, когда не хватает места. При таком подходе "худший случай" происходит при каждом добавлении. Добавление в среднем работает за О(size) действий. Единственное преимущество этого подхода состоит в том, что мы не занимаем лишнюю память.
Вариант №2. Увеличиваем массив на 10 элементов каждый раз, когда не хватает места. Тогда "худший случай" происходит раз в 10 операций, то есть в 10 раз реже, чем в предыдущем варианте. Но, тем не менее, время работы в среднем все равно будет О(size).
Вариант №3. Увеличиваем массив в 2 раза каждый раз, когда не хватает места. Посчитаем время работы в среднем. Пусть для определенности при последнем добавлении нам пришлось увеличивать массив. Это потребовало size операций. Предыдущее увеличение массива произошло при размере size/2, до этого size/4 и т.д.
Всего на size добавлений нам потребовалось ~size операций. Операция добавления работает в среднем за константное время (О(1)). В java 5.0 ArrayList реализован похожим способом, только массив каждый раз увеличивается не в два, а в полтора раза. Аналогичными рассуждениями можно доказать, что в такой реализации операция добавления также работает за константное время.
При удалении элементов из массива, уменьшается длина массива, но не память, отведенная под массив. В этом состоит некоторая проблема, поскольку если сначала добавить миллион элементов, а затем удалить их, большое количество памяти останется занятым объектом ArrayList. Эту проблему решает метод trimToSize(), который удаляет лишнее место. Например, этот метод можно применить, когда известно, что в массив больше ничего добавляться не будет.
Сравнение LinkedList и ArrayList
В LinkedList каждый объект хранит ссылку на следующий за ним. На каждую ссылку расходуется дополнительная память. Но если использовать LinkedList для хранения больших объектов, то ссылки занимают намного меньше места, чем сами объекты и потери памяти незначительны. В ArrayList возможна ситуация, когда мы используем массив намного большей длины, чем нам реально нужно. Но если использовать метод trimToSize(), то никакой дополнительной памяти расходоваться не будет.
В LinkedList чтобы получить доступ к какому-то элементу, нам придется пройти по списку. В ArrayList этого делать не нужно и поэтому в ArrayList быстрее работают методы get(index) и set(index).
В LinkedList добавление работает за фиксированное время (нет худшего случая). В ArrayList мы не можем знать, сколько времени будет работать операция добавления, поскольку может произойти "худший случай" и придется копировать массив. Эта проблема решается при помощи метода ensureCapacity(int capacity). После вызова этого метода объём массива гарантированно будет хотя бы capacity. Кроме того, есть возможность сразу создать массив заданной длины. Для этого можно использовать такой конструктор:
ArrayList<Integer> list = new ArrayList<Integer>(int capacity);
Главный недостаток ArrayList состоит в том, что надо вызывать специальные методы. Не очень хорошо, что для того, чтобы пользоваться классом, мы вынуждены знать, как он устроен.