Articolo originale: Data Structures 101: Arrays — A Visual Introduction for Beginners
Impara a conoscere le strutture dati che usi ogni giorno.
👋 Benvenuto! Iniziamo con un po' di necessario contesto. Ho qualche domanda per te:
✅ Ascolti musica sul tuo smartphone?
✅ Mantieni un elenco di contatti sul telefono?
✅ Hai mai visto una classifica durante una competizione?
Se la tua risposta è "sì" a una qualsiasi di queste domande, allora è quasi certo che hai usato gli array e non lo sapevi nemmeno! 😃 Gli array sono strutture di dati molto potenti che memorizzano elenchi di elementi. Hanno infinite applicazioni. Sono molto importanti nel mondo dell'informatica.
In questo articolo imparerai i pro e i contro degli array, la loro struttura, le operazioni che puoi eseguire su di essi e i casi d'uso.
Cominciamo! 👍
🔎 Approfondimento della struttura di base degli array
Per capire come funzionano, è molto utile visualizzare la memoria del tuo computer come una griglia, proprio come quella qui sotto. Ogni parte di informazione viene conservata in uno di quei piccoli elementi (i quadrati) che compongono la griglia.
Gli array si avvalgono di questa struttura a "griglia" per conservare elenchi di informazioni correlate in posizioni di memoria adiacenti al fine di garantire estrema efficienza nel trovare questi valori. 🔳🔳🔳🔳
Puoi visualizzare la struttura di un array in questo modo:
Gli elementi di un array sono adiacenti nella memoria. Se devi accedere a più di uno di essi, il processo è estremamente ottimizzato in quanto il tuo computer sa già dove si trova il valore.
Stupendo, non è vero? Impariamo come avviene dietro le quinte! 😃
📚 Classificazione
Gli array sono classificati come Strutture Dati Omogenee in quanto conservano elementi dello stesso tipo.
Possono conservare numeri, stringhe, valori booleani (vero e falso), caratteri, oggetti e così via. Ma una volta definito il tipo di valore che dovrà contenere il tuo array, tutti i suoi elementi dovranno essere dello stesso tipo. Non puoi "mischiare" elementi di tipi diversi.
👀 Leggere Valori — La Magia Inizia!
Il meraviglioso potere degli array proviene direttamente dalla loro efficienza nell'accedere ai valori. Questo avviene grazie alla loro struttura tipo griglia. Esaminiamo il processo in maggiore dettaglio.🔍
Quando crei un array:
- Lo assegni a una variabile. 👈
- Definisci il tipo di elementi che dovrà contenere. 🎈
- Definisci la sua dimensione (il numero massimo di elementi). 📚
💡 Nota: Il nome che assegni a questa variabile è molto importante in quanto lo utilizzerai successivamente nel tuo codice per accedere e/o modificarne i valori.
Ma come puoi dire al computer di accedere a un particolare valore? Qui gli indici hanno un ruolo vitale!
1️⃣ Indici
Si usa quello che viene chiamato "indice" per accedere a un valore in un array. È un numero che fa riferimento alla posizione in cui il valore è conservato.
Come puoi vedere nel diagramma qui sotto, il primo elemento dell'array viene indirizzato usando l'indice 0. Mano a mano che ti sposti verso destra, il valore dell'indice aumenta di uno per ciascuno spazio in memoria.
💡 Nota: So che partire a contare da 0 invece che da 1 può sembrare strano, ma è quella che viene chiamata Numerazione a base zero. È molto comune in informatica.
La sintassi generale per accedere a un elemento è <VariabileArray>[<indice>]
Per esempio:
Se il tuo array è associato alla variabile myArray e vuoi accedere al primo elemento (indice 0), dovresti usare myArray[0]
2️⃣ Memoria
Ora che sai come accedere ai valori, vediamo come sono conservati gli array nella memoria del computer. Quando definisci la dimensione di un array, tutto lo spazio in memoria corrispondente alla dimensione viene "riservato" da quel momento in poi per valori futuri che vorresti poter inserire.
💡 Nota: Se non riempi tutto l'array con valori, quello spazio verrà riservato e mantenuto vuoto fino a quando non lo farai.
Per esempio:
Diciamo che definisci un array di dimensione 5 ma inserisci un solo valore. Tutto lo spazio rimanente sarà vuoto e "riservato" in memoria, in attesa di future assegnazioni.
Questa è la chiave: gli array sono estremamente efficienti nell'accedere ai valori in quanto tutti gli elementi sono conservati in spazi contigui di memoria. In questo modo, il computer sa esattamente dove cercare per trovare le informazioni che hai richiesto.
Ma… c'è un aspetto negativo 😞 in quanto non è efficiente dal punto di vista della memoria. Stai riservando memoria per operazioni future che potrebbero non accadere mai. Ecco perché gli array sono consigliati in situazioni dove sai in anticipo quanti elementi andrai a conservare.
🔧 Operazioni — Dietro le quinte!
Ora che sai cosa sono gli array, quando vengono usati e come conservano i loro elementi, approfondiremo le operazioni che si possono compiere su di essi come l'inserimento e l'eliminazione.
1️⃣ Inserimento — Benvenuto!
Supponiamo di avere un array di dimensione 6 e di avere ancora spazio vuoto all'interno. Vogliamo inserire un elemento "e" all'inizio dell'array (indice 0), ma questa posizione è già occupata dall'elemento "a". Cosa dovremmo fare?
Per inserire elementi negli array, spostiamo tutti gli elementi già presenti che si trovano alla destra della posizione di inserimento di una posizione in avanti verso destra. L'elemento "a" ora sarà a indice 1, l'elemento "b" a indice 2 e così via…
💡 Nota: Potresti aver bisogno di creare una variabile per tenere traccia del valore dell'ultimo indice che contiene elementi. Nel diagramma qui sopra, l'array viene riempito fino all'indice 4 prima dell'inserimento. In questo modo, puoi determinare se l'array è pieno e quale indice dovresti utilizzare per inserire un elemento alla fine.
Dopo aver fatto questo, il nuovo elemento viene inserito con successo. 👏
⚠️ Aspetta un minuto! Cosa succede se l'array è pieno?
Cosa pensi che accada se l'array è pieno e cerchi di inserire un elemento? 😱
In questo caso devi creare un array nuovo più grande, poi copiare manualmente tutti gli elementi nel nuovo array. Questa operazione è molto onerosa dal punto di vista del tempo. Immagina cosa accadrebbe se avessi un array con milioni di elementi! Potrebbe volerci moltissimo tempo per completare l'operazione. ⏳
💡 Nota: L'unica eccezione a questa regola, laddove l'inserimento è molto veloce, è quando inserisci un elemento alla fine dell'array (alla posizione di indice alla destra dell'ultimo elemento) e c'è ancora spazio disponibile. Questo viene fatto con un tempo costante O(1).
2️⃣ Cancellazione— Ciao Ciao!
Diciamo ora che vuoi eliminare un elemento dall'array.
Per mantenere l'efficienza per l'accesso casuale (essere in grado di accedere in modo estremamente veloce all'array tramite un indice) gli elementi devono essere conservati in spazi contigui di memoria. Non puoi semplicemente eliminare l'elemento e lasciare uno spazio vuoto.
Dovresti spostare di una posizione a sinistra gli elementi situati dopo l'elemento che vuoi cancellare.
Alla fine l'array risulterà questo 👇. Come puoi vedere, "b" è stato eliminato con successo.
💡 Nota: La cancellazione è molto efficiente quando rimuove l'ultimo elemento. Visto che devi creare una variabile che tenga traccia dell'ultimo indice che contiene un elemento (nel diagramma qui sopra, 3), puoi rimuovere direttamente l'elemento usando l'indice.
3️⃣ Trovare un elemento
Hai tre opzioni per trovare un elemento in un array:
- Se conosci la sua posizione, usa l'indice.
- Se non conosci la sua posizione e i tuoi dati sono ordinati, puoi usare degli algoritmi per ottimizzare la tua ricerca, come la Ricerca Binaria.
- Se non conosci la sua posizione e i dati non sono ordinati, devi scorrere tutti gli elementi nell'array e verificare se l'elemento corrente è quello che stai cercando (vedi la serie di diagrammi qui sotto).
👋 Riepilogando …
- Gli array sono strutture dati estremamente potenti che conservano elementi dello stesso tipo. Il tipo degli elementi e la dimensione dell'array sono fissi e definiti in fase di creazione.
- La memoria è allocata immediatamente dopo che l'array è creato ed è vuota fino a quando non assegni i valori.
- Gli elementi sono posti in posizioni contigue di memoria, in modo che vi si possa accedere in modo molto efficiente (accesso casuale O(1) = tempo costante) usando gli indici.
- Gli indici partono da 0, non da 1 come siamo abituati.
- L'inserimento di elementi all'inizio o in mezzo all'array comporta lo spostamento degli elementi verso destra. Se l'array è pieno, occorre creare un nuovo array di maggiori dimensioni (il che non è molto efficiente). L'inserimento alla fine dell'array è molto efficiente - tempo costante O(1).
- La rimozione di elementi dall'inizio o nel mezzo dell'array comporta lo spostamento di tutti gli elementi verso sinistra per evitare di lasciare uno spazio vuoto in memoria. Questo garantisce che gli elementi siano conservati in spazi di memoria contigui. La rimozione di un elemento alla fine dell'array è molto efficiente in quanto cancelli solo l'ultimo elemento senza spostare gli altri.
- Per trovare un elemento, devi controllare l'intero array fino a quando non lo trovi. Se i dati sono ordinati, puoi usare algoritmi come la Ricerca Binaria per ottimizzare il processo.
“Impara dal passato, vivi nel presente, spera nel futuro. La cosa importante è non smettere di fare domande.”
— Albert Einstein
👋 Grazie!
Spero vivamente che ti sia piaciuto il mio articolo. ❤️
Seguimi su Twitter per trovare altri articoli come questo. 😃