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

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

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

Класс ArrayList

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

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

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

			public class ArrayList : System.Collections.Generic.IList
{
    T[] _items;

    public ArrayList()
        : this(0)
    {
    }

    public ArrayList(int length)
    {
        if (length < 0)
        {
            throw new ArgumentException("length");
        }

        _items = new T[length];
    }

    public int IndexOf(T item)
    {
        throw new NotImplementedException();
    }

    public void Insert(int index, T item)
    {
        throw new NotImplementedException();
    }

    public void RemoveAt(int index)
    {
        throw new NotImplementedException();
    }

    public T this[int index]
    {
        get
        {
            throw new NotImplementedException();
        }
        set
        {
            throw new NotImplementedException();
        }
    }

    public void Add(T item)
    {
        throw new NotImplementedException();
    }

    public void Clear()
    {
        throw new NotImplementedException();
    }

    public bool Contains(T item)
    {
        throw new NotImplementedException();
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        throw new NotImplementedException();
    }

    public int Count
    {
        get { throw new NotImplementedException(); }
    }

    public bool IsReadOnly
    {
        get { throw new NotImplementedException(); }
    }

    public bool Remove(T item)
    {
        throw new NotImplementedException();
    }

    public System.Collections.Generic.IEnumerator GetEnumerator()
    {
        throw new NotImplementedException();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        throw new NotImplementedException();
    }
}
		

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

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

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

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

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

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

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

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

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

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

В Java используется похожий подход, но массив растет медленнее. Размер нового массива определяется следующим образом: size = (size * 3) / 2 + 1;

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

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

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

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

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

			private void GrowArray()
{
    int newLength = _items.Length == 0 ? 16 : _items.Length << 1;

    T[] newArray = new T[newLength];

    _items.CopyTo(newArray, 0);

    _items = newArray;
}
		

Метод Insert

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

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

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

			public void Insert(int index, T item)
{
    if (index >= Count)
    {
        throw new IndexOutOfRangeException();
    }

    if (_items.Length == this.Count)
    {
        this.GrowArray();
    }

    // Shift all the items following index one slot to the right.
    Array.Copy(_items, index, _items, index + 1, Count - index);

    _items[index] = item;

    Count++;
}
		

Метод Add

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

			public void Add(T item)
{
    if (_items.Length == Count)
    {
        GrowArray();
    }

    _items[Count++] = item;
}
		

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

Метод RemoveAt

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

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

			public void RemoveAt(int index)
{
    if (index >= Count)
    {
        throw new IndexOutOfRangeException();
    }

    int shiftStart = index + 1;
    if (shiftStart < Count)
    {
        // Shift all the items following index one slot to the left.
        Array.Copy(_items, shiftStart, _items, index, Count - shiftStart);
    }

    Count--;
}
		

Метод Remove

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

			public bool Remove(T item)
{
    for (int i = 0; i < Count; i++)
    {
        if (_items[i].Equals(item))
        {
            RemoveAt(i);
            return true;
        }
    }

    return false;
}
		

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

Метод IndexOf

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

			public int IndexOf(T item)
{
    for (int i = 0; i < Count; i++)
    {
        if (_items[i].Equals(item))
        {
            return i;
        }
    }

    return -1;
}
		

Метод Item

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

			public T this[int index]
{
    get
    {
        if(index < Count)
        {
            return _items[index];
        }

        throw new IndexOutOfRangeException();
    }
    set
    {
        if (index < Count)
        {
            _items[index] = value;
        }
        else
        {
            throw new IndexOutOfRangeException();
        }
    }
}
		

Метод Contains

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

			public bool Contains(T item)
{
    return IndexOf(item) != -1;
}
		

Перебор

Метод GetEnumerator

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

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

			public System.Collections.Generic.IEnumerator GetEnumerator()
{
    for (int i = 0; i < Count; i++)
    {
        yield return _items[i];
    }
}

System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}
		

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

Метод Clear

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

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

			public void Clear()
{
    _items = new T[0];
    Count = 0;
}
		

Метод CopyTo

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

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

			public void CopyTo(T[] array, int arrayIndex)
{
    Array.Copy(_items, 0, array, arrayIndex, Count);
}
		

Метод Count

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

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

			public int Count
{
    get;
    private set;
}
		

Метод IsReadOnly

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

			public bool IsReadOnly
{
    get { return false; }
}
		

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

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

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