Tableaux et listes chaînées#
Introduction aux structures de données linéaires#
Une structure de données est une façon d’organiser et de stocker des données en mémoire de sorte que certaines opérations (accès, insertion, suppression, recherche) puissent être effectuées efficacement. Le choix de la bonne structure de données est souvent aussi important que le choix de l’algorithme : un algorithme optimal sur une mauvaise structure peut être moins efficace qu’un algorithme simple sur une structure adaptée.
Les structures de données linéaires organisent les éléments en une séquence ordonnée, où chaque élément possède un prédécesseur et un successeur uniques (à l’exception du premier et du dernier). Les deux structures fondamentales de cette catégorie sont le tableau et la liste chaînée.
Définition 27 (Structure de données linéaire)
Une structure de données linéaire est une collection d’éléments organisés en séquence, dans laquelle chaque élément est connecté à son voisin immédiat. On peut parcourir tous les éléments en suivant les connexions de l’un à l’autre. Les structures linéaires comprennent les tableaux, les listes chaînées, les piles et les files.
Le tableau (array)#
Le tableau est la structure de données la plus fondamentale. Sa caractéristique principale est que ses éléments sont stockés de façon contiguë en mémoire.
Définition 28 (Tableau (array))
Un tableau est une collection de \(n\) éléments de même type stockés dans des emplacements mémoire consécutifs. Si l’adresse de base est \(\alpha\) et que chaque élément occupe \(s\) octets, alors l’élément d’indice \(i\) (en base 0) se trouve à l’adresse \(\alpha + i \cdot s\).
Cette propriété d’adressage direct implique que l’accès à un élément quelconque par son indice est une opération \(O(1)\) : il suffit d’un calcul arithmétique, sans parcours.
Remarque 10
La contiguïté mémoire est le point fort et le point faible du tableau :
Points forts :
Accès en \(O(1)\) par indice : une seule opération mémoire.
Excellente localité de cache : les éléments voisins sont en mémoire adjacente, ce qui favorise le chargement préalable du cache (cache prefetching). Sur les processeurs modernes, cet avantage est considérable.
Espace mémoire minimal : pas de pointeurs supplémentaires.
Points faibles :
Taille fixe pour les tableaux statiques (allocation à la compilation).
Insertion en position \(i\) : il faut décaler tous les éléments de \(i\) à \(n-1\) vers la droite, soit \(O(n)\) opérations.
Suppression en position \(i\) : il faut décaler tous les éléments suivants vers la gauche, soit \(O(n)\) opérations.
Complexité des opérations sur un tableau#
Opération |
Tableau statique |
Commentaire |
|---|---|---|
Accès |
\(O(1)\) |
Calcul d’adresse direct |
Modification |
\(O(1)\) |
Écriture à l’adresse calculée |
Recherche (non trié) |
\(O(n)\) |
Parcours séquentiel |
Recherche (trié) |
\(O(\log n)\) |
Recherche binaire |
Insertion en début |
\(O(n)\) |
Décalage de tous les éléments |
Insertion en fin |
\(O(1)\) |
Si place disponible |
Suppression au milieu |
\(O(n)\) |
Décalage des éléments suivants |
La liste Python : tableau dynamique#
En Python, le type list n’est pas un tableau statique de taille fixe : c’est un tableau dynamique (dynamic array), également connu sous le nom de tableau redimensionnable.
Définition 29 (Tableau dynamique)
Un tableau dynamique est un tableau qui peut croître ou décroître automatiquement. Il maintient en interne un tableau de taille \(c\) (la capacité) et un compteur \(n\) (le nombre d’éléments). Lorsque \(n = c\) et qu’on tente d’ajouter un élément, le tableau alloue un nouveau tableau de taille \(\alpha \cdot c\) (avec \(\alpha > 1\), typiquement \(\alpha = 2\)), copie les \(n\) éléments, puis insère le nouvel élément.
Remarque 11
L’analyse amortie de l’opération append sur un tableau dynamique montre qu’elle est \(O(1)\) en temps amorti, même si chaque redimensionnement individuel coûte \(O(n)\).
Voici pourquoi : en doublant la capacité à chaque redimensionnement, on effectue des redimensionnements après \(1, 2, 4, 8, 16, \ldots\) insertions. Pour \(n\) insertions, le coût total des copies est \(1 + 2 + 4 + \cdots + n \leq 2n = O(n)\). Divisé par \(n\) opérations, cela donne \(O(1)\) par opération en moyenne.
En Python, le facteur de croissance utilisé par CPython est légèrement inférieur à 2 (environ 1,125 pour les petits tableaux, convergeant vers 2), ce qui offre un bon équilibre entre économie de mémoire et coût de redimensionnement.
import sys
def analyser_croissance_liste():
"""
Observe la croissance interne de la liste Python en suivant l'évolution
de la taille allouée via sys.getsizeof.
"""
liste = []
taille_precedente = sys.getsizeof(liste)
print(f"{'Longueur':>10} {'Taille (octets)':>18} {'Croissance':>12}")
print("-" * 44)
print(f"{0:>10} {taille_precedente:>18}")
for i in range(1, 65):
liste.append(i)
taille_actuelle = sys.getsizeof(liste)
if taille_actuelle != taille_precedente:
croissance = taille_actuelle - taille_precedente
print(f"{len(liste):>10} {taille_actuelle:>18} {'+' + str(croissance):>12}")
taille_precedente = taille_actuelle
analyser_croissance_liste()
Longueur Taille (octets) Croissance
--------------------------------------------
0 56
1 88 +32
5 120 +32
9 184 +64
17 248 +64
25 312 +64
33 376 +64
41 472 +96
53 568 +96
# Démonstration de la complexité des opérations sur une liste Python
import timeit
def benchmark_liste(n: int):
"""Benchmark des opérations clés sur une liste de taille n."""
liste = list(range(n))
# Accès par indice : O(1)
t_acces = timeit.timeit(lambda: liste[n // 2], number=100_000) / 100_000
# append en fin : O(1) amorti
t_append = timeit.timeit(lambda: liste.copy().append(999), number=10_000) / 10_000
# insert en début : O(n)
t_insert_debut = timeit.timeit(lambda: liste.copy().insert(0, 999), number=1_000) / 1_000
# insert en milieu : O(n)
t_insert_milieu = timeit.timeit(lambda: liste.copy().insert(n // 2, 999), number=1_000) / 1_000
return t_acces, t_append, t_insert_debut, t_insert_milieu
tailles = [1_000, 10_000, 100_000]
print(f"{'Taille':>10} {'Accès (µs)':>12} {'append (µs)':>13} {'insert[0] (µs)':>16} {'insert[n/2] (µs)':>18}")
print("-" * 72)
for n in tailles:
a, b, c, d = benchmark_liste(n)
print(f"{n:>10,} {a*1e6:>12.3f} {b*1e6:>13.3f} {c*1e6:>16.3f} {d*1e6:>18.3f}")
print("\nConclusion : l'accès et append sont constants ; insert[0] croît linéairement.")
Taille Accès (µs) append (µs) insert[0] (µs) insert[n/2] (µs)
------------------------------------------------------------------------
1,000 0.094 2.678 3.784 2.941
10,000 0.100 50.137 54.068 52.088
100,000 0.096 911.395 905.118 824.271
Conclusion : l'accès et append sont constants ; insert[0] croît linéairement.
La liste chaînée simple#
Là où le tableau optimise l’accès par indice, la liste chaînée optimise les insertions et suppressions en positions connues.
Définition 30 (Liste chaînée simple)
Une liste chaînée simple (singly linked list) est une séquence de nœuds, où chaque nœud contient :
une valeur (la donnée stockée) ;
un pointeur (ou référence) vers le nœud suivant, ou
Nonepour le dernier nœud.
La liste est accessible via un pointeur vers le premier nœud (la tête, head). L’accès à un élément requiert de partir de la tête et de suivre les pointeurs, ce qui prend \(O(n)\) dans le pire cas.
La caractéristique clé est que les nœuds peuvent être stockés n’importe où en mémoire : il n’y a pas de contrainte de contiguïté. En contrepartie, chaque nœud doit stocker un pointeur supplémentaire, ce qui augmente la consommation mémoire.
from __future__ import annotations
from typing import Optional, Iterator, TypeVar, Generic
T = TypeVar('T')
class Noeud(Generic[T]):
"""Nœud d'une liste chaînée simple."""
def __init__(self, valeur: T, suivant: Optional['Noeud[T]'] = None):
self.valeur = valeur
self.suivant = suivant
def __repr__(self) -> str:
return f"Noeud({self.valeur!r})"
class ListeChainee(Generic[T]):
"""
Liste chaînée simple avec opérations fondamentales.
Complexités :
- Insertion en tête : O(1)
- Insertion en queue : O(n) sans pointeur de queue, O(1) avec
- Suppression en tête : O(1)
- Suppression d'un élément : O(n) (recherche) + O(1) (suppression)
- Accès par indice : O(n)
- Recherche : O(n)
- Longueur : O(n) sans compteur, O(1) avec compteur
"""
def __init__(self):
self._tete: Optional[Noeud[T]] = None
self._taille: int = 0
def __len__(self) -> int:
return self._taille
def est_vide(self) -> bool:
return self._tete is None
def inserer_en_tete(self, valeur: T) -> None:
"""Insère un élément en tête de liste. O(1)."""
nouveau = Noeud(valeur, self._tete)
self._tete = nouveau
self._taille += 1
def inserer_en_queue(self, valeur: T) -> None:
"""Insère un élément en queue de liste. O(n)."""
nouveau = Noeud(valeur)
if self._tete is None:
self._tete = nouveau
else:
courant = self._tete
while courant.suivant is not None:
courant = courant.suivant
courant.suivant = nouveau
self._taille += 1
def inserer_apres(self, noeud: Noeud[T], valeur: T) -> None:
"""Insère un élément après un nœud donné. O(1)."""
nouveau = Noeud(valeur, noeud.suivant)
noeud.suivant = nouveau
self._taille += 1
def supprimer_tete(self) -> T:
"""Supprime et retourne la valeur en tête. O(1)."""
if self.est_vide():
raise IndexError("Suppression sur liste vide.")
valeur = self._tete.valeur
self._tete = self._tete.suivant
self._taille -= 1
return valeur
def rechercher(self, valeur: T) -> Optional[Noeud[T]]:
"""Recherche un nœud par valeur. O(n)."""
courant = self._tete
while courant is not None:
if courant.valeur == valeur:
return courant
courant = courant.suivant
return None
def supprimer_valeur(self, valeur: T) -> bool:
"""Supprime la première occurrence de valeur. O(n)."""
if self.est_vide():
return False
if self._tete.valeur == valeur:
self._tete = self._tete.suivant
self._taille -= 1
return True
courant = self._tete
while courant.suivant is not None:
if courant.suivant.valeur == valeur:
courant.suivant = courant.suivant.suivant
self._taille -= 1
return True
courant = courant.suivant
return False
def obtenir(self, indice: int) -> T:
"""Accès par indice. O(n)."""
if indice < 0 or indice >= self._taille:
raise IndexError(f"Indice {indice} hors bornes (taille={self._taille}).")
courant = self._tete
for _ in range(indice):
courant = courant.suivant
return courant.valeur
def __iter__(self) -> Iterator[T]:
courant = self._tete
while courant is not None:
yield courant.valeur
courant = courant.suivant
def __repr__(self) -> str:
elements = list(self)
return ' → '.join(str(e) for e in elements) + ' → None'
# --- Démonstration ---
liste = ListeChainee()
for val in [5, 3, 8, 1, 9, 2]:
liste.inserer_en_queue(val)
print("Liste initiale :", liste)
print("Longueur :", len(liste))
liste.inserer_en_tete(0)
print("Après insère(0) :", liste)
liste.supprimer_valeur(8)
print("Après suppr(8) :", liste)
print("Élément [2] :", liste.obtenir(2))
print("Recherche 9 :", liste.rechercher(9))
print("Recherche 99 :", liste.rechercher(99))
Liste initiale : 5 → 3 → 8 → 1 → 9 → 2 → None
Longueur : 6
Après insère(0) : 0 → 5 → 3 → 8 → 1 → 9 → 2 → None
Après suppr(8) : 0 → 5 → 3 → 1 → 9 → 2 → None
Élément [2] : 3
Recherche 9 : Noeud(9)
Recherche 99 : None
La liste doublement chaînée#
La liste doublement chaînée étend la liste simple en ajoutant un pointeur vers le nœud précédent dans chaque nœud.
Définition 31 (Liste doublement chaînée)
Une liste doublement chaînée (doubly linked list) est une séquence de nœuds, où chaque nœud contient :
une valeur,
un pointeur vers le nœud suivant (next),
un pointeur vers le nœud précédent (prev).
La liste est accessible via un pointeur de tête et, optionnellement, un pointeur de queue (tail). Grâce au double chaînage, l’insertion et la suppression sont en \(O(1)\) si l’on possède un pointeur vers le nœud concerné, et le parcours peut se faire dans les deux sens.
class NoeudDouble(Generic[T]):
"""Nœud d'une liste doublement chaînée."""
def __init__(self, valeur: T):
self.valeur = valeur
self.suivant: Optional['NoeudDouble[T]'] = None
self.precedent: Optional['NoeudDouble[T]'] = None
class ListeDoublement(Generic[T]):
"""
Liste doublement chaînée avec pointeurs de tête et de queue.
Complexités :
- Insertion en tête/queue : O(1)
- Suppression en tête/queue : O(1)
- Suppression d'un nœud connu : O(1)
- Accès par indice : O(n)
- Recherche : O(n)
"""
def __init__(self):
self._tete: Optional[NoeudDouble[T]] = None
self._queue: Optional[NoeudDouble[T]] = None
self._taille: int = 0
def __len__(self) -> int:
return self._taille
def inserer_en_tete(self, valeur: T) -> NoeudDouble[T]:
"""O(1)."""
noeud = NoeudDouble(valeur)
if self._tete is None:
self._tete = self._queue = noeud
else:
noeud.suivant = self._tete
self._tete.precedent = noeud
self._tete = noeud
self._taille += 1
return noeud
def inserer_en_queue(self, valeur: T) -> NoeudDouble[T]:
"""O(1)."""
noeud = NoeudDouble(valeur)
if self._queue is None:
self._tete = self._queue = noeud
else:
noeud.precedent = self._queue
self._queue.suivant = noeud
self._queue = noeud
self._taille += 1
return noeud
def supprimer_noeud(self, noeud: NoeudDouble[T]) -> T:
"""Supprime un nœud connu en O(1)."""
if noeud.precedent is not None:
noeud.precedent.suivant = noeud.suivant
else:
self._tete = noeud.suivant
if noeud.suivant is not None:
noeud.suivant.precedent = noeud.precedent
else:
self._queue = noeud.precedent
self._taille -= 1
return noeud.valeur
def __repr__(self) -> str:
elements = []
courant = self._tete
while courant is not None:
elements.append(str(courant.valeur))
courant = courant.suivant
return 'None ⟷ ' + ' ⟷ '.join(elements) + ' ⟷ None'
# Démonstration
dl = ListeDoublement()
noeuds = {}
for v in [10, 20, 30, 40, 50]:
noeuds[v] = dl.inserer_en_queue(v)
print("Liste doublement chaînée :", dl)
dl.supprimer_noeud(noeuds[30])
print("Après suppression de 30 :", dl)
dl.inserer_en_tete(5)
print("Après insertion de 5 tête:", dl)
Liste doublement chaînée : None ⟷ 10 ⟷ 20 ⟷ 30 ⟷ 40 ⟷ 50 ⟷ None
Après suppression de 30 : None ⟷ 10 ⟷ 20 ⟷ 40 ⟷ 50 ⟷ None
Après insertion de 5 tête: None ⟷ 5 ⟷ 10 ⟷ 20 ⟷ 40 ⟷ 50 ⟷ None
Liste circulaire#
Définition 32 (Liste circulaire)
Une liste circulaire est une liste chaînée (simple ou double) dans laquelle le dernier nœud pointe vers le premier nœud (et, dans le cas doublement chaîné, le premier nœud pointe vers le dernier). Il n’existe pas de pointeur None : la liste forme un cycle.
Les listes circulaires sont utiles pour les applications en tourniquet (round-robin) : planification de processus, buffers circulaires, rotation dans un jeu. En parcourant la liste, on revient naturellement au début.
class ListeCirculaire(Generic[T]):
"""
Liste circulaire simple : le dernier nœud pointe vers le premier.
On maintient un pointeur vers le dernier nœud (la queue),
ce qui permet l'insertion en tête et en queue en O(1).
"""
def __init__(self):
self._queue: Optional[Noeud[T]] = None
self._taille: int = 0
def est_vide(self) -> bool:
return self._queue is None
def inserer_en_queue(self, valeur: T) -> None:
"""Insère en queue en O(1)."""
nouveau = Noeud(valeur)
if self._queue is None:
nouveau.suivant = nouveau # pointe vers lui-même
self._queue = nouveau
else:
nouveau.suivant = self._queue.suivant # pointe vers la tête
self._queue.suivant = nouveau
self._queue = nouveau
self._taille += 1
def tete(self) -> Optional[T]:
"""Retourne la valeur en tête sans la supprimer. O(1)."""
if self.est_vide():
return None
return self._queue.suivant.valeur
def tourner(self) -> Optional[T]:
"""
Avance d'un cran (round-robin) : l'ancien second devient la tête.
Retourne la valeur de l'ancienne tête. O(1).
"""
if self.est_vide():
return None
valeur = self._queue.suivant.valeur
self._queue = self._queue.suivant
return valeur
def vers_liste(self) -> list:
"""Convertit en liste Python pour affichage."""
if self.est_vide():
return []
resultat = []
courant = self._queue.suivant # commence à la tête
for _ in range(self._taille):
resultat.append(courant.valeur)
courant = courant.suivant
return resultat
def __repr__(self) -> str:
l = self.vers_liste()
if not l:
return 'ListeCirculaire(vide)'
return ' → '.join(str(e) for e in l) + ' → (retour à la tête)'
# Simulation round-robin : 5 processus, 8 cycles
processus = ['P1', 'P2', 'P3', 'P4', 'P5']
planificateur = ListeCirculaire()
for p in processus:
planificateur.inserer_en_queue(p)
print("Planificateur initial :", planificateur)
print("\nSimulation round-robin (8 cycles) :")
for cycle in range(1, 9):
processus_actif = planificateur.tete()
planificateur.tourner()
print(f" Cycle {cycle} : exécution de {processus_actif}")
print(f" File : {planificateur.vers_liste()}")
Planificateur initial : P1 → P2 → P3 → P4 → P5 → (retour à la tête)
Simulation round-robin (8 cycles) :
Cycle 1 : exécution de P1
File : ['P2', 'P3', 'P4', 'P5', 'P1']
Cycle 2 : exécution de P2
File : ['P3', 'P4', 'P5', 'P1', 'P2']
Cycle 3 : exécution de P3
File : ['P4', 'P5', 'P1', 'P2', 'P3']
Cycle 4 : exécution de P4
File : ['P5', 'P1', 'P2', 'P3', 'P4']
Cycle 5 : exécution de P5
File : ['P1', 'P2', 'P3', 'P4', 'P5']
Cycle 6 : exécution de P1
File : ['P2', 'P3', 'P4', 'P5', 'P1']
Cycle 7 : exécution de P2
File : ['P3', 'P4', 'P5', 'P1', 'P2']
Cycle 8 : exécution de P3
File : ['P4', 'P5', 'P1', 'P2', 'P3']
Implémentation Rust : liste chaînée#
L’implémentation d’une liste chaînée en Rust est un exercice classique sur la gestion de la propriété (ownership) et les types récursifs. Le type Box<T> (pointeur alloué sur le tas) et Option<Box<Node<T>>> permettent d’exprimer la structure de façon sûre.
/// Nœud d'une liste chaînée simple.
/// Option<Box<Noeud<T>>> représente : soit None (fin de liste),
/// soit un pointeur vers le nœud suivant alloué sur le tas.
#[derive(Debug)]
struct Noeud<T> {
valeur: T,
suivant: Option<Box<Noeud<T>>>,
}
/// Liste chaînée simple.
#[derive(Debug)]
struct ListeChainee<T> {
tete: Option<Box<Noeud<T>>>,
taille: usize,
}
impl<T: std::fmt::Display + PartialEq> ListeChainee<T> {
fn new() -> Self {
ListeChainee { tete: None, taille: 0 }
}
/// Insère en tête. O(1).
fn inserer_en_tete(&mut self, valeur: T) {
let nouveau = Box::new(Noeud {
valeur,
suivant: self.tete.take(),
});
self.tete = Some(nouveau);
self.taille += 1;
}
/// Supprime et retourne la valeur en tête. O(1).
fn supprimer_tete(&mut self) -> Option<T> {
self.tete.take().map(|noeud| {
self.tete = noeud.suivant;
self.taille -= 1;
noeud.valeur
})
}
/// Recherche par valeur. O(n).
fn contient(&self, valeur: &T) -> bool {
let mut courant = &self.tete;
while let Some(noeud) = courant {
if &noeud.valeur == valeur {
return true;
}
courant = &noeud.suivant;
}
false
}
/// Affiche la liste.
fn afficher(&self) {
let mut courant = &self.tete;
while let Some(noeud) = courant {
print!("{} → ", noeud.valeur);
courant = &noeud.suivant;
}
println!("None");
}
}
fn main() {
let mut liste: ListeChainee<i32> = ListeChainee::new();
for val in [5, 3, 8, 1, 9] {
liste.inserer_en_tete(val);
}
print!("Liste : ");
liste.afficher();
println!("Taille : {}", liste.taille);
println!("Contient 8 : {}", liste.contient(&8));
println!("Contient 42 : {}", liste.contient(&42));
println!("Suppression : {:?}", liste.supprimer_tete());
print!("Liste après suppression : ");
liste.afficher();
}
Remarque 12
En Rust, la définition naïve struct Noeud { suivant: Noeud } est rejetée par le compilateur car elle aurait une taille infinie (un Noeud contient un Noeud qui contient un Noeud…). L’utilisation de Box<Noeud> résout ce problème : Box<T> est un pointeur de taille fixe (8 octets sur une architecture 64 bits) qui pointe vers un T alloué sur le tas. Option<Box<Noeud>> représente soit l’absence de successeur (None), soit un successeur existant (Some(Box::new(...))). Cette combinaison est le pattern idiomatique Rust pour les structures récursives.
collections.deque : la liste doublement chaînée de blocs#
Python fournit dans la bibliothèque standard collections.deque (prononcé « deck »), une structure de données hautement optimisée qui combine les avantages du tableau et de la liste doublement chaînée.
Définition 33 (Deque de blocs)
La collections.deque de Python est implémentée non pas comme une liste doublement chaînée de nœuds individuels, mais comme une liste doublement chaînée de blocs (doubly linked list of blocks). Chaque bloc est un tableau de taille fixe (typiquement 64 éléments). Cette structure, parfois appelée deque ou tableau de tableaux chaîné, offre :
Insertion/suppression en tête ou en queue : \(O(1)\) dans tous les cas.
Accès par indice : \(O(1)\) (grâce à l’arithmétique sur les blocs).
Meilleure localité de cache qu’une liste chaînée pure.
from collections import deque
import timeit
# Comparaison list vs deque pour les opérations en début de séquence
n = 100_000
# Insertion en début
t_list_insert = timeit.timeit(
stmt='L.insert(0, 0)',
setup=f'L = list(range({n}))',
number=1000
) / 1000
t_deque_appendleft = timeit.timeit(
stmt='D.appendleft(0)',
setup=f'from collections import deque; D = deque(range({n}))',
number=1000
) / 1000
# Suppression en début
t_list_pop = timeit.timeit(
stmt='L.pop(0)',
setup=f'L = list(range({n}))',
number=1000
) / 1000
t_deque_popleft = timeit.timeit(
stmt='D.popleft()',
setup=f'from collections import deque; D = deque(range({n}))',
number=1000
) / 1000
print(f"Comparaison list vs deque pour n = {n:,}\n")
print(f"{'Opération':<30} {'list (ms)':>12} {'deque (ms)':>12} {'Rapport':>10}")
print("-" * 66)
print(f"{'insert(0, x)':<30} {t_list_insert*1000:>12.3f} {t_deque_appendleft*1000:>12.3f} {t_list_insert/t_deque_appendleft:>10.1f}x")
print(f"{'pop(0) / popleft()':<30} {t_list_pop*1000:>12.3f} {t_deque_popleft*1000:>12.3f} {t_list_pop/t_deque_popleft:>10.1f}x")
# Démonstration des opérations de deque
d = deque([1, 2, 3, 4, 5], maxlen=8)
print(f"\ndeque initiale : {d}")
d.appendleft(0)
print(f"appendleft(0) : {d}")
d.append(6)
print(f"append(6) : {d}")
d.rotate(2)
print(f"rotate(2) : {d}")
d.rotate(-3)
print(f"rotate(-3) : {d}")
Comparaison list vs deque pour n = 100,000
Opération list (ms) deque (ms) Rapport
------------------------------------------------------------------
insert(0, x) 0.041 0.000 845.1x
pop(0) / popleft() 0.034 0.000 511.5x
deque initiale : deque([1, 2, 3, 4, 5], maxlen=8)
appendleft(0) : deque([0, 1, 2, 3, 4, 5], maxlen=8)
append(6) : deque([0, 1, 2, 3, 4, 5, 6], maxlen=8)
rotate(2) : deque([5, 6, 0, 1, 2, 3, 4], maxlen=8)
rotate(-3) : deque([1, 2, 3, 4, 5, 6, 0], maxlen=8)
Visualisation comparative#
Résumé#
Dans ce chapitre, nous avons étudié les deux structures de données linéaires fondamentales :
Le tableau (array) stocke ses éléments de façon contiguë en mémoire. L’accès par indice est \(O(1)\) grâce au calcul direct d’adresse. En revanche, les insertions et suppressions en milieu de tableau coûtent \(O(n)\) car elles nécessitent de décaler les éléments.
La
listPython est un tableau dynamique : elle se redimensionne automatiquement avec un facteur de croissance proche de 2. L’opérationappendest \(O(1)\) en temps amorti grâce à l’analyse du coût total des redimensionnements.La liste chaînée simple enchaîne des nœuds par des pointeurs. L’insertion en tête est \(O(1)\), mais l’accès par indice est \(O(n)\) car il faut parcourir la chaîne depuis la tête. La mémoire est fragmentée, ce qui nuit à la localité de cache.
La liste doublement chaînée ajoute un pointeur vers le prédécesseur, permettant la suppression en \(O(1)\) d’un nœud connu et le parcours dans les deux sens.
La liste circulaire connecte le dernier nœud au premier, ce qui est naturel pour les applications en tourniquet (round-robin, buffers).
collections.dequeimplémente une liste doublement chaînée de blocs : elle offre des insertions/suppressions \(O(1)\) aux deux extrémités et un accès par indice \(O(1)\), surpassant lalistpour les opérations en tête.En Rust, la liste chaînée s’implémente avec
Option<Box<Node<T>>>:Box<T>alloue sur le tas et casse la récursivité infinie du type, tandis queOptionreprésente l’éventuelle absence de nœud suivant.
Dans le chapitre suivant, nous construirons sur ces fondations pour étudier les piles et les files — des structures de données linéaires à accès restreint qui sont au cœur de nombreux algorithmes fondamentaux.