При создании объекта типа arraylist в конструктор в качестве аргумента нельзя подать

Обновлено: 27.03.2024

Поле, отвечающее за объем динамического массива по умолчанию:

При создании нового объекта new ArrayList<>() (конструктор без параметров) внутри создается массив на 10 элементов.

Поле, в котором хранятся все элементы коллекции:

Помечено ключевым словом transient – поле не записывается в поток байт при применении стандартного алгоритма сериализации. Стоит отметить, что поле не отмечено ключевым словом private , а сделано это для того, чтобы облегчить доступ к этому полю из вложенных классов (например, SubList).

Значение увеличивается/уменьшается при выполнении таких операций, как вставка и удаление.

  1. public ArrayList() – создает пустой списочный массив объемом в 10 элементов;
  2. public ArrayList(Collection < ? extends E >c) – создает списочный массив, инициализируемый элементами из переданной коллекции (если хотим создать новый ArrayList на базе какой-то коллекции);
  3. public ArrayList(int initialCapacity) – создает списочный массив, имеющий начальную емкость. Если переданный параметр initialCapacity больше 0, то создается массив указанного размера (внутреннему полю elementData присваивается ссылка на новый массив типа Object размером initialCapacity). Если параметр равен 0, то в таком случае создается пустой массив. Если же заданный параметр меньше 0, то генерируется исключение IllegalArgumentException.

Подробный разбор класса ArrayList [Часть 1] - 7

  • Создается новый массив размером, в 1.5 раза больше исходного, плюс один элемент.
  • Все элементы из старого массива копируются в новый массив
  • Новый массив сохраняется во внутренней переменной объекта ArrayList, а старый массив объявляется мусором.

Подробный разбор класса ArrayList [Часть 1] - 8

Также добавлять элементы в нашу коллекцию можно с помощью методов addAll . Первый вариант позволяет добавить все элементы из указанной в параметре метода коллекции (например, другого листа) в исходную коллекцию (вставка в конец), для которой был сделан вызов метода. Переданная коллекция (она же может быть и множеством) преобразуется в массив с помощью метода toArray() . Естественно, операция добавления осуществляется также с помощью копирования. Во втором осуществляется добавление всех элементов collection в список, начиная с индекса index . При этом все элементы сдвинутся вправо на количество элементов в списке collection . Удаление элементов В начале рассмотрим классические варианты удаления элементов из ArrayList. Осуществляет удаление по индексу и смещает все последующие (после элемента под указанным индексом) элементы влево, тем самым закрывая "дырки". Также возвращает удаленный элемент (E), который предварительно перед удалением записывается в дополнительную переменную, значение которой мы и получаем в результате работы вызова метода. Чтобы понять, что такое E, необходимо будет познакомиться с так называемыми обобщенными типами (generics). Обозначение E указывает на то, что метод возвращает тот тип данных, который был указан при создании объекта ArrayList (вспомните: List list , соответственно в данном случае вместо E "подставится" String ). Для общего понимания настоятельно рекомендую ознакомиться с обобщенными типами. Проверяется корректность введенного индекса и далее внутри метода происходит не совсем удаление элемента, а вызов приватного метода fastRemove(Object[] es, int i) , в котором уже происходит удаление. Методу на вход мы передаем наш массив и указанный индекс. Копируются элементы, используя System.arraycopy() , уменьшается размер массива, а далее присваиваем последнему элементу null. Стоит отметить, что новый массив не создается: System.arraycopy(es, i + 1, es, i, size - 1 - i); В наш же исходный массив (es) копируется та часть, которая находится правее позиции под указанным индексом (i+1), и располагается она, начиная с той самой позиции (i), где находился элемент, подлежащий удалению. Таким образом, мы осуществили сдвиг влево и затерли наш элемент.

Подробный разбор класса ArrayList [Часть 1] - 9

Подробный разбор класса ArrayList [Часть 1] - 10

Рассмотрим второй вариант метода: Метод удаляет из списка переданный элемент o , а если точнее, то объект по указанной ссылке. Если элемент присутствует в списке, он удаляется, а все элементы смещаются влево. Если элемент существует в списке и успешно удален, метод возвращает true, в обратном случае — false. Аналогично варианту с удалением по индексу, вызывается метода fastRemove() , где происходят точно такие же действия. Разница в том, что в методе remove(Object o) предварительно дополнительно осуществляется поиск нужного объекта через метод equals() класса Object. При удалении по значению, в цикле просматриваются все элементы списка, до тех пор пока не будет найдено соответствие. Удален будет лишь первый найденный элемент. Подытожим: при удалении элементов из динамического массива, дырок как в обычном массиве не остается (удаленная ячейка не будет пустовать). Все последующие элементы (которые были правее от индекса) сдвигаются на одну позицию влево. Есть еще несколько дополнительных методов, с помощью которых можно в той или иной степени удалять элементы из списка. Рассмотрим их вкратце. Очищаем нашу коллекцию: В простом цикле for перебираются все элементы массива, каждому из которых присваиваются null. Удалить те элементы из нашей коллекции, которые содержатся в другой переданной коллекции можно так: Если необходимо удалить несколько элементов, наверное не стоит делать это в цикле по условию: удобнее и безопаснее воспользоваться методом removeAll() . Он принимает коллекцию элементов, которая будет удалена из списка. Коллекция должна содержать элементы того же типа, которые хранит целевой список. В обратном случае будет выброшен ClassCastException . Метод вернет true, если список был изменен в результате вызова метода.

Подробный разбор класса ArrayList [Часть 1] - 11

Подробный разбор класса ArrayList [Часть 1] - 12

Предположим, есть коллекция: И вторая: Тогда после listSecond.retainAll(listFirst) в listSecond останется: Так как удалился "Green", которого нет в listFirst . Но после listSecond.removeAll(listFirst) в listSecond останется: Не принадлежащие переданной коллекции – значит, что если есть элементы, которых нет в переданной коллекции, то нужно удалить их из первой (к которой применяется метод). Принадлежащие переданной коллекции - соответственно, если есть элемент и в первой и во второй (переданной) коллекции, то дубль из первой уничтожается. Удаляет из списка все элементы, которые находятся между начальным указанным индексом (включительно) и конечным указанным индексом (не включительно). Стоит отметить, что метод нельзя вызвать напрямую на объекте класса ArrayList. Чтобы его использовать необходимо унаследоваться от AbstractList/ArrayList . Метод также используется другим методом (subList, о котором пойдет речь далее). Удаляет элементы из коллекции по заданному предикату. Cобственно предикат — эта некая функция/алгоритм/условие, на основании которой будут удалены один или несколько элементов, соответствующих заданному условию. Predicate — функциональный интерфейс (содержит всего один метод, поэтому может использоваться в виде лямбды), работает по принципу "принял один параметр — вернул boolean". По сути метод переопределяет реализацию из интерфейса Collection и реализует следующую "стратегию": он перебирает элементы и помечает те, которые соответствуют нашему Predicate ; после он пробегается второй раз для удаления (и сдвига) элементов, которые были отмечены в первой итерации. Реализуем интерфейс Predicate , который будет выдавать true, если два объекта равны: В другом классе создадим ArrayList из String и объект нашего класса, который реализует Predicate : Запишем в переменную varc1 значение "White": Добавим в список несколько строк: Выполним на списке метод removeIf , которому передадим наш объект с условием: В результате из списка будут удалены все строки со значением "White", так как наш "предикат" сравнивает их на равенство. Итоговый список: [Black, Red, Yellow].

Замена элементов Осуществляет замену элемента в указанной позиции index на переданный element . Индекс также должен быть больше нуля и меньше индекса последнего элемента, иначе будет выброшено исключение IndexOutOfBoundsException . Никаких копирований внутреннего массива не происходит. Просто вместо элемента по указанному индексу вставляется новый элемент, т.е. перезаписываем значение.

Подробный разбор класса ArrayList [Часть 1] - 14

  1. ускорить выполнение некоторых операций;
  2. передавать массив в качестве параметра методу, который не перегружается, чтобы принимать непосредственно коллекцию;
  3. интеграция нового кода, основанного на коллекциях, с унаследованным кодом, который не распознает коллекции.

Подробный разбор класса ArrayList [Часть 1] - 16

Подробный разбор класса ArrayList [Часть 1] - 17

Проверить коллекцию на наличие в ней элементов: Метод возвращает true, если список пустой (смотрит, равно ли поле size 0 ), иначе – false. Если в списке содержатся только элементы null, метод вернет false. Иными словами, null элементы также учитываются этим методом. Узнать количество элементов в списке: Возвращает количество элементов в списке (значения поля size). Количество элементов может отличаться от объема списка (capacity). Получить итератор для списка: Возвращает итератор для списка для последующего использования в цикле или при любой другой обработке. Итератор реализует fail-fast поведение. Если он бежит по коллекции и замечает какие-то модификации в ней (которые были получены не с помощью методов итератора), он сразу выбрасывает исключение ConcurrentModificationException . У итератора есть так называемый modification count . Когда итератор пробегает по коллекции после каждого next/hasNext/remove , он проверяет этот счетчик. Если он не совпал с тем, что ожидал увидеть итератор, он бросает исключение. Подробно рассматривать итераторы здесь я не буду. Возвращает list-итератор для списка для последующего использования в цикле или при любой другой обработке. Интерфейс ListIterator расширяет интерфейс Iterator для двустороннего обхода списка и видоизменения его элементов. В перегруженном варианте можно передать индекс, с которого начнется «обход». Индекс в данном случае обозначает первый элемент, с которого начнет свою работу метод next() , а при вызове метода previous() обход начнется с элемента под индексом «переданный индекс – 1». В Java 8 внедрен новый тип итератора late binding (позднее связывание) и fail-fast, который называется итератором-разделителем. Итераторы-разделители позволяют перебирать последовательность элементов, но применяются они иным способом. Наиболее важной особенностью интерфейса Spliterator является его способность поддерживать параллельную итерацию отдельных частей последовательности элементов, а следовательно и параллельное программирование.

I am working on a project, and I was taught to instantiate variables in constructors. I'm having some trouble doing this with an ArrayList thought. Can you suggest some best practices, do I need to define the ArrayList with the instance variables or can I do it in the constructor. Thanks for your suggestions! I have an example of what I'm talking about below:

Don't confuse declaration and initialization. Also careful that you don't shadow the variable. (Those are all keywords.)

Sotiros I just did that for brevities sake. You're totally right and in practice I don't! Rohit I was taught that in a default constructor anything that needs to have a value to be accessed later should be instantiated in the default constructor instead of adding default values before that, this prevents you from having issues later on with random values floating around.

Rohit is referring to a concept called shadowing. If you have a field declared with the name list and then declare a new variable called list within the constructor, when referring to list within the constructor, you'll be referring to the local variable rather than the field.

6 Answers 6

You can now choose to sort by Trending, which boosts votes that have happened recently, helping to surface more up-to-date answers.

Trending is based off of the highest score sort and falls back to it if no posts are trending.

If you want to just declare it in the constructor you can have the code:

Otherwise you can declare it as a field, and then initialize it in the constructor.

And then in the constructor:

Making it a field would be useful, as you would then be able to create accessor/mutator methods in order to retrieve and use the List from different classes, without having to declare it public (which is rarely a good thing).

If you want to declare it in the constructor, then you (most likely) want to declare the outer field, so you want:

Currently you are shadowing the List list class variable, meaning that you are creating a new instance of list , rather than that you are initializing the list instance variable.

I personally prefer initializing it at declaration time though, so what you previously had. I prefer this to make the code more concise and you most likely won't end up forgetting to initialize it if you teach yourself that habbit.

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

  • Open with Desktop
  • View raw
  • Copy raw contents Copy raw contents

Copy raw contents

Copy raw contents

Чем отличается ArrayList от LinkedList?

Преимущества ArrayList: в возможности доступа к произвольному элементу по индексу за постоянное время (так как это массив), минимум накладных расходов при хранении такого списка, вставка в конец списка в среднем производится так же за постоянное время. В среднем потому, что массив имеет определенный начальный размер n (в коде это параметр capacity), по умолчанию n = 10, при записи n+1 элемента, будет создан новый массив размером (n * 3) / 2 + 1, в него будут помещены все элементы из старого массива + новый, добавляемый элемент. В итоге получаем, что при добавлении элемента при необходимости расширения массива, время добавления будет значительно больше, нежели при записи элемента в готовую пустую ячейку. Тем не менее, в среднем время вставки элемента в конец списка является постоянным. Удаление последнего элемента происходит за константное время. Недостатки ArrayList проявляются при вставке/удалении элемента в середине списка — это взывает перезапись всех элементов размещенных «правее» в списке на одну позицию влево, кроме того, при удалении элементов размер массива не уменьшается, до явного вызова метода trimToSize().

LinkedList наоборот, за постоянное время может выполнять вставку/удаление элементов в списке (именно вставку и удаление, поиск позиции вставки и удаления сюда не входит). Доступ к произвольному элементу осуществляется за линейное время (но доступ к первому и последнему элементу списка всегда осуществляется за константное время — ссылки постоянно хранятся на первый и последний, так что добавление элемента в конец списка вовсе не значит, что придется перебирать весь список в поисках последнего элемента). В целом же, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти и по скорости выполнения операций. LinkedList предпочтительно применять, когда происходит активная работа (вставка/удаление) с серединой списка или в случаях, когда необходимо гарантированное время добавления элемента в список.

Всегда ли добавление в ArrayList имеет сложность O(1)?

Чаще всего это действительно так, но не всегда. Внутри ArrayList находится массив. И когда пустые элементы в этом массиве заканчиваются, реализация ArrayList расширяет его - происходит создание нового массива, большего размера, куда происходит копирование старого, и уже в новый добавляется элемент. Таким образом, иногда вставка в ArrayList может занимать линейное время O(n)

Collections.emptyList() или новый экземпляр

Тот же вопрос применяется к emptyMap() и emptySet().

Оба метода возвращают пустой список, но Collections.emptyList() непреложный (immutable) список. Это означает, что вы не можете добавлять новые элементы к "пустому" списку. На фоне, каждый вызов метода Collections.emptyList() фактически не создает новый экземпляр пустого списка. Вместо этого, оно будет использовать снова уже существующий пустой экземпляр. Если Вы знакомы с синглтоном как с паттерном проектирования, Вы должны понять что имеется в виду. Это должно Вам дать большую производительность, если вызывается часто.

Какое начальное количество корзин в HashMap?

  1. Но при создании HashMap в конструкторе можно задать другое значение (поле capacity)

Гарантирует ли HashMap указанную сложность выборки элемента?

Если вы возьмете хеш-функцию, которая постоянно будет возвращать одно и то же значение, то HashMap превратится в связный список, с отвратной производительностью. Затем даже, если вы будете использовать хеш-функцию с равномерным распределением, в предельном случае гарантироваться будет только временная сложность lg N. Так что, ответ на вопрос — нет, не гарантируется.

Какое максимальное число значений hashCode()

Здесь все довольно просто, достаточно вспомнить сигнатуру метода: int hashCode(). То есть число значений равно диапазону типа int — 2^32

Назовите основные реализации List, Set, Map

  • HashMap
  • TreeMap
  • SortedMap
  • Hashtable

Отличия между Iterator и ListIterator?

  • Мы можем использовать Iterator для обхода коллекций Set и List, тогда как ListIterator можно использовать только со списками.
  • Итератор может перемещаться только в прямом направлении, тогда как ListIterator может использоваться для перемещения в обоих направлениях.
  • ListIterator наследуется от интерфейса Iterator и поставляется с дополнительными функциями, такими как добавление элемента, замена элемента, получение позиции индекса для предыдущего и следующего элементов.

Интерфейсы Comparable и Comparator?

Что есть в java.util.concurrent*

  • Concurrent Collections — набор коллекций, более эффективно работающие в многопоточной среде нежели стандартные универсальные коллекции из java.util пакета. Вместо базового враппера Collections.synchronizedList с блокированием доступа ко всей коллекции используются блокировки по сегментам данных или же оптимизируется работа для параллельного чтения данных по wait-free алгоритмам.
  • Queues — неблокирующие и блокирующие очереди с поддержкой многопоточности. Неблокирующие очереди заточены на скорость и работу без блокирования потоков. Блокирующие очереди используются, когда нужно «притормозить» потоки «Producer» или «Consumer», если не выполнены какие-либо условия, например, очередь пуста или перепонена, или же нет свободного «Consumer»'a.
  • Synchronizers — вспомогательные утилиты для синхронизации потоков. Представляют собой мощное оружие в «параллельных» вычислениях.
  • Executors — содержит в себе отличные фрейморки для создания пулов потоков, планирования работы асинхронных задач с получением результатов.
  • Locks — представляет собой альтернативные и более гибкие механизмы синхронизации потоков по сравнению с базовыми synchronized, wait, notify, notifyAll.
  • Atomics — классы с поддержкой атомарных операций над примитивами и ссылками.

Название говорит само за себя. Все операции по изменению коллекции (add, set, remove) приводят к созданию новой копии внутреннего массива. Тем самым гарантируется, что при проходе итератором по коллекции не кинется ConcurrentModificationException. Следует помнить, что при копировании массива копируются только референсы (ссылки) на объекты (shallow copy), т.ч. доступ к полям элементов не thread-safe. CopyOnWrite коллекции удобно использовать, когда write операции довольно редки, например при реализации механизма подписки listeners и прохода по ним.

В каком случае может быть потерян элемент в HashMap?

После добавления элемента в HashMap у объекта, который выступает в качестве ключа, изменяют одно поле, которое участвует в вычислении хеш-кода. В результате при попытке найти данный элемент по исходному ключу, будет происходить обращение к правильной корзине, а вот equals (ведь equals и hashCode должны работать с одним и тем же набором полей) уже не найдет указанный ключ в списке элементов. Тем не менее, даже если equals реализован таким образом, что изменение данного поля объекта не влияет на результат, то после увеличения размера корзин и пересчета хеш-кодов элементов, указанный элемент, с измененным значением поля, с большой долей вероятности попадет совсем в другую корзину и тогда он уже совсем потеряется.

Как создать синхронизированную коллекцию из данной коллекции?

Можно использовать Collections.synchronizedCollection(Collection c) чтобы получить синхронизированную (потокобезопасную) коллекцию, подкрепленную указанной коллекцией.

Чем отличается HashMap от Hashtable?

Класс HashMap по функционалу очень похож на Hashtable. Главное отличие в том, что методы класса Hashtable синхронизированы, а HashMap - нет. Кроме этого класс HashMap в отличии от Hashtable разрешает использование null в качестве ключей и значений.

Наличие синхронизации в Hashtable уменьшает производительность кода, использующего данный класс. Поэтому классы JCF (Java Collections Framework, появившийся в Java 2), в том числе и HashMap, несинхронизированы. Если синхронизация все же нужна, можно использовать методы класса Collections:

  • Collections.synchronizedMap(map)
  • Collections.synchronizedList(list)
  • Collections.synchronizedSet(set) Данные методы возвращают синхронизированный декоратор переданной коллекции. При этом все равно в случае итерирования по коллекции требуется ручная синхронизация.
  • Карта имеет схожий с hashmap интерфейс взаимодействия
  • Потокобезопасность
  • Операции чтения не требуют блокировок и выполняются параллельно
  • Операции записи зачастую также могут выполняться параллельно без блокировок
  • Элементы карты имеют значение value, объявленное как volatile

Как используя HashMap получить бесконечный цикл

HashMap имеет концепцию повторного хеширования, когда достигает своего верхнего предела. Это процесс создания новой области памяти и копирования туда существующих элементов. Допустим Поток A положил пару key-value в Map и повторное хеширование началось, в то же время поток Б начал манипулировать с областью памяти используя операцию put(положить). Во время повторного хеширования существует возможность для создания циклической зависимости где элемент находящийся в ссылочном листе [в любой области памяти] может указывать на любой предыдущий узел в ту же область памяти. Это приведет к бесконечному циклу так как код повторного хеширования содержит в себе while(TRUE) который будет работать бесконечно.

Почему Map не наследуется от Collection

Всё очень просто, эти структуры не совместимы. Для создания и для операция всех реализаций Map используется пара ключ-значение

Почему нельзя использовать byte[] в качестве ключа в HashMap?

Хеш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива (метод вычисления хеш-кода массива не переопределен и вычисляется по стандартному Object.hashCode() на основании адреса массива). Так же у массивов не переопределен equals и выполняет сравнение указателей. Это приводит к тому, что обратиться к сохраненному с ключом-массивом элементу не получится при использовании другого массива такого же размера и с такими же элементами, доступ можно осуществить лишь в одном случае — при использовании той же самой ссылки на массив, что использовалась для сохранения элемента.

Какое дерево лежит в реализации TreeSet?

Почему нет конкретных реализаций интерфейса Iterator?

Интерфейс итератора объявляет методы для итерации коллекции, но за ее реализацию отвечают классы реализации коллекции. Каждый класс коллекции, который возвращает итератор для обхода, имеет свой собственный вложенный класс реализации итератора. Это позволяет классам коллекции выбирать, является ли итератор отказоустойчивым или отказоустойчивым. Например, итератор ArrayList является отказоустойчивым, тогда как итератор CopyOnWriteArrayList является отказоустойчивым.

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

  • Open with Desktop
  • View raw
  • Copy raw contents Copy raw contents

Copy raw contents

Copy raw contents

Класс java.util.ArrayList является одной из самых популярных и часто используемых реализаций интерфейса java.util.List .

Данная реализация основана на массиве, но, в отличии от массивов в Java , java.util.ArrayList может динамически менять размер, а также хранить null значения.

Прежде всего обратим внимание на поля класса и выделим наиболее значимые:

Количество элементов в списке хранится в переменной size .

Важно понимать, что size - это не размер массива, это именно количество элементов.

Если представить массив как шкаф с ящиками, то размер массива - это количество ящиков, а количество элементов массива - это количество занятых ящиков.

Как было сказано выше, в основе реализации лежит массив. За это отвечает поле elementData .

Массив имеет фиксированный размер, а значит при создании списка его надо как-то инициализировать.

Если не указать размер массива при создании объекта java.util.ArrayList будет создан массив размером 10 . Это значение по-умолчанию, которое хранится в константе DEFAULT_CAPACITY .

Можно указать размер при создании объекта списка воспользовавшись конструктором и передав туда значение желаемого размера:

Более того, если вы знаете, что в список будет добавлено большое количество элементов, лучше сразу задать необходимый initialCapacity . Лучше с самого начала зарезервировать массив нужного размера, чем несколько раз терять время на его, хоть и динамическое, но расширение.

Вопрос:

Элементы java.util.ArrayList хранятся в elementData , как уже было отмечено, однако тип массива java.lang.Object .

А где же параметризация?

Ответ:

Приведение к параметризованному типу происходит при обращении, т.е при попытке достать элемент.

Это связано с тем, как устроена параметризация( Generic -и) в Java .

Об этом можно прочитать здесь.

Теперь разберем то, как происходит добавление элементов в список и за счет чего достигается динамичность размера.

В java.util.ArrayList существует несколько методов добавить элемент, для начала разберем наиболее часто используемый.

Добавление в конец

За добавление элемента в конец у java.util.ArrayList отвечает метод:

Перед тем, как вставить добавляемый элемент в список происходит проверка: достаточно ли места для вставки?

За это отвечает метод ensureCapacityInternal .

Т.е сначала проверяется хватает ли места для добавления нового элемента и если хватает, то происходит добавление элемента в конец, при этом возвращается true , так как список изменяется.

Что происходит в случае, если массив, хранящий элементы, переполнен, т.е для добавления элемента в список нет места?

Ответ прост: список увеличивается в размере.

Расширение списка происходит следующим образом:

  • Создается новый массив, большего размера
  • Вызывается System.arrayCopy , который копирует старый массив в новый.
  • Добавляемый элемент вставляется в новый, только что созданный и заполненный список.

Для наглядности приведем пример:

У вас есть шкаф с 10 ячейками, но со временем этого количества стало не хватать, так как вы купили 11-ю вещь. Вы покупаете новый шкаф, с большим количеством ячеек, перекладываете туда свои старые вещи и 11-ю покупку. Старый же шкаф отдается GarbageCollector -у.

Теперь пришла пора разобрать алгоритм увеличения размера списка.

Алгоримт увеличения размера списка

Новый массив создается по следующему правилу:

Это означает, что размер будет увеличен в полтора раза.

Теперь рассмотрим добавлние элемент в середину или начало списка.

Добавление в середину или начало

За добавление элемента в конкретную ячейку по индексу у java.util.ArrayList отвечает метод:

Добавление происходит в несколько этапов:

  1. Идет проверка на то, что индекс, по которому происходит вставка, не выходит за границы списка:
  1. После этого идет стандартная проверка на то, достаточно ли места в массиве для вставки новго элемента, точно та же самая, как и при вставке в конец списка. При необходимости происходит расширение списка:

Подготовка происходит следующим образом: все элементы, находящиеся правее места вставки, включая само место вставки, сдвигается правее. Достигается это копированием правой части массива.

  1. Ну и наконец происходит непосредственно вставка значения по указанному индексу:

Описанный процесс изображен на рисунке:

Добавление элемента в список

Если места для вставки нет, то System.arrayCopy будет вызван дважды: первый раз при расширении, т.е создании нового массива, а второй раз уже непосредственно при вставке нового элемента.

Удаление элемента из java.util.ArrayList возможно двумя способами:

  • public E remove(int index) - по индексу
  • public boolean remove(Object o) - по значению

Удаление по индексу

За удаление по индексу у java.util.ArrayList отвечает метод:

В начале идет привычная проверка на то, не выходит ли индекс за рамки списка.

После чего идет смещение всех элементов влево:

  1. Определяется количество элементов, которые необходимо скопировать.
  1. Происходит копирование с помощью уже знакомого System.arrayCopy :
  1. Благодаря этому получается 'сдвиг' влево, а значит, последний элемент уже не нужен, поэтому его отдаем на 'съедение' GarbageCollectror -у.

Описанный процесс изображен на рисунке:

Удаление элемента из списка

Удаление по значению

За удаление по значению у java.util.ArrayList отвечает метод:

При удалении по значению происходит поиск удаляемого элемента. Идет перебор массива поэлементно, пока не будет найдет необходимый.

После чего происходит то же самое, что и при удалении по индексу.

При удалении по значению очень важно переопределенный метод equals , так как удаляемый элемент ищется с его помощью:

Так как списки могут содержать null значения, то за их удаление отвечает первый цикл.

Если в списке присутствуют дубли, то удален будет первый найденный элемент!

Еще одним важным моментом, о котором стоило бы поговорить, является то, что при удалении элементов размер массива elementData , хранящего наши элементы, не изменяется. Т.е значение capacity остается прежним.

Разберем это на примере:

Создадим список и добавим в него 1000 элементов, после чего удалим 999 из них.

Так вот, несмотря на то, что элементы из списка мы удалили, размер списка, т.е количество доступных ячеек в массиве не изменится.

Если снова обратиться к примеру со шкафом, то представьте, что вы из своего шкафа выбросили часть вещей. Размер шкафа и его вместимость при этом остались теми же, просто часть ячеек не заняты.

И если в реальной жизни в этом нет ничего страшного, то в программировании это может привести к утечкам памяти.

Для того, чтобы держать массив в 'актуальном' состоянии и 'ужать' его размер после удаления большого количества элементов существует метод trimToSize() .

Данный метод урежет размер массива до количества элементов.

В примере с удалением 999 элементов и вызове trimToSize() мы поулучим размер массива равный 1 .

Помните, что если вы заполнили список и вы не планируете, что этот список будет больше расширяться, то можно на таком списке вызвать trimToSize() и ужать неиспользованные 'ячейки'.

Но это не значит, что нужно постоянно вызывать этот метод, особенно, если вы постоянно добавляете и удаляете элементы из списка.

Все методы java.util.ArrayList не синхронизированы. Поэтому добавление из различных потоков в такой список строго не рекомендуется.

Если необходима concurrent -реализация java.util.ArrayList , то стоит воспользоваться java.util.concurrent.CopyOnWriteArrayList .

В Java также существует класс утилит java.util.Collections , предоставляющих статические методы для преобразования в concurrent структуру данных:

Но тут есть подводный камень.

Посмотрим на метод:

Все, что делает метод synchronizedList - это оборачивает реализацию java.util.List в SynchronizedList :

, где методы синхронизованы на java.lang.Object . Грубо говоря, это превращает java.util.ArrayList в java.util.Vector . А это серьезно снижает производительность.

В целом, я бы не использовал Collections.synchronizedList(. ) , разве что необходимо синхронизировать небольшую по объему структуру и производительность не важна.

Благодаря тому, что в основе реализации лежит массив, java.util.ArrayList предоставляет доступ к элементам по индексу за константное время: O(1) .

В то время как доступ к элементу по значению требует перебор списка до нахождения искомого, что выражается в линейном времени доступа: O(N) .

Реализация java.util.ArrayList из стандартной библиотеки Java предоставляет быстрый доступ к элементам по индексу и линейное время доступа к элементам по значению.

Благодаря использованию native -метода System.arrayCopy реализация java.util.ArrayList является предпочтительным выбором при необходимости использования списка.

Ключевое слово native означает, что метод реализован в платформенно-зависимом коде, чаще всего на C/C++ , и скомпонован в виде динамической библиотеки.

Эта реализация зависит от JVM .

Возможно, вас сейчас это напугало, но на самом деле достаточно просто понимать, что native означает лишь то, что вызываемый код, реализован не на Java .

Данная реализация позволяет хранить любые значения, в том числе дубликаты и null .

Не синхронизована, поэтому доступ из разных потоков не рекомендуется.

Если количество добавляемых элементов в список велико, то имеет смысл сразу задать должное capacity , что увеличит скорость работы и сэкономит ресурсы.

Данная реализация динамически меняет размер при добавлении элементов, но не уменьшает размер внутреннего массива при удалении.

Для того, чтобы контролировать размер массива при удалении элементов стоит воспользоваться методом trimToSize() .

ArrayList — реализация изменяемого массива интерфейса List, часть Collection Framework, который отвечает за список (или динамический массив), расположенный в пакете java.utils. Этот класс реализует все необязательные операции со списком и предоставляет методы управления размером массива, который используется для хранения списка. В основе ArrayList лежит идея динамического массива. А именно, возможность добавлять и удалять элементы, при этом будет увеличиваться или уменьшаться по мере необходимости.

Что хранит ArrayList?

Только ссылочные типы, любые объекты, включая сторонние классы. Строки, потоки вывода, другие коллекции. Для хранения примитивных типов данных используются классы-обертки.

Конструкторы ArrayList

ArrayList()

Пустой конструктор с начальной емкостью внутреннего массива = 10.

В угловых скобках желательно указать тип хранимых значений. В примере выше — String .

ArrayList(Collection c)

Конструктор принимает другую коллекцию, создавая новый массив с элементами переданной коллекции:

Порядок элементов в новом списке будет совпадать с исходным.

ArrayList(int initialCapacity)

В качестве параметра конструктора выступает значения начального размера внутреннего массива.

Если в массиве, который лежит в основе ArrayList, закончилось место при добавлении новых элементов, создается новый массив большего размера, и данные копируются в него. Если при написании кода заранее известно, что в массиве будет обрабатываться большое количество элементов, в целях оптимизации следует указать большее значение.

Методы ArrayList

Ниже представлены основные методы ArrayList.

add(E e)

Добавляет новый элемент в конец списка. Возвращает boolean -значение (true — успех, false — не добавлено):

add(int index, E element)

Добавляет элемент element в позицию index. При добавлении происходит сдвиг всех элементов справа от указанного индекса на 1 позицию вправо:

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

addAll(Collection collection)

Добавление всех элементов коллекции collection в список в порядке их расположения в collection.

addAll(int index, Collection collection)

Добавление всех элементов collection в список начиная с индекса index . При этом все элементы сдвинутся вправо на количество элементов в списке collection :

Методы addAll() также возвращают boolean-результат добавления элементов.

clear()

Удаление всех элементов из списка.

Возвращает объект-копию массива:

Следует обратить внимание, что метод clone() возвращает Object , так что после его вызова потребуется сделать приведение к необходимому классу.

При клонировании создается новый независимый объект. В примере показано, как очищение клонированного объекта не сказалось на составе его клона.

contains(Object o)

Проверка наличие объекта в списке, возвращает boolean -значение.

ensureCapacity(int minCapacity)

Увеличивает размер внутреннего массива, чтобы в него поместилось количество элементов, переданных в minCapacity . Если массив достаточно вместителен, никакие преобразования не производятся.

Этот метод полезен, когда возникает потребность вместить большое количество элементов в несколько итераций. Например, при создании списка емкость его внутреннего массива — 10. При загрузке данных по сети они обрабатываются асинхронно порциями и результаты помещаются в массив. Если ожидается доставка 10 000 элементов, может быть неэффективно просто добавлять эти данные каждый раз: достаточно будет в начале обработки вызвать метод ensureCapaciry(10000) и записывать туда данные по мере необходимости.

forEach(Consumer action)

Обработать в цикле ArrayList можно стандартными способами, цикл for:

В классе ArrayList есть метод для обработки каждого элемента, который называется также, forEach. В качестве аргумента передается реализация интерфейса Consumer, в котором нужно переопределить метод accept():

Метод accept принимает в качестве аргумента очередной элемент того типа, который хранит в себе ArrayList. Пример для Integer:

Метод action() будет выполнен для каждого элемента.

get(int index)

Возвращает элемент, который расположен в указанной позиции списка.

Если index < 0 или index >= максимального количества элементов списка, будет выброшено исключение IndexOutOfBoundsException .

Это основной метод получения элемента из списка, время извлечения элемента по индексу всегда будет одинаковым, независимо от размера ArrayList.

indexOf(Object o)

Метод возвращает индекс первого вхождения элемента в списке. Если элемента не существует в списке, метод вернет -1.

isEmpty()

Метод возвращает true, если список пустой, false в обратном случае.

Если в списке содержатся только элементы null , метод вернет false. Иными словами, null элементы также учитываются этим методом.

iterator()

Возвращает итератор для списка для последующего использования в цикле или при любой другой обработке.

Итератор для ArrayList — fail-fast. Это значит, что если коллекция изменится во время итерации, будет выброшено исключение ConcurrentModificationException. Подробнее об fail-fast и его противоположности fail-safe можно почитать здесь.

lastIndexOf(Object o)

Функционал метода похож на indexOf() , отличие в том, что возвращается индекс последнего элемента в списке.

Если элемент не найден, также возвращает -1.

remove(int index)

Удаление элемента в указанной позиции индекса. После удаления сдвигает все элементы влево для заполнения освободившегося пространства.

Если index= количество элементов списка, будет выброшено исключение IndexOutOfBoundsException . В результате метод возвращает элемент, который был удален.

remove(Object o)

Метод удаляет из списка переданный элемент o . Если элемент присутствует в списке, он удаляется, а все элементы смещаются влево. Если элемент существует в списке и успешно удален, метод возвращает true, в обратном случае — false.

removeAll(Collection c)

Если необходимо удалить несколько элементов, не стоит делать это в цикле по условию: гораздо удобнее и безопаснее воспользоваться методом removeAll() . Он принимает коллекцию элементов, которая будет удалена из списка.

Коллекция должна содержать элементы того же типа, которые хранит целевой список. В обратном случае будет выброшен ClassCastException . Метод вернет true, если список был изменен в результате вызова метода.

set(int index, E element)

Замена элемента в указанной позиции index на переданный element . Индекс также должен быть больше нуля и меньше индекса последнего элемента, иначе будет выброшено исключение IndexOutOfBoundsException .

size()

Лучший способ (практически единственный) для того, чтобы узнать размер массива.

sort(Comparator c)

Сортировка списка по заданному правилу. Правило сортировки представляет собой реализованный интерфейс Comparator с переопределенным методом compareTo() .

Переопределение нужно, если коллекция содержит объекты собственного класса. При работе со стандартными классами ( Integer , String и так далее) переопределение compareTo() требуется только для нестандартной сортировки.

toArray()

Превращает список в фиксированный массив. Обратите внимание, что метод возвращает массив объектов ( Object[] ). Если необходимо привести список в массив объектов определенного типа, в качестве параметра в метод можно передать массив, куда будут перемещены элементы списков.

Читайте также: