Структура данных - массивы

Основы

Массив (список) - набор элементов, которые хранятся непрерывно в памяти. Что означает непрерывно? Это означает, что в памяти данная структура хранится ячейка за ячейкой.

Основная идея массивов состоит в том, чтобы хранить несколько различных элементов в одном месте.

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

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

Типизация массивов

Понятное дело, что есть и определенные разновидности массивов. В частности основными типами являются:

  1. Одномерные
  2. Многомерные

Тут все просто, одномерные массивы - это те что представлены выше на картинке.

Многомерные же, массивы в которых вложены другие массивы. Но есть и другая типизация:

  1. Статические массивы
  2. Динамические массивы

Статический массив

Статический массив - массив у которого заранее предопределен его размер. Основные сложности в использовании, тесно связаны с этим ограничением. Так как если вы захотите добавить что-то сверх, вам придется создавать новый массив и перекладывать из старого все значения.

То есть по факту у вас статическая размерность массива, которая не позволит добавить что-то сверх данного размера. Такие массивы представлены во многих строго типизированных языках: C++, C#, Java и другие.

Динамический массив

Динамический массив - массив у которого динамический размер. Тут проще с использованием, однако есть и свои особенности. В частности как выделять память для такого массива. Не всегда же увеличивать ее в 2 раза, было бы очень глупой потерей памяти.

Хранение динамического массива в памяти:

Под массив всегда выделяется фрагмент в памяти RAM, размер этой памяти всегда больше требуемого. Дается такому выделению имя - емкость массива. Текущая длина хранится в отдельном счетчике. Она естественным образом нужна для того чтобы определить размер, но также и для того чтобы следить за границей массива.

Команда увеличения размера массива - если емкость не превышена, просто измнит счетчик длины массива до нужного размера. Команда увеличения размера сделает следующее:

  1. Выделит новый фрагмент в RAM, размер которого превышает размер массива
  2. Содержимое массива скопирует в эту выделенную память
  3. Размер и емкость массива обнулит
  4. В служебной стрктуре, где хранятся указатели - изменит их
  5. Запустит высвобождение памяти, которая ранее использовалась для массива