Kaip struktūruoti masyvai programavime?

Masyvai yra tvarkingos elementų kolekcijos, saugomos šalia viena kitos atminties ląstelėse.

Pagrindinės savybės:

• Indeksavimas: Prieiga prie elementų vyksta pagal indeksą, pradedant nuo 0. Indeksas nurodo nuotolį nuo masyvo pradžios.
• Dydis: Masyvo dydis (elementų skaičius) yra fiksuotas jo sukūrimo metu statiniuose tipizuotuose kalbose arba gali būti dinamiškai keičiamas dinamiškai tipizuotuose kalbose (pvz., Swift Array).
• Duomenų tipas: Visi masyvo elementai turi būti to paties duomenų tipo.
• Šalia: Elementų saugojimas šalia vienas kito atminties ląstelėse užtikrina greitą prieigą prie bet kurio elemento pagal jo indeksą.

Operacijos:

• Prieiga pagal indeksą: O(1) - pastovus laikas.
• Pridėjimas/panaikinimas pabaigoje: O(1) vidutiniškai dinamiškuose masyvuose (Swift Array).
• Pridėjimas/panaikinimas pradžioje ar viduryje: O(n) - linijinis laikas, nes gali prireikti perkelti elementus.

Pavyzdys Swift:

// Masyvo kūrimas
var names: [String] = ["Alice", "Bob", "Charlie"]

// Prieiga prie elemento pagal indeksą
let first_name = names[0] // "Alice"

// Elemento pridėjimas
names.append("David") // ["Alice", "Bob", "Charlie", "David"]

// Elemento panaikinimas
names.remove(at: 1) // ["Alice", "Charlie", "David"]

// Masyvo iteracija
for name in names {
    print(name)
}

Vidinė struktūra (dinamiškiems masyvams, pvz., Swift Array):

Dinamiški masyvai dažniausiai įgyvendinami ant statinio atminties buferio. Kai pasiekiama buferio talpa, išskiriamas naujas, didesnis buferis, o seni elementai kopijuojami (realiokacija). Tai užtikrina amortizuotą O(1) laiką pridėjimui pabaigoje.