Quelle est la différence entre un tableau et une liste?

Le tableau a une taille fixe, déterminée lors de sa création. La liste ajuste sa taille dynamiquement lors de l'ajout ou de la suppression d'éléments.

L'accès aux éléments du tableau se fait par indice en O(1). L'accès aux éléments de la liste peut varier, par exemple, une liste chaînée simple a un accès par indice en O(n), tandis qu'ArrayList en moyenne en O(1).

Dans un tableau, les éléments sont stockés dans des zones continues de mémoire, ce qui assure une meilleure performance de cache. Dans une liste, les éléments peuvent être dispersés en mémoire, liés par des pointeurs.

Les opérations d'insertion et de suppression au milieu du tableau nécessitent de déplacer tous les éléments suivants, ce qui peut être coûteux (O(n)). Dans les listes, ces opérations peuvent être plus efficaces (par exemple, dans les listes chaînées O(1) si un pointeur vers l'élément est disponible, sinon O(n) pour la recherche), mais nécessitent la mise à jour des pointeurs.

Les tableaux peuvent stocker directement des types primitifs. Les listes stockent généralement des références à des objets (emballages pour types primitifs).

// Exemple de tableau
int[] array = new int[5];
array[0] = 10; // Accès O(1)

// Exemple d'ArrayList (liste en Java)
import java.util.ArrayList;
import java.util.List;

List<Integer> list = new ArrayList<>();
list.add(10); // Ajout O(1) en moyenne
list.get(0); // Accès O(1) en moyenne

# Exemple de tableau (numpy array)
import numpy as np
array = np.array([1, 2, 3]) # Taille fixe

# Exemple de liste
donnees_liste = [1, 2, 3]
donnees_liste.append(4) # Taille dynamique

donnees_liste[0] # Accès O(1)

Comparaison:

Caractéristique	Tableau	Liste
Taille	Fixe	Dynamique
Accès par indice	O(1)	Varie (souvent O(1) ou O(n))
Mémoire	Contiguë	Peut être dispersée
Insertion/Suppression	O(n) au milieu	Varie (peut être O(1))
Types de données	Primitifs et objets	Généralement références à des objets