Tableaux et listes
Progression
#Tableaux et listes
Deux façons d’aligner des éléments en mémoire racontent deux histoires différentes. Le tableau dynamique est une étagère d’emplacements contigus: on sait pointer directement le 37ᵉ, ce qui rend l’accès indexé très rapide et “amical” pour les caches. Mais insérer en plein milieu oblige à décaler ceux à droite.
La liste chaînée est un sentier balisé: chaque maillon connaît le suivant. Glisser un nouveau maillon entre deux existants est facile si vous êtes déjà au bon endroit; en revanche, accéder au 37ᵉ impose de suivre 36 flèches — et les sauts en mémoire perdent le bénéfice des caches.
#Quand l’un brille plus que l’autre
Si votre usage implique de nombreux accès par index, des parcours séquentiels ou des ajouts fréquents en fin de structure, le tableau dynamique est le choix optimal. Son redimensionnement amorti garantit une complexité moyenne de O(1) pour les ajouts.
En revanche, si vous devez effectuer fréquemment des insertions locales ou des suppressions en tête, une liste chaînée ou une structure dédiée comme une deque sera bien plus performante.
#Exemple guidé (insertion triée)
1# Pseudo‑code pour insertion triée dans une liste chaînée2def insert_sorted(head, x):3 if not head or x < head.val:4 return Node(x, head)5 cur = head6 while cur.next and cur.next.val < x:7 cur = cur.next8 cur.next = Node(x, cur.next)9 return head#Visualiser le coût d’une insertion
/>
#Cas pratiques (Python)
En Python, le type list est implémenté comme un tableau dynamique, offrant une indexation en O(1) et un append amorti en O(1), mais un coût linéaire O(n) pour les insertions arbitraires.
Pour des besoins de file ou de pile avec un haut débit en tête et en queue, collections.deque est la structure idéale (append et popleft en O(1)), bien qu'elle ne permette pas d'accès indexé rapide. Enfin, pour le calcul numérique intensif, numpy.ndarray fournit un bloc mémoire contigu et typé, optimisé pour la vectorisation.
- Insérer souvent au début d’une
list→ préférezdeque. - Itérer des listes chaînées d’objets lourds → localité médiocre, ralentissements.
- Copier de gros tableaux inutilement → recherchez des opérations in‑place.
#Mini‑exercice (5 minutes)
Implémentez une file FIFO en Python de deux manières: (1) list avec append/pop(0), (2) deque avec append/popleft. Mesurez le temps pour 100 000 opérations et comparez.