Kāda ir atšķirība starp masīvu un sarakstu?

Masīvs ir ir fiksēta izmēra, kas tiek noteikts izveides laikā. Saraksts dinamiski maina savu izmēru, pievienojot vai noņemot elementus:

Masīva elementiem piekļūšana pēc indeksa ir O(1) laika. Piekļuve saraksta elementiem var atšķirties, piemēram, vienvirziena saistītais saraksts ir pieejams pēc indeksa par O(n), bet ArrayList – vidēji par O(1):

Masīvā elementi tiek glabāti nepārtrauktās atmiņas vietās, kas nodrošina labāku kešatmiņas veiktspēju. Sarakstā elementi var būt izkaisīti atmiņā, sasaistīti ar norādītājiem:

Vidēji, masīva ievietošana un dzēšana vidū prasa pārvietot visus sekojošos elementus, kas var būt dārgi (O(n)). Sarakstos šīs operācijas var būt efektīvākas (piemēram, saistītos sarakstos, ja ir norādītājs uz vajadzīgo elementu, tad O(1), citādi – O(n) meklēšanai), bet prasa norādītāju atjaunināšanu:

Masīvi var tieši glabāt primitivus tipus. Saraksti parasti glabā atsauces uz objektiem (apvalkā primitivajiem tipiem):

// Masīva piemērs
int[] array = new int[5];
array[0] = 10; // Piekļuve O(1)

// ArrayList piemērs (Java)
import java.util.ArrayList;
import java.util.List;

List<Integer> list = new ArrayList<>();
list.add(10); // Pievienošana vidēji O(1)
list.get(0); // Piekļuve O(1) vidēji

# Masīva piemērs (numpy array)
import numpy as np
array = np.array([1, 2, 3]) # Fiksēts izmērs

# Saraksta piemērs
list_data = [1, 2, 3]
list_data.append(4) # Dinamisks izmērs
list_data[0] # Piekļuve O(1)

Salīdzinājums:

Īpašība	Masīvs	Saraksts
Izmērs	Fiksēts	Dinamisks
Piekļuve pēc indeksa	O(1)	Mainās (bieži O(1) vai O(n))
Atmiņa	Nepārtraukta	Var būt izkaisīta
Ievietošana/Noņemšana	O(n) vidū	Mainās (var būt O(1))
Datu tipi	Primārie tipi un objekti	Parasti atsauces uz objektiem