Hogyan épülnek fel a tömbök a programozásban?

A tömbök azonos típusú elemek rendezett gyűjteményei, amelyek egymás melletti (szekvenciális) memóriahelyeken tárolódnak.

Fő jellemzők:

• Indexelés: Az elemekhez való hozzáférés 0-tól kezdődő indexen keresztül történik. Az index a tömb elejétől való eltolódást mutatja.
• Méret: A tömb mérete (elemek száma) rögzített a létrehozáskor statikusan típusos nyelvekben, vagy dinamikusan változhat dinamikus típusú nyelvekben (pl. Swift Array).
• Adattípus: Minden tömb elemének ugyanazon adattípussal kell rendelkeznie.
• Szekvenciális elhelyezkedés: Az elemek egymás melletti memóriahelyeken való tárolása gyors hozzáférést biztosít bármely elemhez a index segítségével.

Műveletek:

• Hozzáférés index alapján: O(1) - állandó idő.
• Hozzáadás/eltávolítás a végén: O(1) átlagosan dinamikus tömbök esetén (Swift Array).
• Hozzáadás/eltávolítás a kezdetén vagy közepén: O(n) - lineáris idő, mivel az elemek eltolása szükséges lehet.

Példa Swift-ben:

// Stringekből álló tömb létrehozása
var names: [String] = ["Alice", "Bob", "Charlie"]

// Elem elérése index segítségével
let first_name = names[0] // "Alice"

// Elem hozzáadása
names.append("David") // ["Alice", "Bob", "Charlie", "David"]

// Elem eltávolítása
names.remove(at: 1) // ["Alice", "Charlie", "David"]

// Iterálás a tömbön
for name in names {
    print(name)
}

Belső szerkezet (dinamikus tömbök esetén Swift Array típus):

A dinamikus tömbök általában egy statikusan lefoglalt memória buffer felett valósulnak meg. Amikor a buffer kapacitása eléri a határt, egy nagyobb, új buffer kerül lefoglalásra, és a régi elemek másolásra kerülnek (reallocation). Ez biztosítja az amortizált O(1) komplexitást a végéhez való hozzáadásnál.