Dans une reprĂ©sentation contiguĂ« d'une liste, la manipulation de l'Ă©lĂ©ment en tĂȘte est trĂšs
coûteuse (O(n)) car elle provoque un décalage de tous les éléments de la liste. Il est
possible d'éviter cela, en gérant la liste contiguë de façon circulaire.
Dâune maniĂšre gĂ©nĂ©rale pour pouvoir gĂ©rer les listes circulaires il faut utiliser deux
indices :
tĂȘte= indice du premier Ă©lĂ©ment du tableau elements
queue = indice de lâemplacement aprĂšs le dernier Ă©lĂ©ment de la liste
Exemple :
tĂȘte=1 queue=5
5 20 4 9
queue=0 tĂȘte=3
5 20 4 9
queue=1 tĂȘte=4
9 5 20 4
Remarques
Dans les listes circulaires la premiĂšre case du tableau est utilisĂ©e (donc on nâa pas
une correspondance entre indice et position cad la position est toujours en décalage
de 1 par rapport Ă lâindice)
Si la liste est vide alors tĂȘte=0 et queue=0
Les indices de tĂȘte et de queue sont incrĂ©mentĂ©s ou dĂ©crĂ©mentĂ©s de 1 Ă chaque
ajout ou suppression
Lâindice de tĂȘte ne prĂ©cĂšde pas forcĂ©ment lâindice de queue
Dans une liste non circulaire les positions et les indices sont égaux (ajouter un élément à la
position 4 cad lâaffecter Ă elements[4]), par ailleurs L->lg correspond toujours Ă la position du
dernier élément de la liste L.
Ceci nâest pas le cas dans les listes circulaires oĂč il faut faire une correspondance entre les
indices et les positions. En effet, lg et pos nâont pas de signification en tant quâindice : Pour
trouver leurs vrais indices il faut les lier Ă la tĂȘte ou Ă la queue. Par exemple la boucle de
décalage pour les listes non circulaires :