Алгоритми і структури даних для початківців динамічний масив

Алгоритми і структури даних для початківців динамічний масив

Іноді від колекції потрібно необмежена місткість і простота використання списку, але при цьому константне час доступу до довільного елементу, як в масиві. У цьому випадку використовується список на основі масиву - динамічний масив (Array List).

клас ArrayList

ArrayList - це колекція, яка реалізує інтерфейс IList і використовує масив для зберігання елементів. Як і зв'язний список, ArrayList може зберігати довільне число елементів (обмежене лише обсягом вільної пам'яті), але в іншому поводиться як масив.

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

Додавання візуального ефекту

Додавання візуального ефекту в динамічний масив відрізняється від вставки в зв'язний список. На те є дві причини. Перша: динамічний масив підтримує вставку в середину масиву, тоді як в зв'язний список можна вставляти тільки в кінець або початок. Друга: вставка елемента в зв'язний список завжди виконується за константне час. Вставка в динамічний масив може займати як O (1), так і O (n) часу.

розширення масиву

У міру додавання елементів внутрішній масив може переповниться. У цьому випадку необхідно зробити наступне:

  1. Створити масив більшого розміру.
  2. Скопіювати елементи в новий масив.
  3. Оновити посилання на внутрішній масив списку так, щоб вона вказувала на новий.

Тепер залишилося відповісти на питання, якого розміру має бути новий масив. Це визначається стратегією зростання динамічного масиву. Ми розглянемо дві стратегії і для обох подивимося, наскільки швидко зростає масив і наскільки його зростання знижує продуктивність.

Збільшення вдвічі (підхід Mono і Rotor)

Існують дві реалізації ArrayList. код яких можна знайти в мережі: Mono і Rotor. Обидві використовують простий алгоритм збільшення розміру масиву, збільшуючи його вдвічі при необхідності. Якщо початковий розмір масиву дорівнює нулю, то новий вміщуватиме 16 елементів:

Цей алгоритм робить менше виділень пам'яті, але витрачає більше місця, ніж варіант, прийнятий в Java. Іншими словами, він забезпечує більш часті випадки вставки за константне час ціною використання більшої кількості пам'яті. Процес створення нового масиву і копіювання в нього елементів відбуватиметься рідше.

Повільне зростання (підхід Java)

В Java використовується схожий підхід, але масив зростає повільніше. Розмір нового масиву визначається наступним чином:

При використанні цього алгоритму використовується менше пам'яті.

Давайте подивимося на криві зростання масивів до 200 000 елементів при використанні цих двох стратегій:

Алгоритми і структури даних для початківців динамічний масив

Як видно з графіка, для того, щоб перейти кордон в 200 000 елементів, варіанту з подвоєнням масиву знадобилося 19 операцій виділень пам'яті і копіювання, тоді як варіант Java зажадав 30 операцій.

Яка стратегія краще? Не існує правильного і неправильного відповіді на це питання. При використанні подвоєння у нас буде менше операцій вставки за O (n), але більша витрата пам'яті. При більш повільному зростанні буде використано менше пам'яті. У загальному випадку допустимі обидва варіанти. Якщо ваш додаток має специфічні вимоги, можливо, вам буде потрібно реалізувати ту чи іншу стратегію розширення. У будь-якому випадку, зовнішня поведінка динамічного масиву не зміниться.

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

метод Insert

  • Поведінка: додає елемент за вказаною індексу. Якщо індекс дорівнює кількості елементів або більше нього, кидає виняток.
  • Складність: O (n).

Вставка за певним індексом вимагає зсуву всіх елементів, починаючи з цього індексу, на одну позицію вправо. Якщо внутрішній масив заповнений, вставка потебует збільшення його розміру.

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

Масив до зсуву елементів

Масив після зсуву елементів

Масив після вставки елемента на вільну позицію

  • Поведінка: додає елемент в кінець списку.
  • Складність: 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 для проходу по всіх елементах списку.
  • Складність: Отримання ітератора - O (1), обхід списку - O (n).

Зауважте, що ми не можемо просто пройтися по масиву _items. так як він містить ще не заповнені осередки, тому ми обмежуємо діапазон, за яким будемо ітерованих кількістю елементів.

Решта методи IList

метод Clear

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

Существет два варіанти реалізації методу Clear. У першому випадку створюється новий порожній масив, у другому - тільки обнуляється поле Count. В нашій реалізації буде створюватися новий масив нульової довжини.

  • Поведінка: копіює всі елементи з внутрішнього масиву в зазначений, починаючи з зазначеного індексу.
  • Складність: O (n).

метод Count

  • Поведінка: повертає поточну кількість елементів в колекції. Якщо список порожній, повертає 0.
  • Складність: O (1).

Count - автоінкрементіруемое поле з приватним сетером і публічним геттером. Користувач може тільки прочитати його, а змінювати будуть методи додавання і видалення елементів.

метод IsReadOnly

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

Далі буде

На цьому ми закінчуємо розбір динамічних масивів. Наступного разу ми перейдемо до стека і черг.