Kuidas on massiivid programmeerimises üles ehitatud?

Massiivid on järjestatud elementide kogum, mis asub üksteise järel mälupesades.

Peamised omadused:

• Indeksimine: Juurdepääs elementidele toimub indeksi kaudu, mis algab nullist. Indeks näitab nihke massiivi algusest.
• Suurus: Massiivi suurus (elementide arv) on fikseeritud selle loomise ajal statilistes keeltes või võib dünaamiliselt muutuda dünaamilistes keeltes (näiteks Swift Array).
• Andmetüüp: Kõik massiivi elemendid peavad olema sama andmetüübiga.
• Järjepidevus: Elementide salvestamine järjestikustes mälupesades tagab kiire juurdepääsu iga elemendi juurde selle indeksi järgi.

Tegevused:

• Juurdepääs indeksi järgi: O(1) - konstantselt.
• Lisamine/kustutamine lõpus: O(1) keskmiselt dünaamiliste massiivide puhul (Swift Array).
• Lisamine/kustutamine algusest või keskelt: O(n) - lineaarne aeg, kuna võib olla vaja elemente nihutada.

Näide Swiftis:

// Massiivi loomine
var names: [String] = ["Alice", "Bob", "Charlie"]

// Elementi juurdepääs indeksi järgi
let first_name = names[0] // "Alice"

// Elementi lisamine
names.append("David") // ["Alice", "Bob", "Charlie", "David"]

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

// Massiivi iteratsioon
for name in names {
    print(name)
}

Siseehitus (dünaamiliste massiivide jaoks, näiteks Swift Array):

Dünaamilised massiivid tavaliselt realiseeritakse staatiliselt eraldatud mälupuhvrile. Kui puhvri maht saavutatakse, eraldatakse uus, suurem puhver ning vanad elemendid kopeeritakse (reallokatsioon). See tagab amortiseeritud O(1) lisamise lõppu.