Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Liste

En informatique, une liste est une structure de données permettant de regrouper des données de manière à pouvoir y accéder librement (contrairement aux files et aux piles, dont l'accès se fait respectivement en mode FIFO et LIFO). On utilise dans ce but un index qu'on peut placer sur un élément particulier de la liste. On définie un certain nombre de primitives, qui sont des fonctions que la liste permette de faire efficacement.

Primitives

Voici les primitives communément utilisées pour manipuler des listes. Il n'existe pas de normalisation pour les primitives de manipulation de liste. Leurs noms sont donc indiqués de manière informelle.

• "Placement sur le premier élément" : place l'index sur le premier élément de la liste.
• "Placement sur le dernier élément" : place l'index sur le dernier élément de la liste.
• "Placement sur l'élément suivant" : place l'index sur l'élément qui suit l'élément courant si c'est possible.
• "Placement sur l'élément précédent" : place l'index sur l'élément qui précède l'élément courant si c'est possible.
• "Liste est-elle vide ?" : Retourne vrai si la liste est vide, faux sinon.
• "L'élément courant est-il le premier ?" : Retourne vrai si l'élément courant est le premier élément de la liste, faux sinon.
• "L'élément courant est-il le dernier ?" : Retourne vrai si l'élément courant est le dernier élément de la liste, faux sinon.
• "Nombre d'élément" : renvoie le nombre d'éléments dans la liste.
• "Ajouter en queue" : ajoute un élément après le dernier élément de la liste.
• "Ajouter en tête" : ajoute un élément avant le premier élément de la liste.
• "Insertion" : insère un élément avant l'élément courant.
• "Remplacement" : Remplace l'élément courant.
• "Suppression" : Supprime l'élément courant.

Implémentation

Dans des langages déclaratifs comme le C, l'implémentation des listes utilise l'une des méthodes suivantes :

• Implémentation par contiguité : Les éléments se trouvent dans l'ordre dans une structure de données de plus bas niveau, comme un tableau, par exemple.
• Implémentation par chaînage : Les éléments contiennt les informations (des pointeurs, en C), permettant de retrouver l'élément suivant (chaînage simple) ou les éléments précédent et suivant (chaînage double).