Простой тип данных коллекции, встречающийся в некоторых языках / платформах (например, в Java или .NET). Список массивов реализует список с использованием массива, используя преимущества обоих DS.

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>введите .NET 2, который имеет преимущество (в большинстве случаев) в том, что он строго типизирован и позволяет избежать ненужной упаковки типов значений.

Связанные теги

arrayslist