Kuo skiriasi masyvas nuo sąrašo?

Masivas turi fiksuotą dydį, kuris nustatomas kuriant. Sąrašas dinamiškai keičia savo dydį, pridedant arba pašalinant elementus:

Masivo elementų prieiga per indeksą yra O(1) laiko. Prieigos prie sąrašo elementų laikas gali skirtis, pavyzdžiui, viengubo susietas sąrašas turi prieigą per indeksą už O(n), o ArrayList – vidutiniškai už O(1):

Masive elementai saugomi nuosekliuose atminties segmentuose, kas užtikrina geresnį talpyklos našumą. Sąraše elementai gali būti išsibarsčiusiose atminties vietose, susieti rodykliais:

Vidutiniškai, masyvo įterpimo ir ištrynimo operacijos reikalauja perkelti visus vėlesnius elementus, kas gali būti brangu (O(n)). Sąrašuose šios operacijos gali būti efektyvesnės (pavyzdžiui, susietuose sąrašuose, jei yra rodyklė į reikalingą elementą, O(1), kitaip – O(n) paieškai), tačiau reikalauja rodyklių atnaujinimo:

Masyvai gali tiesiogiai saugoti pagrindinius tipus. Sąrašai dažniausiai saugo nuorodas į objektus (apvalkale pagrindiniams tipams):

// Masivo pavyzdys
int[] array = new int[5];
array[0] = 10; // Prieiga O(1)

// ArrayList pavyzdys (Java)
import java.util.ArrayList;
import java.util.List;

List<Integer> list = new ArrayList<>();
list.add(10); // Pridėjimas vidutiniškai O(1)
list.get(0); // Prieiga O(1) vidutiniškai

# Masivo pavyzdys (numpy array)
import numpy as np
array = np.array([1, 2, 3]) # Fiksuotas dydis

# Sąrašo pavyzdys
list_data = [1, 2, 3]
list_data.append(4) # Dvinamis dydis
list_data[0] # Prieiga O(1)

Palyginimas:

Savybė	Masivas	Sąrašas
Dydis	Fiksuotas	Dvinamis
Prieiga per indeksą	O(1)	Keičiasi (dažniausiai O(1) arba O(n))
Atmintis	Nuosekli	Gali būti išsibarsčiusi
Įterpimas/Ištrynimas	O(n) viduryje	Keičiasi (gali būti O(1))
Duomenų tipai	Pagrindiniai tipai ir objektai	Paprastai nuorodos į objektus