Как са структурирани масивите в програмирането?

Масивите са подредени колекции от елементи от един и същи тип, съхранявани в съседни (последователни) клетки на паметта.

Основни характеристики:

• Индексиране: Достъпът до елементите става чрез индекс, който започва от 0. Индексът показва отместването от началото на масива.
• Размер: Размерът на масива (броят на елементите) е фиксиран при създаването му в езици със статичен тип или може да се променя динамично в езици с динамичен тип (например, Swift Array).
• Тип данни: Всички елементи в масива трябва да имат един и същи тип данни.
• Последователност: Съхраняването на елементите в съседни клетки на паметта осигурява бърз достъп до всеки елемент чрез неговия индекс.

Операции:

• Достъп чрез индекс: O(1) - константно време.
• Добавяне/премахване в края: O(1) средно за динамичните масиви (Swift Array).
• Добавяне/премахване в началото или в средата: O(n) - линейно време, тъй като може да е необходимо преместване на елементите.

Пример в Swift:

// Създаване на масив от низове
var names: [String] = ["Alice", "Bob", "Charlie"]

// Достъп до елемент чрез индекс
let first_name = names[0] // "Alice"

// Добавяне на елемент
names.append("David") // ["Alice", "Bob", "Charlie", "David"]

// Премахване на елемент
names.remove(at: 1) // ["Alice", "Charlie", "David"]

// Итерация през масива
for name in names {
    print(name)
}

Вътрешна структура (за динамични масиви от тип Swift Array):

Динамичните масиви обикновено се реализират върху статично заделен буфер за памет. Когато капацитетът на буфера бъде достигнат, се заделя нов, по-голям буфер и старите елементи се копират (reallocation). Това осигурява амортизирана сложност O(1) за добавяне в края.