Come sono strutturati gli array nella programmazione?

Gli array sono collezioni ordinate di elementi dello stesso tipo, memorizzati in celle di memoria contigue (sequenziali).

Caratteristiche principali:

• Indicizzazione: L'accesso agli elementi avviene tramite un indice che inizia da 0. L'indice indica lo spostamento dall'inizio dell'array.
• Dimensione: La dimensione dell'array (numero di elementi) è fissa alla sua creazione in linguaggi a tipizzazione statica o può cambiare dinamicamente in linguaggi a tipizzazione dinamica (ad esempio, in Swift Array).
• Tipo di dato: Tutti gli elementi dell'array devono avere lo stesso tipo di dato.
• Contiguità: La memorizzazione degli elementi in celle di memoria contigue garantisce un accesso rapido a qualsiasi elemento tramite il suo indice.

Operazioni:

• Accesso tramite indice: O(1) - tempo costante.
• Aggiunta/rimozione alla fine: O(1) in media per array dinamici (Swift Array).
• Aggiunta/rimozione all'inizio o nel mezzo: O(n) - tempo lineare, poiché potrebbe essere necessario spostare gli elementi.

Esempio in Swift:

// Creazione di un array di stringhe
var names: [String] = ["Alice", "Bob", "Charlie"]

// Accesso a un elemento tramite indice
let first_name = names[0] // "Alice"

// Aggiunta di un elemento
names.append("David") // ["Alice", "Bob", "Charlie", "David"]

// Rimozione di un elemento
names.remove(at: 1) // ["Alice", "Charlie", "David"]

// Iterazione sull'array
for name in names {
    print(name)
}

Struttura interna (per array dinamici di tipo Swift Array):

Gli array dinamici sono generalmente implementati su un buffer di memoria allocato staticamente. Quando si raggiunge la capacità del buffer, viene allocato un nuovo buffer più grande e gli elementi vecchi vengono copiati (reallocazione). Questo garantisce una complessità ammortizzata di O(1) per l'aggiunta alla fine.