Каква е разликата между масив и списък?

Масивът има фиксиран размер, определен при създаването му. Списъкът динамично променя размера си при добавяне или премахване на елементи.

Достъпът до елементите на масива се извършва по индекс в O(1) време. Достъпът до елементите на списъка може да варира, например, едносвързаният списък има достъп по индекс в O(n), докато ArrayList средно в O(1).

В масива елементите се съхраняват в последователни области на паметта, което осигурява по-добра кеш-производителност. В списъка елементите могат да бъдат разпръснати в паметта, свързани чрез указатели.

Операциите по вмъкване и изтриване в средата на масива изискват преместване на всички следващи елементи, което може да бъде скъпо (O(n)). В списъците тези операции могат да бъдат по-ефективни (например, в свързаните списъци O(1), ако има указател към елемента, иначе O(n) за търсене), но изискват актуализиране на указателите.

Масивите могат да съхраняват директно примитивни типове. Списъците обикновено съхраняват препратки към обекти (обвивки за примитивни типове).

// Пример за масив
int[] array = new int[5];
array[0] = 10; // Достъп O(1)

// Пример за ArrayList (списък в Java)
import java.util.ArrayList;
import java.util.List;

List<Integer> list = new ArrayList<>();
list.add(10); // Добавяне O(1) средно
list.get(0); // Достъп O(1) средно

# Пример за масив (numpy array)
import numpy as np
array = np.array([1, 2, 3]) # Фиксиран размер

# Пример за списък
data_list = [1, 2, 3]
data_list.append(4) # Динамичен размер

data_list[0] # Достъп O(1)

Сравнение:

Характеристика	Масив	Списък
Размер	Фиксиран	Динамичен
Достъп по индекс	O(1)	Варира (често O(1) или O(n))
Памет	Последователна	Може да бъде разпръсната
Вмъкване/Изтриване	O(n) в средата	Варира (може да бъде O(1))
Типове данни	Примитиви и обекти	Обикновено препратки към обекти