Структуры данных в картинках. 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
Вы уже умеете создавать массивы в Java? Тогда самое время узнать что такое Arraylist. Ну что ж, поехали!
Допустим, Вы работаете программистом на компанию, которая осуществляет доставку товаров по всему миру. И Вам необходимо сохранить список городов, в которые осуществляется доставка.
Вы это можете сделать 2 способами:
1. С помощью обычного массива
2. С помощью Arraylist
1. С ПОМОЩЬЮ ОБЫЧНОГО МАССИВА
Создаем обычный массив с именем deliveryCities. В фигурных скобках прописываем значения элементов массива, то есть названия городов. Например:
В результате, будет создан массив deliveryCities на 4 элемента. И если мы заходим получить 3-й элемент массива – мы напишем deliveryCities[2], поскольку 3-й элемент имеет индекс 2. Таким образом мы можем создать массив из элементов любого типа, после чего можем работать с этими элементами.
Но что, если мы хотим добавить еще один город для доставки, например, London?
И вот Вам мой ответ: «Так сделать не получится! Потому что в Java нет возможности изменять длину массивов. А это значит, что если Вы изначально создали массив на 4 элемента, значит уже этот массив будет всегда на 4 элемента.»
Решение будет выглядеть так:
2. С ПОМОЩЬЮ ARRAYLIST
Так что же такое Arraylist? Говоря простым и понятным языком, ArrayList – это список, который очень похож на массив за исключением того, что он имеет произвольную длину и целый ряд методов, которые позволяют добавлять, удалять, заменять элементы списка в любое время и в любом месте.
А это значит, что Вы можете, например, сначала создать Arraylist на 4 элемента, а потом взять и добавить еще 7 элементов, а потом удалить 2 элемента, а потом снова добавить 15 элементов и т.д. Вы поняли идею, Arraylist, как резиновый, его можно увеличивать или уменьшать безо всяких проблем.
Работать с ArrayList очень и очень просто
Во-первых, как и в случае с массивами, нужно создать список. Создать список можно несколькими способами. Наиболее распространенным способом является следующая структура:
Списочный массив ArrayList
Знакомство с ArrayList
Работать с ArrayList просто: создайте нужный объект, вставьте объект методом add(), обращайтесь к нему методом get(), используйте индексирование так же, как для массивов, но без квадратных скобок. ArrayList также содержит метод size(), который возвращает текущее количество элементов в массиве (напомню, что в обычном массиве используется свойство length).
Переменные принято называть во множественном числе.
Рассмотрим на примерах.
Запускаем программу и видим, что в текстовом поле отобразилось имя кота Васьки. Что же произошло? Мы объявили экземпляр класса ArrayList под именем catNames и через метод add() добавили имя. Списочный массив стал содержать одну строку и мы можем в этом убедиться, когда выводим в текстовом поле первый элемент массива через индекс, равный 0.
Продолжим опыт. Перенесём объявление класса на уровень нашего основного класса и добавим через кнопку ещё два имени.
Что теперь произошло? В методе onCreate() как прежде добавляется одно имя, которое выводится в текстовом поле. При нажатии на кнопку мы добавляем ещё два имени, а в текстовой метке выводим имя второго кота через метод catnamesList.get(1).
Хорошо, мы знаем, что добавили трёх котов и поэтому можем обращаться через индекс 0, 1 или 2. А если котов стало слишком много, и мы запутались в их количестве? Тогда нужно вызвать метод size(), который вернёт общее число элементов массива. В этом случае, чтобы получить имя последнего кота в массиве, нужно получить размер массива и отнять единицу.
Вроде бы всё замечательно. Но студия выводит предупреждение у кода метода add(). Почему?
Мы знаем, что у кота есть четыре лапы и хвост. Создадим отдельную переменную для количества лап и попробуем запихнуть их в массив имён. Выглядит как бред, но Java не ругается на наши действия. Вы можете через метод size() убедиться, что размер массива увеличился. Но при попытке вывести последний элемент получим ошибку.
Чтобы вы не совершали подобных ошибок, был придуман следующий подход. Когда вы создаёте новый объект для массива, то в угловых скобках сразу указываете, какой тип собираетесь использовать.
Как только вы исправите пример, то строчка mCatNames.add(paws); будет сразу подчёркнута красной линией. Java поняла, что мы хотим использовать в массиве только строки, а не числа. Поэтому, вы уже не совершите глупых ошибок. Удалите неправильную строку, остальное можно оставить без изменений.
Теперь студия не ругается, и мы можем свернуться калачиком и поспать.
Такая форма записи с угловыми скобками говорит о том, что мы использовали generic-класс (дженерик или обобщение) с типизированными параметрами.
В Java 7 появилась укороченная запись, называемая ромбовидной. Вы можете опустить параметр с правой стороны выражения.
Если у вас есть собственный класс, то он используется таким же образом, только с использованием ключевого слова new.
Метод add()
Метод add() самый популярный и не требует особых объяснений. Только не забывайте, что существует перегруженная версия метода, позволяющая вставлять элемент в нужную позицию.
Следует быть осторожным, чтобы ненароком не вставить в несуществующую позицию. По возможности, избегайте операций вставки в середину коллекции. Ведь системе приходится заново пересчитывать индексы элементов.
Методы ensureCapacity() и trimToSize()
Если заранее известно, сколько элементов следует хранить, то перед заполнением массива вызовите метод ensureCapacity():
Первоначальную ёмкость можно задать и в конструкторе в качестве параметра.
Если вы уверены, что списочный массив будет иметь постоянный размер, то можете использовать метод trimToSize(). Это может способствовать рациональному использованию памяти.
Метод indexOf()
Предположим, мы внимательно следим за Рыжиком. Когда он был последним, то его легко было вычислить. Зная размер массива, мы вычитали единицу и получали к нему доступ. Но потом мы стали добавлять в массив других котов и уже не сможем понять, где теперь наш Рыжик. Но выход всегда есть. Существует метод indexOf(), который ищет подходящий элемент и выводит его индекс.
Не забываем, что отсчёт массива идёт с 0, если индекс равен 2, значит он является третим в массиве.
Просмотр всех элементов через цикл
Чтобы вывести всех усатых-полосатых на чистую воду, используем цикл for:
Или укороченная запись:
Метод contains()
Чтобы узнать, есть в массиве какой-либо элемент, можно воспользоваться методом contains(), который вернёт true или false:
Понятно, что в нашем массиве никаких бобиков и барбосов быть не может, поэтому появится надпись false.
Для удаления элемента из массива используется метод remove(). Можно удалять по индексу или по объекту:
Элементы, следующие после удалённого элемента, сдвигаются влево, а размер списочного массива уменьшается на единицу.
Метод removeAll() удаляет сразу все элементы. Но лучше использовать метод clear().
Чтобы заменить элемент в массиве, нужно использовать метод set() с указанием индекса и новым значением. Предположим, вы обнаружили, что у вас не кот Мурзик, а кошка Мурка. Нет проблем.
Для очистки массива используется метод clear():
Метод работает гораздо быстрее похожего метода removeAll().
Также можно сконвертировать из нашего списка в обычный массив и выполнить другие операции. Читайте документацию.
Конвертация в массив может понадобится для ускорения некоторых операций, передачи массива в качестве параметра методам, которые требуют именно массив и другие причины.
В Java 8 появился ещё один вариант через Stream.
Сколько раз совпадают элементы
В списочном массиве значения вполне могут совпадать. Например, среди котов попадаются однофамильцы и мы их спокойно можем запихнуть в ArrayList. Но сколько раз повторяются одинаковые элементы?
Интерфейс List
java.util.List является интерфейсом и его можно использовать вместо ArrayList следующим образом:
Или укороченный вариант для Java 7:
Как видите, мы заменили ArrayList на List, но при этом в объявлении оставили new ArrayList(). Всё остальное остаётся без изменений. Кстати, этот способ является рекомендуемым. Но иногда он может не подойти.
Контейнеры List гарантируют определённый порядок следования элементов. Интерфейс List дополняет Collection несколькими методами, обеспечивающими вставку и удаление элементов в середине списка.
Существует две основные разновидности List:
В отличие от массива контейнер List позволяет добавлять и удалять элементы после создания, а также изменяет свои размеры.
Метод contains() проверяет, присутствует ли объект в списке. Чтобы удалить объект, передайте ссылку на него методу remove(). Кроме того, если у вас имеется ссылка на объект, вы можете определить индекс объекта в List при помощи метода indexOf().
Сам List реализует более общий интерфейс коллекции Collection и можно было даже написать:
Но у Collection нет методов set() и get(), поэтому работать с таким интерфейсом не очень удобно.
Для создания массива можно не только добавлять по одному объекту через метод add(), но и сразу массив через метод Arrays.asList().
Оставим пока в покое котов и создадим массив из объектов Integer.
Но у данного способа есть недостаток. Если вы определили массив таким образом, то уже не можете вставлять или удалять другой элемент (методы add() и delete()), хотя при этом можете изменять существующий элемент.
В Android 11 (R) обещают добавить несколько перегруженных версий метода of(), которые являются частью Java 8.
Заключение
С ArrayList работать проще и удобнее, чем с массивами. Можно без проблем добавлять новые элементы, в том числе и в середину листа. А в случае использования обычного массива вам придётся заново выделять память и перезаписывать элементы, так как размер массива поменять нельзя, после того как была выделена память.
Работа с массивом быстрее и можно использовать массив, если точно знаете заранее размер массива и вам не придётся его динамически менять, делать вставки и т.д.
Структура данных в картинках
Теперь, когда вы получили представление об ArrayList, заглянем за кулисы и посмотрим, как данные хранятся в этом объекте. Источник
Только что созданный объект list содержит свойства elementData и size.
Хранилище значений elementData есть ни что иное как массив определенного типа (указанного в generic), в нашем случае String[]. Если вызывается конструктор без параметров, то по умолчанию будет создан массив из 10-ти элементов типа Object (с приведением к типу, разумеется).
Добавим новый элемент:
Внутри метода add(value) происходят следующие вещи:
1) проверяется, достаточно ли места в массиве для вставки нового элемента;
2) добавляется элемент в конец (согласно значению size) массива.
Если места в массиве не достаточно, новая ёмкость рассчитывается по формуле (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():
Уменьшаем размер массива и забываем про последний элемент:
При удалении по значению, в цикле просматриваются все элементы списка, до тех пор пока не будет найдено соответствие. Удален будет лишь первый найденный элемент.
При удалении элементов текущая величина capacity не уменьшается, что может привести к своеобразным утечкам памяти. Поэтому не стоит пренебрегать методом trimToSize().
Объединяем два ArrayList
С помощью библиотеки Apache Commons Collections можно объединить два ArrayList.
Сортировка
Сортировать элементы можно при помощи метода Collections.sort().
Интерфейс ListIterator
На практике он мне не встречался. Позволяет проходить по всем элементам вперёд или назад. Для этого он проверяет, есть ли следующий/предыдущий элемент после текущего.
Выводим все элементы от начала до конца, а потом в обратном направлении.
Объяснение Java ArrayList на примерах
ArrayList в Java – это структура данных, которую можно растянуть, чтобы вместить в себя дополнительные элементы и уменьшить ее до меньшего размера при удалении элементов. Это очень важная структура данных, полезная для обработки динамического поведения элементов.
Где ArrayList Java может пригодиться:
Посмотрите на следующее изображение человека, растягивающего эластичную резинку.
Фактическая длина резиновой ленты намного меньше, но при растяжении она может простираться намного больше, чем ее фактическая длина, и может использоваться для удержания / связывания с ней гораздо более крупных объектов.
Теперь рассмотрим следующую картину: простая веревка не может растягиваться и будет иметь фиксированную длину.
Он может расти по мере того, как и когда необходимо разместить элементы, которые необходимо хранить, а когда элементы удаляются, он может уменьшаться до меньшего размера.
Проблема с массивом, который используем в том, что он не может быть расширен или уменьшен, поэтому мы будем использовать ArrayList.
Массивы похожи на веревку, показанную на картинке выше; они будут иметь фиксированную длину, не могут быть расширены или уменьшены по сравнению с исходной длиной.
Таким образом, наша растягиваемая резиновая полоса очень похожа на Array List, тогда как веревка может рассматриваться как массив.
Технически говоря, Java Array List похож на динамический массив или массив переменной длины.
Следующий фрагмент кода, поможет разобраться.
Методы ArrayList
Пример Java ArrayList
Примечание. Для простоты, элементы, показанные в приведенном выше коде, являются односимвольными элементами. Мы также можем добавлять строки, целые числа и т. д.
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
7)Object get(int index): Возвращает объект типа Object имеющий указанный индекс
8)int size(): Показывает количество элементов в ArrayList, то есть показывает размер ArrayList
9)boolean contains(Object o): Проверяет, присутствует ли объект типа Object в ArrayList, если его там нет возвращает true, иначе возвращает false.
10)clear(): Удаляет все элементы созданные в ArrayList
