Mi a különbség a tömb és a lista között?

A tömbnek fix mérete van, amit létrehozáskor határoznak meg. A lista dinamikusan változtatja méretét az elemek hozzáadásakor vagy eltávolításakor.

A tömb elemei index alapján érhetők el O(1) idő alatt. A lista elemeihez való hozzáférés változó lehet, például egy egysoros láncolt lista index szerint O(n), míg az ArrayList átlagosan O(1).

A tömbben az elemek folyamatos memóriaterületeken tárolódnak, ez jobb cache teljesítményt biztosít. A listában az elemek széttagolhatottak a memóriában, pointerekkel összekapcsolva.

A beszúrás és törlés a tömb közepén költséges, mivel minden következő elemet el kell tolni, ez O(n). A listákban ezek az műveletek hatékonyabbak lehetnek (pl. láncolt listákban O(1), ha van mutató az elemre, különben O(n) kereséshez), de mutatókat kell frissíteni.

A tömbök közvetlenül primitív típusokat tárolhatnak. A listák általában objektumokra mutató hivatkozásokat tartalmaznak (primitive típusok wrapperjei).

// Példa tömb
int[] array = new int[5];
array[0] = 10; // Elérés O(1)

// Példa ArrayList-re (Java listára)
import java.util.ArrayList;
import java.util.List;

List<Integer> list = new ArrayList<>();
list.add(10); // Hozzáadás átlagosan O(1)
list.get(0); // Elérés átlagosan O(1)

# NumPy tömb példa
import numpy as np
array = np.array([1, 2, 3]) # Fix méret

# Lista példa
data_list = [1, 2, 3]
data_list.append(4) # Dinamikus méret

data_list[0] # Elérés O(1)

Összehasonlítás:

Jellemző	Tömb	Lista
Méret	Fix	Dinamik
Index szerinti elérés	O(1)	Változó (gyakran O(1) vagy O(n))
Memória	Kontiguó	Szétszórt lehet
Beszúrás/Törlés	O(n) középen	Változó (lehet O(1))
Adattípusok	Primitív és objektumok	Általában objektumokra mutató hivatkozások