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 :