Cum sunt structurate array-urile în programare?

Array-urile sunt colecții ordonate de elemente ale aceluiași tip, stocate în celule de memorie adiacente (secvențiale).

Caracteristici principale:

• Indexare: Accesul la elemente se face printr-un index care începe de la 0. Indexul indică deplasarea față de începutul array-ului.
• Dimensiune: Dimensiunea array-ului (numărul de elemente) este fixă la crearea sa în limbaje cu tipizare statică sau poate fi modificată dinamic în limbaje cu tipizare dinamică (de exemplu, în Swift Array).
• Tip de date: Toate elementele array-ului trebuie să aibă același tip de date.
• Contiguitate: Stocarea elementelor în celule de memorie adiacente asigură acces rapid la orice element după index.

Operații:

• Acces după index: O(1) - timp constant.
• Adăugare/ștergere la final: O(1) în medie pentru array-urile dinamice (Swift Array).
• Adăugare/ștergere la început sau în mijloc: O(n) - timp liniar, deoarece poate fi necesară deplasarea elementelor.

Exemplu în Swift:

// Crearea unui array de string-uri
var names: [String] = ["Alice", "Bob", "Charlie"]

// Accesarea unui element după index
let first_name = names[0] // "Alice"

// Adăugarea unui element
names.append("David") // ["Alice", "Bob", "Charlie", "David"]

// Ștergerea unui element
names.remove(at: 1) // ["Alice", "Charlie", "David"]

// Iterarea peste array
for name in names {
    print(name)
}

Structura internă (pentru array-urile dinamice de tip Swift Array):

Array-urile dinamice sunt de obicei implementate pe un buffer de memorie alocat static. Când capacitatea buffer-ului este atinsă, se alocă un buffer nou, mai mare, iar elementele vechi sunt copiate (reallocare). Acest lucru asigură o complexitate amortizată de O(1) pentru adăugarea la final.