Динамические массивы (изучаю структуры данных)

Jan 22, 2022

При изучении тематики динамические массивы изучил следующие моменты:

• Основные параметры: Мера сложности О(1) - получаем любой элемент по индексу
  Свободно расширяется
  
• Каждый раз при увеличении массива менять размер памяти неэффективно, поэтому есть буфер
• Две схемы реаллокации (увеличения буфера):Аддитивная - размер массива маленький, буфер изменяется маленькими порциями
  Мультипликативная - изменение размера в разы (часто удваивается) *2 или /1,5 Но приводится к целому типу. Минимальная ёмкость 16 элементов.
  
• Увеличение размера происходит, когда массив заполнен, и мы ещё добавляем новые элементы.
• Уменьшение, когда заполненность ниже определенного %.
• Анализ мультипликативной схемы с помощью банковского метода.
• Атрибуты массива:count - текущее количество
  capacity - текущая емкость буфера (мин.16 ед.)
  array - указатель на память
  
• На практике используют массиво-список (массив из массивов/блоков фиксированного размера.

В практическом освоении проработаны следующие методы класса ‘’’ динамических массивов’’’

• ’'’Конструктор атрибутов экземпляра класса’’’
• ’'’Длина массива’’’
• ’'’Бронирование ячейки памяти’’’
• ’'’Проверка корректности индекса’’’
• ’'’Увеличение размера буфера для массива с сохранением элементов’’’
• ’'’Добавление элемента в конец массива’’’
• ’'’Вспомогательный метод для проверки вставки по индексу’’’
• ’'’Вспомогательный метод распечатки атрибутов экземпляра класса’’’
• ’'’Вставка нового объекта по индексу’’’’'’Отработка исключений’’’
  ’'’Увеличение ёмкости, при необходимости’’’
  ’'’Вариант вставки справа’’’
  ’'’Сдвиг объектов справа’’’
  
• ’'’Удаляем объект в позиции i’’’’'’Отработка исключений’’’
  ’'’Сдвиг объектов справа от указанного, на один шаг влево’’’
  ’'’Уменьшение ёмкости, при необходимости’’’
  
• ’'’Вспомогательный метод печати массива’’’
• ’'’Вспомогательные метод для выведения массива в список’’’

Ссылка на код

Проведен анализ сложности. Сложность О(n) т.к. присутствует цикл

Ссылка на тестирование кода