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 :