Описание тега arraylist
ArrayList часто обозначает абстрактный тип данных (ADT), встречающийся в некоторых распространенных языках программирования / платформах, который представляет "растущий" (динамически изменяемый) массив.
В Java:
java.util.ArrayList- это класс в стандартной библиотеке Java SE, реализующий интерфейс List. ВArrayList класс представляет содержимое списка с помощью Object массив, который он перераспределяет по мере необходимости, чтобы приспособиться к росту списка.
Сложность общих List операции над массивами следующие:
List.add(Object)-O(1)с амортизацией (см. ниже).List.get(int)-O(1)List.remove(int)-O(N)в общем случаеList.contains(Object)-O(N)в общем случае
Амортизированная стоимость addоснован на следующем аргументе. Предположим, вы начали с пустого списка массивов и добавилиNэлементы по одному. Каждый раз, когда вы добавляете элемент, метод add проверяет, заполнен ли резервный массив списка. Если это так, то он выделяет новый резервный массив, в два раза превышающий размер текущего, а затем копирует существующие элементы из старого массива в новый. Если вы подсчитаете количество копий элементов, которые происходят в этом процессе, вы обнаружите, что при увеличении размера массива доN == initial * 2^P, в общей сложности initial *2^P - 1 копии будут иметь место, а это меньше, чем Nкопии. Затем добавьтеN назначения новых элементов и проверки границ, а общая стоимость явно пропорциональна N, при накоплении более N звонки в add. Затем делает среднюю стоимость одного вызова постоянной; т.е.O(1).
В.NET:
System.Collections.ArrayList в библиотеке классов.NET Framework, как и ее аналог в Java, также представляет собой массив динамического размера. Он стал в основном устаревшим с введением универсального System.Collections.Generic.List<T> type в.NET 2, преимущество которого (в большинстве случаев) состоит в том, что он строго типизирован и позволяет избежать ненужной упаковки типов значений.