Listes simplement chaînées (SLIST)¶

Les listes simplement chaînées sont les plus simples et ne prennent en charge que les fonctionnalités ci-dessus. Elles sont idéales pour les applications avec de grands jeux de données et peu ou pas de suppressions, ou pour mettre en œuvre une pile LIFO. Elles ajoutent la fonctionnalité suivante :

-

O(n) suppression de n'importe quel élément de la liste.

Files d'attente finies simplement chaînées (STAILQ)¶

Les files d'attente finies simplement chaînées ajoutent les fonctionnalités suivantes :

• des éléments peuvent être ajoutés en fin de liste ;
• O(n) suppression de n'importe quel élément de la liste.
• les éléments peuvent être concaténés.

Cependant :

• toutes les insertions doivent indiquer la tête de la liste ;
• chaque élément de tête de liste nécessite deux pointeurs au lieu d'un seul.

Les files d'attente finies simplement chaînées sont idéales pour les applications avec de grands jeux de données et peu ou pas de suppressions, ou pour mettre en œuvre une file FIFO.

Structures de données doublement chaînées¶

De plus, tous les types doublement chaînés de structures de données (listes et files d'attente finies) permettent :

• l’insertion d'un nouvel élément avant n'importe quel élément de la liste ;
• O(1) suppression de n'importe quel élément de la liste.

Cependant :

-

chaque élément nécessite deux pointeurs au lieu d'un seul.

Listes doublement chaînes (LIST)¶

Les listes chaînées sont la forme la plus simple des structures de données doublement chaînées. Elles ajoutent la fonctionnalité suivante à celles ci-dessus :

-

elles peuvent être traversées en arrière.

Cependant :

-

Pour une traversée en arrière, un élément de début de traversée et la liste à laquelle il appartient doivent être indiquées.

Files d'attente finies doublement chaînées (TAILQ)¶

Les files d'attente finies ajoutent les fonctionnalités suivantes :

• des éléments peuvent être ajoutés en fin de liste ;
• elles peuvent être traversées en arrière, de la queue à la tête ;
• les éléments peuvent être concaténés.

Cependant :

• toutes les insertions et suppressions d’élément de liste doivent mentionner la tête de la liste ;
• chaque élément de tête de liste nécessite deux pointeurs au lieu d'un seul.

Files d'attente circulaires doublement chaînées (CIRCLEQ)¶

Les files d'attente circulaires ajoutent la fonctionnalité suivante à celles ci-dessus :

-

le premier et le dernier élément sont connectés.

Cependant :

-

La condition terminale pour la traversée est plus complexe.