Ako sú v programovaní usporiadané polia?

Pole sú zoradené kolekcie prvkov rovnakého typu, uložené v susedných (sekvenčných) pamäťových bunkách.

Hlavné vlastnosti:

• Indexovanie: Prístup k prvkom sa vykonáva pomocou indexu, ktorý začína od 0. Index ukazuje posun od začiatku poľa.
• Veľkosť: Veľkosť poľa (počet prvkov) je pevná pri jeho vytvorení v jazykoch s pevným typom alebo sa môže dynamicky meniť v jazykoch s dynamickým typom (napríklad Swift Array).
• Druh dát: Všetky prvky poľa musia mať rovnaký dátový typ.
• Sekvenčnosť: Uloženie prvkov v susedných pamäťových bunkách zabezpečuje rýchly prístup ku ktorémukoľvek prvku pomocou jeho indexu.

Operácie:

• Prístup pomocou indexu: O(1) - konštantný čas.
• Pridanie/odstránenie na konci: O(1) priemerné pre dynamické polia (Swift Array).
• Pridanie/odstránenie na začiatku alebo v strede: O(n) - lineárny čas, pretože môže byť potrebné posunúť prvky.

Príklad v Swift:

// Vytvorenie poľa reťazcov
var names: [String] = ["Alice", "Bob", "Charlie"]

// Prístup k prvku pomocou indexu
let first_name = names[0] // "Alice"

// Pridanie prvku
names.append("David") // ["Alice", "Bob", "Charlie", "David"]

// Odstránenie prvku
names.remove(at: 1) // ["Alice", "Charlie", "David"]

// Iterácia cez pole
for name in names {
    print(name)
}

Vnútorná štruktúra (pre dynamické polia typu Swift Array):

Dynamické polia sú zvyčajne implementované na základe staticky prideleného bufferu pamäte. Keď kapacita bufferu dosiahne, alokuje sa nový, väčší buffer a staré prvky sa kopírujú (reallocácia). To zabezpečuje amortizovanú zložitosť O(1) pre pridanie na konci.