Как создать динамический массив в java

Класс ArrayList . Динамический массив. Общие сведения. Создание массива

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

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

Класс ArrayList реализует интерфейс List и имеет следующие объявления:

class ArrayList

здесь E – тип сохраняемых объектов.

Список распространенных методов класса следующий:

• add – добавить элемент в массив;
• addAll – добавить набор в массив;
• clear – очистить массив;
• clone – получить копию массива;
• contains – определить, содержится ли в списке определенный элемент;
• containsAll – определить, есть ли все элементы некоторой коллекции в заданной коллекции;
• ensureCapacity – зарезервировать фрагмент памяти для массива;
• get – получить элемент массива;
• indexOf – определить позицию первого вхождения элемента в массиве;
• isEmpty – определить, пустой ли массив;
• iterator – получить итератор на массив;
• lastIndexOf – определить позицию последнего вхождения элемента в массиве;
• listIterator – получить итератор в виде списка;
• remove – удалить элемент в заданной позиции;
• removeAll – удалить группу элементов из коллекции;
• removeIf – изменить коллекцию на основе предиката;
• replaceAll – произвести вычисление над каждым элементом массива;
• retainAll – сформировать новый массив, содержащий элементы заданной коллекции;
• set – установить новое значение в массиве;
• size – получить размер массива;
• sort – рассортировать элементы массива в заданном порядке;
• subList – получить фрагмент массива на основе заданного массива;
• toArray – конвертировать массив в массив типа Object[] ;
• trimToSize – скорректировать текущий размер массива.

2. Конструкторы класса. Создание массива. Пример

В классе ArrayList определены следующие конструкторы:

ArrayList() ArrayList(Collectionextends E>) ArrayList(int size)

• E – тип элементов коллекции;
• size – текущий размер массива.

Первый конструктор создает пустой динамический массив. Второй конструктор создает динамический массив на основе другого массива.

Третий конструктор создает пустой массив с зарезервированным объемом размера size . Если при наращивании количество элементов в таком массиве превысит size , то зарезервированный объем (максимальная емкость) будет увеличен на некоторую величину.

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

import java.util.*; public class TrainCollections <  public static void main(String[] args) < // 1. Конструктор ArrayList() // Создать пустой массив целых чисел ArrayList AL = new ArrayList(); // Прибавить к массиву числа от 0 до 9 for (int i=0; iout.println(AL); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] // 2. Создать массив строк на основе другого массива строк, // конструктор ArrayList(Collection) // 2.1. Создать исходный массив ArrayList AS1 = new ArrayList(); AS1.add("Winter"); AS1.add("Spring"); AS1.add("Autumn"); AS1.add("Summer"); System.out.println(AS1); // [Winter, Spring, Autumn, Summer] // 2.2. Использовать конструктор ArrayList(Collection) ArrayList AS2 = new ArrayList(AS1); System.out.println(AS2); // [Winter, Spring, Autumn, Summer] // 3. Конструктор ArrayList(int) // 3.1. Создать пустой массив з зарезервированным размером 8 элементов ArrayList AC = new ArrayList(8); // 3.2. Вывести размер массива System.out.println(AC.size()); // 0 - это есть текущий размер массива > >

Результат выполнения программы

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [Winter, Spring, Autumn, Summer] [Winter, Spring, Autumn, Summer] 0

Связанные темы

• Методы изменяющие данные в массиве. Методы add() , addAll() , clear() , remove() , removeIf() , replaceAll() , set() , sort()
• Методы, определяющие информацию об элементах массива. Методы get() , contains() , containsAll() , indexOf() , lastIndexOf() , iterator() , listIterator()
• Методы определяющие общие характеристики массива. Методы ensureCapacity() , isEmpty() , size() , trimToSize()
• Методы преобразующие массив в целом. Методы clone() , sublist() , toArray() , retainAll()

Как создать динамический массив в java

В Java динамический массив создается с использованием класса ArrayList . Этот класс находится в пакете java.util и обеспечивает динамическое управление массивом. Чтобы создать динамический массив, нужно выполнить следующие шаги:

• Импортируйте класс ArrayList из пакета java.util:

import java.util.ArrayList; 

• Создайте объект класса ArrayList , указав тип элементов, которые будут храниться в массиве. Например, для создания массива целых чисел:

ArrayListInteger> nums = new ArrayList<>(); 

• Добавьте элементы в массив с помощью метода add():

nums.add(1); nums.add(2); nums.add(3); 

• Обращайтесь к элементам массива по индексу, как в обычном массиве:

int firstElement = nums.get(0); // 1 int secondElement = nums.get(1); // 2 int thirdElement = nums.get(2); // 3 

• Динамический массив автоматически расширяется при добавлении новых элементов. Например, чтобы добавить еще один элемент в конец массива:

nums.add(4); 

• Размер динамического массива можно получить с помощью метода size() :

int nums = myArray.size(); // 4 

Динамический массив

В [math]i[/math] -ую ячейку массива записывается элемент [math]x[/math] . Время выполнения — [math]O(1)[/math] .

add(x)

Добавление в массив элемента [math]x[/math] . Время выполнения — [math]O(1)[/math] ; в худшем случае, при котором необходимо перенести все элементы из текущего массива во вдвое больший массив — [math]O(n)[/math] ( [math]n[/math] — размер массива).

del()

Удаляет последний элемент массива. В случае, если количество элементов в массиве в [math]C[/math] раз меньше его длины, то происходит сжатие в [math]B[/math] раз. ( [math]C,B[/math] — константы, зависящие от реализации). Время выполнения операции в худшем случае — [math]O(n)[/math] .

size()

Возвращает количество элементов массива. Время выполнения — [math]O(1)[/math] .

Амортизационная стоимость каждой операции

Пусть наш массив расширяется в [math]2[/math] раза, и уменьшается в [math]2[/math] раза, когда длина массива в [math]4[/math] раза больше количества элементов в массиве. В этом случае амортизационная стоимость каждой операции будет [math]O(1)[/math] .

Метод предоплаты

Стоимость операции add(x)

Иллюстрация

Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции add(x), при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили [math]i[/math] -ый элемент, мы будем класть по одной монетке к элементам с номерами [math]i[/math] и [math]i-\frac[/math] ). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции add(x) — [math]3[/math] , и среднее время её работы — [math]O(1)[/math] .

Стоимость операции del()

При каждой операции будем использовать две монетки. Одну из них потратим на само удаление элемента, другую на элемент, стоящий на позиции [math]i \bmod \dfrac[/math] . Тогда даже в самом худшем случае (только что расширились, а потом [math]\dfrac[/math] удалили) у каждого элемента из первых [math]\dfrac[/math] будет по монете и на удаление надо будет потратить только [math]1[/math] монету.

Метод потенциалов

За потенциал примем число: [math]\Phi(c, s) = \begin 2s-c, & \text s\geqslant\fracc \\ \fracc-s, & \text s\lt \fracc \end[/math] , где [math]c[/math] — размер массива, [math]s[/math] — число элементов массива.

Стоимость операции add(x)

• [math]\frac= 1[/math] , массив расширяется: [math] a_i = t_i + \Phi(2c, s + 1) — \Phi(c, s) = (s + 1) + (2(s+1)-2c)-(2s-c) = 3 [/math]

• [math]1\gt \frac\geqslant\frac[/math] , массив не расширяется: [math]a_i=t_i+\Phi(c,s+1)-\Phi(c,s)=1+(2(s+1)-c)-(2s-c)=3[/math]

• [math]\frac\lt \frac, \frac\geqslant\frac[/math] , массив не расширяется:

[math]a_i = t_i + \Phi(c, s+1)-\Phi(c, s)= 1 +(2(s+1)-c)-(\fracc — s)= 3+3s-\fracc= 3 + \frac3c-\fracc \lt 3+\fracc-\fracc=3[/math]

• [math]\frac\lt \frac, \frac\lt \frac[/math] , массив не расширяется: [math]a_i = t_i + \Phi(c, s + 1) — \Phi(c, s) = 1 + (\fracc — (s + 1)) — (\fracc — s) = 0[/math]

В итоге, средняя стоимость операции — [math]3[/math] , а среднее время работы — [math]O(1)[/math] .

Стоимость операции del()

• [math]\frac=\frac[/math] , массив сужается: [math]a_i = t_i + \Phi(\frac, s — 1) — \Phi(c, s) = s + (\frac\cdot\fracc-(s-1)) — (\fracc-s) = 1-\fracc+s=1[/math]
• [math]\frac\lt \frac\lt \frac[/math] , массив не сужается: [math]a_i = t_i + \Phi(c, s — 1) — \Phi(c, s) = 1 + (\fracc-(s-1))-(\fracc-s)= 2[/math]
• [math]\frac\geqslant\frac, \frac\lt \frac\Rightarrow s=\fracc[/math] , массив не сужается: [math]a_i = t_i + \Phi(c, s — 1) — \Phi(c, s) =1 +(\fracc-(s-1))-(2s-c)=2+\fracc-3s = 2[/math]
• [math]\frac\gt \frac[/math] , массив не сужается: [math]a_i = t_i + \Phi(c, s — 1) — \Phi(c, s) = 1 + (2(s-1)-c)-(2s-c)=0[/math]

Средняя стоимость операции — [math]2[/math] , а среднее время работы — [math]O(1)[/math] .

Динамические массивы в современных языках программирования

Динамические массивы широко применяются во многих языках программирования. Рассмотрим, как эта структура данных реализуется в С++ и Java.

С++ — vector

В С++ динамический массив используется в структуре vector, она описана в STL(). Стратегия расширения проста: при попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера в [math]2[/math] раза при компиляции GNU C++ и в [math]1.5[/math] раза при компиляции Microsoft Visual C++. При удалении элементов уменьшение размера массива никогда не происходит. При инициализации vector по-умолчанию начальный размер равен [math]0[/math] .

Java — ArrayList

В Java структура ArrayList основана на динамическом массиве. При превышении максимального на данный момент размера происходит увеличение в [math]1.5[/math] раза. Причем начальный размер равен [math]10[/math] . Как и в vector, в ArrayList не предусмотрено изменение размера при удалении элементов. Для принудительного изменения размера следует использовать метод trimToSize().

Источники информации

• Wikipedia — Dynamic array
• Wikipedia — Динамический массив

• Дискретная математика и алгоритмы
• Амортизационный анализ

Java-массивы. Динамические массивы в Java

Массив — набор определённого числа однотипных элементов. Использование массива позволяет нам не создавать большое количество переменных, а создать всего лишь одну переменную, имеющую вид массива. В отличие от стандартных переменных массивы содержат больше, чем одно значение. В программировании это очень важно, ведь при разработке софта может потребоваться огромное количество данных.

Лучшая ассоциация для массива — стена с почтовыми ячейками. Каждая ячейка помечена квартирными номерами (индексы массива), внутри лежат газеты и письма (элементы массива), а получить содержимое можно, открыв ящик ключом (обратиться к содержимому по позиции элемента в массиве через индекс). При этом содержимое массива может включать в себя как простые данные (это одномерный массив), так и несколько вложенных массивов (это многомерный массив).

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

Как происходит объявление массива в Java

Как и любую переменную в Java, массив надо объявить. Для этого есть два способа. Первый больше отвечает стилю Java, второй является наследием языка C.

Вне зависимости от способа, dataType — это тип переменных в массиве. Посмотрите внимательно на примеры — в них объявлены 2 массива. Один предназначен для целых чисел типа int, другой — для объектов типа Object.

Можно сказать, что во время объявления массива ему присваивается как имя (ArrayName), так и тип переменных.

Создание массива

Чтобы создать массив в Java, нужно зарезервировать место в памяти, для чего используем оператор new:

 
new typeOfArray [length];
Здесь у нас typeOfArray — тип массива, length — длина массива или число ячеек, выраженное в целых числах (int). Но мы лишь выделили память под массив, не связав его ни с какой переменной, ранее объявленной. Как правило, сначала массив объявляют, потом создают:
 
int[] myArray; // объявление массива myArray = new int[10]; // создание массива, выделение памяти на 10 элементов типа int
Итак, объявлен массив из целых чисел с именем myArray. После объявления мы сообщили, что массив состоит из 10 ячеек. Но можно использовать и более сокращённый синтаксис:
 
int[] myArray = new int[10]; // объявление и выделение памяти за один раз
Что же, мы создали массив с помощью new. После этого в его ячейках будут записаны значения по умолчанию. Например, для численных типов — это нули (0), для boolean — false, а если говорить о ссылочных типах, то null. Это значит, что после выполнения кода
 
int[] myArray = new int[10];
у нас на выходе будет массив из 10 целых чисел, причём в каждой ячейке будет записан 0.
Длина массива length
Длина массива — число элементов, под которое этот массив рассчитан. Длину массива изменить после создания нельзя.
Ещё нюанс: элементы массива в Java нумеруются с нуля. Таким образом, массив на 10 элементов состоит из чисел в диапазоне 0-9.

Если нужно получить доступ к длине нашего массива, используют переменную length:
 
int[] myArray = new int[10]; // создали массив, присвоили имя myArray System.out.println(myArray.length); // вывели в консоль длину массива
 
Вывод программы: 10
Инициализация массива
Инициализация — это заполнение массива конкретными данными, а не данными по умолчанию.
Нижеследующий код позволит создать массив, включающий в себя 4 сезона года. Также мы выполним заполнение массива строками-названиями сезонов:
 
String[] seasons = new String[4]; /* выполнили объявление и создание массива из 4 строк, где по умолчанию записано null, ведь строка — ссылочный тип данных*/ seasons[0] = "Winter"; /* в первую ячейку записали строку Winter*/ seasons[1] = "Spring"; /* во вторую ячейку (номер 1) записали строку Spring и т. д.*/ seasons[2] = "Summer"; seasons[3] = "Autumn";
Так мы записали названия всех сезонов. Но в принципе можно всё сделать проще, совместив инициализацию и объявление:
 
String[] seasons = new String[] ;
Или даже так, опустив оператор new:
 
String[] seasons = ;
Динамический массив в Java
Минус массива — статичность, то есть необходимость задавать размер заранее. Для этого и придумали динамический массив, который может менять размер в процессе выполнения программы. Например, статические массивы работают по следующей схеме:

А динамические массивы в Java функционируют несколько иначе:

Так как для копирования массива используется специальная нативная функция, проблем с «переездом» не возникает.
В общем, как вы уже догадались, динамические массивы применяются во время обработки наборов однородных данных, размер которых на момент написания программы нам неизвестен.


Похожие публикации:

Как в иллюстраторе уменьшить объект без изменения контура
Как выйти из процедуры 1с
Как вычисляется hashcode java
Как сфотографировать звезды на айфон 11