В чем заключается отличие между массивом и списком?

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

Доступ к элементам массива осуществляется по индексу за 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]) # Фиксированный размер

# Пример списка
list_data = [1, 2, 3]
list_data.append(4) # Динамический размер
list_data[0] # Доступ O(1)

Сравнение: