Это структура данных , потому что это сбор данных и инструменты для их работы.
Основные характеристики:
- Очень быстрый поиск по индексу.
- Чрезвычайно быстрый обход порядка индекса.
- Минимальный объем памяти (не так для упомянутых мной дополнительных модификаций).
Обычно вставка - это O (N), потому что вам может потребоваться скопировать массив, когда вы перераспределяете массив, чтобы освободить место для новых элементов. Однако вы можете снизить стоимость добавления к амортизированному O (1), перераспределив (т.е. удваивая размер массива каждый раз, когда вы перераспределяете). [1]
Удаление - это O (N), потому что вам нужно будет сдвинуть в среднем N / 2 элемента. Вы можете отслеживать количество неиспользуемых элементов в начале и конце массива, чтобы сделать удаления с концов O (1). [1]
Поиск по индексу - O (1). Это простое добавление указателя.
Поиск по значению O (N). Если данные упорядочены, можно использовать двоичный поиск, чтобы уменьшить это значение до O (log N).
- Отслеживание первого использованного элемента и последнего использованного элемента технически квалифицируется как другая структура данных, поскольку функции для доступа к структуре данных различны, но все равно будут называться массивом.