Сегодня мы рассмотрим: Настоящие ценители музыки знают, что для качественного...
В предыдущей лекции была затронута одна из реализаций массива переменной длины —
реализация с помощью списка LinkedList
Для использования ArrayList
Import Java.util.ArrayList;
ArrayList
Пример.
ArrayListЭтой строкой мы создали объект класса ArrayList
После применения "list.add(5);" получим следующую картинку:
В случае, если мы проделаем добавление элемента десять раз подряд и захотим сделать
это одиннадцатый раз, то у нас возникнет проблема. Проблема состоит в том, что наш массив
в list закончился и нам больше некуда записывать данные. Поэтому нам необходимо расширить
массив. Это происходит автоматически. Для этого создаётся новый массив большей длины,
и в него копируются значения из прежнего массива. Это довольно дорогостоящая операция,
она выполняется примерно O(N) итераций. В классе ArrayList
Заметим также, что выполнение операции "list.remove(index);" не уменьшит реальную длину массива в list.
Таблица времени работы в среднем операций для ArrayList.
Рассмотрим теперь асимптотическое время выполнения операций над ArrayList
Заметим, что для 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
size + (2/3) * size + (2/3) 2 * size + (2/3) 3 * size + ... = size / (1 - 2/3) = 3 * size
То есть мы получили, что выполнение операции add(value) size раз происходит C * size времени, а это и означает, что время выполнения add(value) равно O(1).
Дополнительные методы в ArrayList.
В дополнение к уже изученным методам для ArrayList
Также длину массива можно задавать при конструировании объекта класса
ArrayList
ArrayList
Заключение.
Обзор класса ArrayList
В ArrayList
В силу того, что Java — объектно-ориентированный язык программирования,
значительных перевесов в борьбе за экономию памяти ни тот ни другой класс не получают.
Хотя формально в этом плане выигрывает ArrayList
LinkedList
Основной же недостаток ArrayList
Структуры данных в картинках. ArrayList
- Java
Приветствую вас, хабралюди!
Взбрело мне в голову написать несколько статей, о том как реализованы некоторые структуры данных в Java. Надеюсь, статьи будут полезны визуалам (картинки наше всё), начинающим java-визуалам а также тем кто уже умеет писать new ArrayList(), но слабо представляет что же происходит внутри.
Сегодня поговорим о ArrayList-ах
ArrayList - реализует интерфейс List. Как известно, в Java массивы имеют фиксированную длину, и после того как массив создан, он не может расти или уменьшаться. ArrayList может менять свой размер во время исполнения программы, при этом не обязательно указывать размерность при создании объекта. Элементы ArrayList могут быть абсолютно любых типов в том числе и null.
Создание объекта
ArrayListТолько что созданный объект list, содержит свойства elementData и size .
Хранилище значений elementData есть ни что иное как массив определенного типа (указанного в generic), в нашем случае String . Если вызывается конструктор без параметров, то по умолчанию будет создан массив из 10-ти элементов типа Object (с приведением к типу, разумеется).
Внутри метода add(value) происходят следующие вещи:
EnsureCapacity(size + 1);
2) добавляется элемент в конец (согласно значению size
) массива.
ElementData = element;
Весь метод ensureCapacity(minCapacity)
рассматривать не будем, остановимся только на паре интересных мест. Если места в массиве не достаточно, новая емкость рассчитывается по формуле (oldCapacity * 3) / 2 + 1
. Второй момент это копирование элементов. Оно осуществляется с помощью native
метода System.arraycopy()
, который написан не на Java.
// newCapacity - новое значение емкости elementData = (E)new Object; // oldData - временное хранилище текущего массива с данными System.arraycopy(oldData, 0, elementData, 0, size);
Ниже продемонстрирован цикл, поочередно добавляющий 15 элементов:
list.add("1");
...
List.add("10");
При добавлении 11-го элемента, проверка показывает что места в массиве нет. Соответственно создается новый массив и вызывается System.arraycopy()
.
Добавление в «середину» списка
list.add(5, "100");Добавление элемента на позицию с определенным индексом происходит в три этапа:
1) проверяется, достаточно ли места в массиве для вставки нового элемента;
EnsureCapacity(size+1);
2) подготавливается место для нового элемента с помощью System.arraycopy()
;
System.arraycopy(elementData, index, elementData, index + 1, size - index);
3) перезаписывается значение у элемента с указанным индексом.
Как можно догадаться, в случаях, когда происходит вставка элемента по индексу и при этом в вашем массиве нет свободных мест, то вызов System.arraycopy() случится дважды: первый в ensureCapacity() , второй в самом методе add(index, value) , что явно скажется на скорости всей операции добавления.
В случаях, когда в исходный список необходимо добавить другую коллекцию, да еще и в «середину», стоит использовать метод addAll(index, Collection) . И хотя, данный метод скорее всего вызовет System.arraycopy() три раза, в итоге это будет гораздо быстрее поэлементного добавления.
Удаление элементов
Удалять элементы можно двумя способами:- по индексу remove(index)
- по значению remove(value)
С удалением элемента по индексу всё достаточно просто
List.remove(5);
Сначала определяется какое количество элементов надо скопировать
Int numMoved = size - index - 1;
затем копируем элементы используя System.arraycopy()
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
уменьшаем размер массива и забываем про последний элемент
ElementData[--size] = null; // Let gc do its work
При удалении по значению, в цикле просматриваются все элементы списка, до тех пор пока не будет найдено соответствие. Удален будет лишь первый найденный элемент.
Дополнение 1: Как верно заметил