Jak jsou pole ve programování strukturována?

Pole jsou uspořádané kolekce prvků stejného typu, uložené v sousedních (sekvenčních) paměťových buňkách.

Hlavní vlastnosti:

• Indexování: Přístup k prvkům se provádí pomocí indexu, který začíná od 0. Index udává posun od začátku pole.
• Velikost: Velikost pole (počet prvků) je pevná při jeho vytvoření v jazycích s pevným typem nebo může být dynamicky měněna v jazycích s dynamickým typem (například v Swift Array).
• Typ dat: Všechny prvky pole musí mít stejný datový typ.
• Souslednost: Uložení prvků v sousedních paměťových buňkách zajišťuje rychlý přístup k libovolnému prvku přes jeho index.

Operace:

• Přístup přes index: O(1) - konstantní čas.
• Přidání/odstranění na konci: O(1) průměrně pro dynamické pole (Swift Array).
• Přidání/odstranění na začátku nebo uprostřed: O(n) - lineární čas, protože může být nutné posunout prvky.

Příklad v Swift:

// Vytvoření pole řetězců
var names: [String] = ["Alice", "Bob", "Charlie"]

// Přístup k prvku přes index
let first_name = names[0] // "Alice"

// Přidání prvku
names.append("David") // ["Alice", "Bob", "Charlie", "David"]

// Odstranění prvku
names.remove(at: 1) // ["Alice", "Charlie", "David"]

// Iterace přes pole
for name in names {
    print(name)
}

Vnitřní struktura (pro dynamická pole typu Swift Array):

Dynamická pole jsou obvykle implementována na základě staticky přiděleného bufferu paměti. Když kapacita bufferu dosáhne, je alokován nový, větší buffer a staré prvky jsou zkopírovány (reallocace). To zajišťuje amortizovanou složitost O(1) pro přidání na konec.