Mis vahe on massiivi ja nimekirja vahel?

Massiiv on fikseeritud suurusega, mis määratakse loomise ajal. Nimekiri muutub dünaamiliselt suurust, lisades või eemaldades elemente:

Massiivi elementidele pääseb ligi indeksiga O(1) ajal. Pääs nimekirja elementidele võib varieeruda, näiteks ühe-ühendatud nimekiri võimaldab ligipääsu indeksiga O(n), samas kui ArrayList keskmiselt O(1):

Massiivis hoitakse elemente pidevates mälupiirkondades, mis tagab parema vahemälupuhvri jõudluse. Nimekirjas võivad elemendid olla hajutatud mälus, seotud näitajate kaudu:

Keskmiselt nõuab massiivi sisestamine ja kustutamine keskosas kõigi järgnevate elementide nihutamist, mis võib olla kulukas (O(n)). Nimekirjades võivad need operatsioonid olla tõhusamad (näiteks seotud nimekirjades, kui on näitaja vajaliku elemendi juurde, siis O(1), vastasel juhul O(n) otsimiseks), kuid nõuavad näitajate uuendamist:

Massiivid võivad otse hoida primitiivseid tüüpe. Nimekirjad tavaliselt hoiavad viiteid objektidele (ümbrised primitiivsetele tüüpidele):

// Näide massiivist
int[] array = new int[5];
array[0] = 10; // Ligipääs O(1)

// ArrayList näide (Java)
import java.util.ArrayList;
import java.util.List;

List<Integer> list = new ArrayList<>();
list.add(10); // Lisamine keskmiselt O(1)
list.get(0); // Ligipääs O(1) keskmiselt

# Näide massiivist (numpy array)
import numpy as np
array = np.array([1, 2, 3]) # Fikseeritud suurus

# Näide nimekirjast
list_data = [1, 2, 3]
list_data.append(4) # Dünaamiline suurus
list_data[0] # Ligipääs O(1)

Võrdlus:

Omadus	Massiiv	Nimekiri
Suurus	Fikseeritud	Dünaamiline
Ligipääs indeksiga	O(1)	Muutuv (tihti O(1) või O(n))
Mälu	Pidev	Võib olla hajutatud
Lisamine/Kustutamine	O(n) keskosas	Muutuv (võib olla O(1))
Andmetüübid	Põhityypid ja objektid	Tavaliselt viited objektidele