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
- Beaucoup d’accès par index, parcours séquentiels, ajouts en fin: privilégiez un tableau dynamique. Le redimensionnement par facteur (×2 classiquement) rend l’append amorti O(1).
- Insertions locales fréquentes ou suppressions en tête: une liste ou une structure dédiée (deque) est plus adaptée.
#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)
list: tableau dynamique; indexation O(1),appendamorti O(1),insert(i,x)O(n).collections.deque: file/pile à haut débit en tête/queue (append,popleftO(1)); pas d’accès indexé rapide.numpy.ndarray: bloc contigu typé, idéal pour le calcul numérique et 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.