Une liste dans un tableau fixe
Une liste est une suite ordonnée. Une pile et une file imposent en plus une règle sur l'ordre des sorties. Le contrat ne choisit toujours pas le rangement : tableau, nœuds et buffer circulaire peuvent chacun porter une partie de ces comportements.
Commençons par un tableau de quatre cases. La taille compte les valeurs utiles. La capacité compte les cases réservées.
La case d'index 3 existe déjà, mais elle n'appartient pas encore à la liste. get(3) doit donc être refusé. La capacité décrit la mémoire disponible, pas les index logiques autorisés.
Grandir sans changer le contrat
Un tableau dynamique garde le même accès par index, mais remplace son bloc quand la capacité manque. Dans cet exemple pédagogique, la nouvelle capacité est le double de l'ancienne.
Avant la croissance
Ancien bloc à @256. Il devient un bloc fantôme pendant la copie.
Après la croissance
Nouveau bloc à @512. Il n'est pas une extension du bloc @256.
Allouer ailleurs
Quandsize == values.length, un nouveau tableau deux fois plus grand est créé à un autre endroit.Copier les valeurs
Chaque valeur logique est lue dans l'ancien bloc puis écrite dans le nouveau.Changer la référence
Le champvaluesdésigne le nouveau bloc. L'ancien bloc n'est plus utilisé.Effectuer l'ajout
La nouvelle valeur est écrite à l'ancienne position desize, puis la taille augmente.
Pour un appel isolé, add sur un tableau plein demande même plus de travail que remove(0) : il faut allouer, copier toutes les valeurs, puis écrire la nouvelle. La différence apparaît dans la répétition. En doublant la capacité, la croissance ne revient qu'occasionnellement, tandis que remove(0)décale les valeurs à chaque appel.
La croissance ne corrige pas les décalages
Rendre de la mémoire sans s'agiter
Après beaucoup de retraits, la taille peut devenir bien plus petite que la capacité. Java garde cette marge. Un ArrayList ne rend pas sa mémoire tout seul.
trimToSize() ne raccourcit pas le bloc en place. Il crée un bloc d'exactement size cases, copie les valeurs et remplace la référence. Rendre la marge a donc un prix immédiat.
Le piège du seuil naïf
Hystérésis
- • La croissance et le shrink utilisent des seuils séparés.
- • Une marge reste après le shrink.
- • Une petite oscillation de size ne recopie pas tout.
Même frontière
- • Le bloc réduit est immédiatement plein.
- • Un add puis un remove alternent croissance et shrink.
- • Chaque petite opération déclenche une grande copie.
Le choix de Java
trimToSize() seulement lorsque vous avez une vraie raison de rendre la marge.Remplacer les cases par des liens
Une liste chaînée remplace le grand bloc par des nœuds. Chaque nœud garde une valeur et la référence next. La liste conserve head, tail et size.
Ajouter à la fin
Lire l'index i
head et suit i références.Curseur et double chaînage
Une insertion liée est locale seulement si vous connaissez déjà le bon nœud. Si vous partez de head pour le chercher, le parcours reste à payer.
Parcourir une fois
Un curseur garde la position actuelle et les références utiles autour d'elle.Modifier localement
Une insertion près du curseur change quelques liens, sans repartir de head.Continuer depuis cette position
En Java,ListIteratorformalise ce principe. Il ne transforme pas la liste en accès direct par index.
Le double chaînage ajoute previous. Vous pouvez alors avancer et reculer localement. En échange, chaque nœud prend une référence de plus et chaque modification doit maintenir les deux sens.
Le curseur aide
- • Vous êtes déjà positionné au bon endroit.
- • Vous enchaînez plusieurs modifications voisines.
- • Vous devez avancer et reculer localement.
Le curseur n'aide pas
- • Vous demandez sans cesse un index arbitraire.
- • Vous recréez le curseur depuis head à chaque opération.
- • Vous oubliez de mettre à jour previous ou next.
La pile travaille du même côté
Une pile respecte LIFO. Le cours utilise put, take et peek. Les noms standards push et pop décrivent les mêmes gestes.
Pourquoi le tableau convient
- Toutes les opérations portent sur la fin logique.
- Aucun voisin ne doit combler un trou.
Ce que la pile interdit
- Retirer arbitrairement au milieu.
- Consulter une position quelconque par son contrat.
Ce que gagne le client
- Une règle LIFO impossible à contourner.
- Un cas vide traité explicitement.
Trois façons de construire une file
Une file respecte FIFO. On ajoute derrière et on retire devant. Les trois implémentations suivantes donnent le même ordre logique, mais pas les mêmes gestes en mémoire.
ArrayList
- put ajoute simplement à la fin.
- Les valeurs restent dans un bloc compact.
Le retrait en tête
- take appelle remove(0).
- Toutes les valeurs restantes se décalent.
La file sur ArrayList n'est pas fausse. Elle retourne les valeurs dans le bon ordre. Son défaut est le travail caché de remove(0).
Deux extrémités, deux responsabilités
head est le prochain élément à sortir. tail reçoit le prochain élément. Ajouter et retirer changent quelques références, sans déplacer les autres valeurs.Faire tourner les indices
Le buffer circulaire conserve le tableau compact sans fermer le trou après chaque retrait. head avance vers le plus ancien élément et tail vers la prochaine case d'écriture. Arrivés au bout, les deux reviennent à l'index 0.
L'ordre physique est 50, 20, 30, 40. Depuis head, l'ordre FIFO est 20, 30, 40, 50. head et tail sont égaux parce que la file est pleine.
Écrire à tail
putplace la valeur danselements[tail], puis avance tail avec le modulo.Lire à head
takeconserve la valeur deelements[head], puis avance head. Aucune autre case ne bouge.Traduire un index logique
L'index logique i se trouve à la position physique(head + i) % elements.length.Distinguer vide et plein
Quand head égale tail,sizeindique s'il reste zéro valeur ou si toutes les cases sont occupées.
Quatre invariants à vérifier
0 ≤ size ≤ elements.lengthheaddésigne le prochain élément à sortir.taildésigne la prochaine case d'écriture.- Chaque avance reboucle avec le modulo.
Choisir selon les opérations
Il n'existe pas de gagnant absolu. Partez de l'opération qui revient souvent, puis regardez le geste réel.
| Représentation | Accès par index | Ajout et retrait utiles | Mémoire et piège |
|---|---|---|---|
| Tableau dynamique | 1 accès | Fin : une écriture le plus souvent. Début : décalages. | Bloc compact avec capacité libre; copie rare lors d'une croissance. |
| Liste simplement chaînée | i + 1 nœuds lus | Tête locale; fin locale si tail existe. | Une allocation et une référence par valeur; recherche préalable souvent oubliée. |
| Liste doublement chaînée | Suit toujours les liens. | Modification locale dans les deux sens avec un curseur. | Deux références par nœud et plus de liens à maintenir. |
| Buffer circulaire | 1 calcul + 1 accès | put à tail et take à head, sans décalage. | Capacité bornée; modulo et distinction vide/plein indispensables. |
Questions utiles
- • Avez-vous besoin d'un index arbitraire ?
- • Modifiez-vous surtout au début, à la fin ou près d'un curseur ?
- • La capacité peut-elle être bornée ?
- • Quel cas vide ou plein devez-vous garantir ?
Mauvais raccourcis
- • « LinkedList est toujours meilleure pour insérer. »
- • « ArrayList grandit, donc remove(0) ne coûte rien. »
- • « head égale tail signifie forcément vide. »
- • « Une valeur encore visible dans une case reste logique. »
Vérifiez vos réflexes
Vérifiez vos réflexes
Une réponse par question. La correction apparaît tout de suite.
Écrivez une file circulaire
Implémentez CircularQueue
Écrivez d'abord. Une IA externe pourra ensuite relire votre travail. Son retour peut être faux. Vérifiez-le avec la leçon.
Brouillon enregistré sur cet appareil.
Voir le prompt qui sera copié
Vous corrigez le travail d'un étudiant qui prépare une remédiation Java 17. Évaluez d'abord son raisonnement, ses invariants et la cohérence de son brouillon. Un code incomplet mais bien expliqué mérite un retour utile. Signalez précisément les erreurs sans inventer d'exigences hors sujet. Cette leçon évalue une file circulaire bornée. Vérifiez le rôle exact de head, tail et size, le modulo, les cas vide et plein, et l'absence de décalage. Ne remplacez pas le tableau par une collection Java. Travail demandé: Implémentez une CircularQueue avec : - un int[] elements, head, tail et size; - un constructeur qui reçoit la capacité; - put, take, peek et isEmpty; - IllegalStateException si put est appelé sur une file pleine, ou take/peek sur une file vide; - aucun décalage et aucune collection Java. Tracez ensuite cette suite pour une capacité de 4 : put(10), put(20), put(30), take(), put(40), put(50). Donnez la valeur retirée, l'ordre logique final, puis head, tail et size. Expliquez en une phrase pourquoi head et tail ont alors la même valeur. Commencez par poser au plus deux questions si une intention reste ambiguë. Donnez ensuite les points corrects, les problèmes précis et la plus petite prochaine étape. Ne fournissez une solution complète que si l'étudiant la demande explicitement. Réponse de l'étudiant: [aucune réponse collée]
Continuez le parcours
Les tableaux et les liens réapparaissent dans presque toutes les structures suivantes. La map les combine avec une fonction de hash. L'annexe sur les génériques explique le E et le T utilisés dans les contrats.