Алгоритмы и структуры данных для начинающих: динамический массив

Иногда от коллекции требуется неограниченная вместимость и простота использования списка, но при этом константное время доступа к произвольному элементу, как в массиве. В этом случае используется список на основе массива — динамический массив (Array List).


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

Класс ArrayList

ArrayList — это коллекция, которая реализует интерфейс IList<T> и использует массив для хранения элементов. Как и связный список, ArrayList может хранить произвольное число элементов (ограниченное только объемом доступной памяти), но в остальном ведет себя как массив.

Интерфейс IList<T> предоставляет все методы ICollection<T> и дополнительно — методы для чтения, вставки и удаления элементов по индексу. Код ниже сгенерирован с помощью команды «Implement Interface» в Visual Studio 2010 и, кроме автоматически сгенерированных заглушек для методов, содержит также:

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

Вставка элементов

Вставка элементов в динамический массив отличается от вставки в связный список. На то есть две причины. Первая: динамический массив поддерживает вставку в середину массива, тогда как в связный список можно вставлять только в конец или начало. Вторая: вставка элемента в связный список всегда выполняется за константное время. Вставка в динамический массив может занимать как O(1), так и O(n) времени.

Расширение массива

По мере добавления элементов внутренний массив может переполниться. В этом случае необходимо сделать следующее:

  1. Создать массив большего размера.
  2. Скопировать элементы в новый массив.
  3. Обновить ссылку на внутренний массив списка так, чтобы она указывала на новый.

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

Увеличение вдвое (подход Mono и Rotor)

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

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

Медленный рост (подход Java)

В Java используется похожий подход, но массив растет медленнее. Размер нового массива определяется следующим образом:

При использовании этого алгоритма используется меньше памяти.

Давайте посмотрим на кривые роста массивов до 200 000 элементов при использовании этих двух стратегий:

data_structures_006

Как видно из графика, для того, чтобы перейти границу в 200 000 элементов, варианту с удвоением массива понадобилось 19 операций выделений памяти и копирования, тогда как вариант Java потребовал 30 операций.

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

Наша реализация будет использовать увеличение вдвое (подход Mono/Rotor)

Метод Insert

  • Поведение: добавляет элемент по указанному индексу. Если индекс равен количеству элементов или больше него, кидает исключение.
  • Сложность: O(n).

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

В следующем примере дается массив с пятью позициями, четыре из которых заполнены. Значение «3» вставляется на третью позицию (с индексом 2):

Массив до сдвига элементов

Массив до сдвига элементов

Массив после сдвига элементов

Массив после сдвига элементов

Массив после вставки элемента на свободную позицию

Массив после вставки элемента на свободную позицию

Метод Add

  • Поведение: добавляет элемент в конец списка.
  • Сложность: O(1), если осталось более одного свободного места; O(n), если необходимо расширение массива.

Удаление элементов

Метод RemoveAt

  • Поведение: удаляет элемент, расположенный по заданному индексу.
  • Сложность: O(n).

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

Массив до удаления элемента

Массив до удаления элемента

Массив после удаления элемента

Массив после удаления элемента

Массив после сдвига элементов

Массив после сдвига элементов

Метод Remove

  • Поведение: удаляет первый элемент, значение которого равно предоставленному. Возвращает true, если элемент был удален, или false в противном случае.
  • Сложность: O(n).

Доступ к элементам

Метод IndexOf

  • Поведение: возвращает индекс первого элемента, значение которого равно предоставленному, или -1, если такого значения нет.
  • Сложность: O(n).

Метод Item

  • Поведение: позволяет прочитать или изменить значение по индексу.
  • Сложность: O(1).

Метод Contains

  • Поведение: возвращает true, если значение есть в списке, и false в противном случае.
  • Сложность: O(n).

Перебор

Метод GetEnumerator

  • Поведение: возвращает итератор IEnumerator<T> для прохода по всем элементам списка.
  • Сложность: Получение итератора — O(1), обход списка — O(n).

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

Остальные методы IList<T>

Метод Clear

  • Поведение: удаляет все элементы из списка.
  • Сложность: O(1).

Существет два варианта реализации метода Clear. В первом случае создается новый пустой массив, во втором — только обнуляется поле Count. В нашей реализации будет создаваться новый массив нулевой длины.

Метод CopyTo

  • Поведение: копирует все элементы из внутреннего массива в указанный, начиная с указанного индекса.
  • Сложность: O(n).

Мы не используем метод CopyTo массива _items, поскольку хотим скопировать только элементы с индексами от 0 до Count, а не весь массив. При использовании Array.Copy мы можем указать количество копируемых элементов.

Метод Count

  • Поведение: возвращает текущее количество элементов в коллекции. Если список пуст, возвращает 0.
  • Сложность: O(1).

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

Метод IsReadOnly

  • Поведение: всегда возвращает false, так как наша коллекция изменяемая.
  • Сложность: O(1).

Продолжение следует

На этом мы заканчиваем разбор динамических массивов. В следующий раз мы перейдем к стекам и очередям.

Перевод статьи «The Array List»