Структуры данных в картинках. ArrayList
Взбрело мне в голову написать несколько статей, о том как реализованы некоторые структуры данных в Java. Надеюсь, статьи будут полезны визуалам (картинки наше всё), начинающим java-визуалам а также тем кто уже умеет писать new ArrayList(), но слабо представляет что же происходит внутри.
Сегодня поговорим о ArrayList-ах
ArrayList — реализует интерфейс List. Как известно, в Java массивы имеют фиксированную длину, и после того как массив создан, он не может расти или уменьшаться. ArrayList может менять свой размер во время исполнения программы, при этом не обязательно указывать размерность при создании объекта. Элементы ArrayList могут быть абсолютно любых типов в том числе и null.
Создание объекта
Только что созданный объект list, содержит свойства elementData и size.
Хранилище значений elementData есть ни что иное как массив определенного типа (указанного в generic), в нашем случае String[]. Если вызывается конструктор без параметров, то по умолчанию будет создан массив из 10-ти элементов типа Object (с приведением к типу, разумеется).
Вы можете использовать конструктор ArrayList(capacity) и указать свою начальную емкость списка.
Добавление элементов
Внутри метода add(value) происходят следующие вещи:
1) проверяется, достаточно ли места в массиве для вставки нового элемента;
2) добавляется элемент в конец (согласно значению size) массива.
Весь метод ensureCapacity(minCapacity) рассматривать не будем, остановимся только на паре интересных мест. Если места в массиве не достаточно, новая емкость рассчитывается по формуле (oldCapacity * 3) / 2 + 1. Второй момент это копирование элементов. Оно осуществляется с помощью native метода System.arraycopy(), который написан не на Java.
Ниже продемонстрирован цикл, поочередно добавляющий 15 элементов:
При добавлении 11-го элемента, проверка показывает что места в массиве нет. Соответственно создается новый массив и вызывается System.arraycopy().
После этого добавление элементов продолжается
Добавление в «середину» списка
Добавление элемента на позицию с определенным индексом происходит в три этапа:
1) проверяется, достаточно ли места в массиве для вставки нового элемента;
2) подготавливается место для нового элемента с помощью System.arraycopy();
3) перезаписывается значение у элемента с указанным индексом.
Как можно догадаться, в случаях, когда происходит вставка элемента по индексу и при этом в вашем массиве нет свободных мест, то вызов System.arraycopy() случится дважды: первый в ensureCapacity(), второй в самом методе add(index, value), что явно скажется на скорости всей операции добавления.
В случаях, когда в исходный список необходимо добавить другую коллекцию, да еще и в «середину», стоит использовать метод addAll(index, Collection). И хотя, данный метод скорее всего вызовет System.arraycopy() три раза, в итоге это будет гораздо быстрее поэлементного добавления.
Удаление элементов
Удалять элементы можно двумя способами:
— по индексу remove(index)
— по значению remove(value)
С удалением элемента по индексу всё достаточно просто
Сначала определяется какое количество элементов надо скопировать
затем копируем элементы используя System.arraycopy()
уменьшаем размер массива и забываем про последний элемент
При удалении по значению, в цикле просматриваются все элементы списка, до тех пор пока не будет найдено соответствие. Удален будет лишь первый найденный элемент.
Дополнение 1: Как верно заметил MikeMirzayanov, при удалении элементов текущая величина capacity не уменьшается, что может привести к своеобразным утечкам памяти. Поэтому не стоит пренебрегать методом trimToSize().
Итоги
— Быстрый доступ к элементам по индексу за время O(1);
— Доступ к элементам по значению за линейное время O(n);
— Медленный, когда вставляются и удаляются элементы из «середины» списка;
— Позволяет хранить любые значения в том числе и null;
— Не синхронизирован.
Ссылки
Пишите в комментариях пожелания/замечания и есть ли смысл продолжать.
Как заполнить arraylist java при создании
Completing the CAPTCHA proves you are a human and gives you temporary access to the web property.
What can I do to prevent this in the future?
If you are on a personal connection, like at home, you can run an anti-virus scan on your device to make sure it is not infected with malware.
If you are at an office or shared network, you can ask the network administrator to run a scan across the network looking for misconfigured or infected devices.
Another way to prevent getting this page in the future is to use Privacy Pass. You may need to download version 2.0 now from the Chrome Web Store.
Cloudflare Ray ID: 71aa6d044d9e7785 • Your IP : 82.102.23.104 • Performance & security by Cloudflare
ArrayList в Java с примерами — Collection Framework
Класс ArrayList реализует интерфейс List, который основан на структуре данных массива. Он широко используется из-за гибкости и функциональности. Многие разработчики выбирают ArrayList вместо обычного массива, потому что это является хорошей альтернативой традиционному массиву. ArrayList — это массив с изменяемым размером, который реализует интерфейс List.
Почему ArrayList лучше чем массив?
Существенным недостатком массива является то, что он имеет фиксированный размер, поэтому если он заполнен, то вы не можете добавить к нему больше элементов, аналогичное происходит и при удалении, если вы удаляете некоторое количество элементов из массива, то потребление памяти остается таким же.
В свою очередь ArrayList имеет возможность изменять свой размер при добавлении или удалении элементов. Отдельным преимуществом класса ArrayList является возможность переопределения методов, что в свою очередь может упростить решение поставленной задачи. На рисунках ниже представлены принципиальные схемы удаления и добавления элементов из ArrayList.
Методы класса ArrayList
1)add(Object o): Этот метод добавляет объект типа Object в ArrayList
2)add(int index, Object o): Добавляет объекты типа Object в ArrayList по заданному индексу
Произойдет добавление строки “John” во 2-ой индекс(3-ая позиция, поскольку ArrayList начинается с нулевого индекса)
3)remove(Object o): Удаление объекта типа Object из ArrayList
4)remove(int index): Удаление элемента ArrayList по индексу
5)set(int index, Object o): Используется для изменения элемента в ArrayList по индексу на другой объект типа Object
6)int indexOf(Object o): Дает индекс объекта с типом Object, если элемент не найден в ArrayList, то возвращает -1.
7)Object get(int index): Возвращает объект типа Object имеющий указанный индекс
8)int size(): Показывает количество элементов в ArrayList, то есть показывает размер ArrayList
9)boolean contains(Object o): Проверяет, присутствует ли объект типа Object в ArrayList, если его там нет возвращает true, иначе возвращает false.