Kā ir uzbūvēti masīvi programmēšanā?

Masīvi ir sakārtotas elementu kolekcijas, kas glabājas blakus esošās atmiņas šūnās.

Galvenās īpašības:

• Indeksācija: Pieeja pie elementiem notiek pēc indeksa, sākot no 0. Indekss norāda nobīdi no masīva sākuma.
• Izmērs: Masīva izmērs (elementu skaits) ir fiksēts tā izveides brīdī statiskās tipizētās valodās vai var dinamiski mainīties dinamiski tipizētās valodās (piemēram, Swift Array).
• Datu tips: Visu masīva elementu datu tipi ir vienādi.
• Sakārtotība: Elementu glabāšana blakus atmiņas šūnās nodrošina ātru piekļuvi jebkuram elementam pēc indeksa.

Operācijas:

• Piekļuve pēc indeksa: O(1) - konstants laiks.
• Pievienošana/panākšana beigās: O(1) vidēji dinamiskiem masīviem (Swift Array).
• Pievienošana/panākšana sākumā vai vidū: O(n) - lineārs laiks, jo var būt nepieciešams pārvietot elementus.

Piemērs Swift:

// Masīva izveide
var names: [String] = ["Alice", "Bob", "Charlie"]

// Piekļuve elementam pēc indeksa
let first_name = names[0] // "Alice"

// Elementa pievienošana
names.append("David") // ["Alice", "Bob", "Charlie", "David"]

// Elementa dzēšana
names.remove(at: 1) // ["Alice", "Charlie", "David"]

// Masīva iterācija
for name in names {
    print(name)
}

Iekšējā struktūra (dinamiskiem masīviem, piemēram, Swift Array):

Dinamiski masīvi parasti tiek realizēti uz statiski piešķirta atmiņas bufera. Kad tiek sasniegta bufera ietilpība, tiek izdalīts jauns, lielāks bufers, un vecie elementi tiek kopēti (reallokācija). Tas nodrošina amortizētu O(1) pievienošanai beigās.