Na czym polega różnica między tablicą a listą?

Tablica ma stały rozmiar, określany podczas tworzenia. Lista dynamicznie zmienia swój rozmiar podczas dodawania lub usuwania elementów.

Dostęp do elementów tablicy odbywa się po indeksie w czasie O(1). Dostęp do elementów listy może się różnić, na przykład, jednokierunkowa lista ma dostęp po indeksie w O(n), a ArrayList w średnio O(1).

W tablicy elementy są przechowywane w ciągłych obszarach pamięci, co zapewnia lepszą wydajność cache. W liście elementy mogą być rozproszone w pamięci, powiązane wskaźnikami.

Operacje wstawiania i usuwania w środku tablicy wymagają przesunięcia wszystkich kolejnych elementów, co może być kosztowne (O(n)). W listach te operacje mogą być bardziej wydajne (np. w listach powiązanych O(1), jeśli mamy wskaźnik na element, w przeciwnym razie O(n) dla wyszukiwania), ale wymagają aktualizacji wskaźników.

Tablice mogą przechowywać bezpośrednio typy prymitywne. Listy zazwyczaj przechowują odwołania do obiektów (opakowania dla typów prymitywnych).

// Przykład tablicy
int[] array = new int[5];
array[0] = 10; // Dostęp O(1)

// Przykład ArrayList (lista w Java)
import java.util.ArrayList;
import java.util.List;

List<Integer> list = new ArrayList<>();
list.add(10); // Dodanie O(1) w średnim przypadku
list.get(0); // Dostęp O(1) w średnim przypadku

# Przykład tablicy (numpy array)
import numpy as np
array = np.array([1, 2, 3]) # Stały rozmiar

# Przykład listy
dane_lista = [1, 2, 3]
lista_dane.append(4) # Dynamiczny rozmiar

lista_dane[0] # Dostęp O(1)

Porównanie:

Cecha	Tablica	Lista
Rozmiar	Stały	Dynamiczny
Dostęp po indeksie	O(1)	Zmienny (często O(1) lub O(n))
Pamięć	Kontynuowana	Może być rozproszona
Wstawianie/Usuwanie	O(n) w środku	Zmienny (może być O(1))
Typy danych	Prymitywy i obiekty	Zazwyczaj odwołania do obiektów