Care este diferența dintre un array și o listă?

Array-ul are o dimensiune fixă, determinată la crearea sa. Lista își ajustează dimensiunea în mod dinamic atunci când adaugă sau elimină elemente.

Accesul la elementele array-ului se face după index în O(1). Accesul la elementele listei poate varia, de exemplu, o listă simplu înlănțuită are acces după index în O(n), în timp ce ArrayList în medie în O(1).

În array, elementele sunt stocate în zone continue de memorie, ceea ce asigură un performanță mai bună a cache-ului. În listă, elementele pot fi dispersate în memorie, legate prin pointeri.

Operațiile de inserare și ștergere în mijlocul array-ului necesită deplasarea tuturor elementelor următoare, ceea ce poate fi costisitor (O(n)). În liste, aceste operații pot fi mai eficiente (de exemplu, în liste înlănțuite O(1) dacă există un pointer către element, altfel O(n) pentru căutare), dar necesită actualizarea pointerilor.

Array-urile pot stoca direct tipuri primitive. Listele de obicei stochează referințe către obiecte (ambalaje pentru tipuri primitive).

// Exemplu de array
int[] array = new int[5];
array[0] = 10; // Acces O(1)

// Exemplu de ArrayList (listă în Java)
import java.util.ArrayList;
import java.util.List;

List<Integer> list = new ArrayList<>();
list.add(10); // Adăugare O(1) în medie
list.get(0); // Acces O(1) în medie

# Exemplu de array (numpy array)
import numpy as np
array = np.array([1, 2, 3]) # Dimensiune fixă

# Exemplu de listă
date_lista = [1, 2, 3]
lista_din = [4]

# Acces
lista_din[0] # O(1)

Comparare:

Caracteristică	Array	Listă
Dimensiune	Fixă	Dinamic
Acces după index	O(1)	Variabil (adesea O(1) sau O(n))
Memorie	Continuă	Poate fi dispersată
Inserare/Ștergere	O(n) în mijloc	Variabil (poate fi O(1))
Tipuri de date	Primitiv și obiecte	De obicei referințe la obiecte