dans les deux sens dans la liste, soit vers la queue (fin), soit vers la tête. Ces listes sont dites bilatères.
Les traitements doivent être adaptés en conséquence. Prenez le problème à l’envers : vous avez deux pointeurs à
mettre à jour. Si vous savez le faire dans un sens (comme les listes simples) vous savez le faire dans l’autre, vous
changez juste de sens. Il y a donc deux fois plus d’opérations de chaînage :
Chaînage avant
q pPrec→pSuiv ← pNouveau
q pNouveau→pSuiv ← pSuivant
Chaînage arrière
q pSuivant→pPrec ← pNouveau
q pNouveau→pPrec ← pPrec
Les listes bilatères peuvent aussi être circulaires et/ou triées.
d. Files et piles
Dans une file d’attente, dans un magasin, un cinéma, bref dans une queue, le premier arrivé est le premier servi. En
anglais, cela se traduit par "First In, First Out", soit FIFO en abrégé.
Une file d’attente de type FIFO peut être représentée par une liste chaînée. Chaque nouvel élément est rajouté en
fin de liste, tandis que les éléments sont traités les uns après les autres depuis la tête de la liste.
Quand vous faites la vaisselle, les assiettes sont empilées les unes sur les autres. Quand vous lavez les assiettes
vous prenez celles du dessus en descendant au fur et à mesure. Si des nouvelles assiettes sales sont rajoutées elles
le sont sur le dessus de la pile.
Le principe est le même en informatique quand vous voulez traiter des éléments au fur et à mesure de leur arrivée :
les derniers arrivés sont traités en premier. La pile peut être représentée par une liste chaînée : les nouveaux
éléments sont systématiquement rajoutés en tête de liste et les éléments sont toujours traités depuis cette tête. Si
les éléments arrivent plus vite que leur traitement, ceux arrivés en premier risquent d’être traités bien tard.
- 13 -
© ENI Editions - All rigths reserved - Jonifar lina
186
Les traitements doivent être adaptés en conséquence. Prenez le problème à l’envers : vous avez deux pointeurs à
mettre à jour. Si vous savez le faire dans un sens (comme les listes simples) vous savez le faire dans l’autre, vous
changez juste de sens. Il y a donc deux fois plus d’opérations de chaînage :
Chaînage avant
q pPrec→pSuiv ← pNouveau
q pNouveau→pSuiv ← pSuivant
Chaînage arrière
q pSuivant→pPrec ← pNouveau
q pNouveau→pPrec ← pPrec
Les listes bilatères peuvent aussi être circulaires et/ou triées.
d. Files et piles
Dans une file d’attente, dans un magasin, un cinéma, bref dans une queue, le premier arrivé est le premier servi. En
anglais, cela se traduit par "First In, First Out", soit FIFO en abrégé.
Une file d’attente de type FIFO peut être représentée par une liste chaînée. Chaque nouvel élément est rajouté en
fin de liste, tandis que les éléments sont traités les uns après les autres depuis la tête de la liste.
Quand vous faites la vaisselle, les assiettes sont empilées les unes sur les autres. Quand vous lavez les assiettes
vous prenez celles du dessus en descendant au fur et à mesure. Si des nouvelles assiettes sales sont rajoutées elles
le sont sur le dessus de la pile.
Le principe est le même en informatique quand vous voulez traiter des éléments au fur et à mesure de leur arrivée :
les derniers arrivés sont traités en premier. La pile peut être représentée par une liste chaînée : les nouveaux
éléments sont systématiquement rajoutés en tête de liste et les éléments sont toujours traités depuis cette tête. Si
les éléments arrivent plus vite que leur traitement, ceux arrivés en premier risquent d’être traités bien tard.
- 13 -
© ENI Editions - All rigths reserved - Jonifar lina
186