Liste (informatique)


Liste (informatique)
Cet article concerne l'utilisation du mot liste en informatique, pour une définition plus générale du mot liste, voir le Wiktionnaire.

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).

La liste est à la base de structures de données plus complexes comme la pile, la file, les arbres, etc. L'importance de la liste comme structure de données est telle qu'elle est à la base du langage de programmation LISP (de l'anglais List Processing).

Sommaire

Primitives

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

Primitives de base :

  • « Insérer » : ajoute un élément dans la liste. Terme anglais correspondant : « Add ».
  • « Retirer » : retire un élément de la liste. Terme anglais correspondant : « Remove ».
  • « La liste est-elle vide ? » : renvoie « vrai » si la liste est vide, « faux » sinon. Terme anglais correspondant : « Isnil ».
  • « Nombre d'éléments dans la liste » : renvoie le nombre d'éléments dans la liste. Terme anglais correspondant : « Length ».

Primitives auxiliaires fréquemment rencontrées :

  • « Premier » : retourne le premier élément dans la liste. Terme anglais correspondant : « First ».
  • « Dernier » : retourne le dernier élément dans la liste. Terme anglais correspondant : « Last ».
  • « Prochain » : retourne le prochain élément dans la liste. Terme anglais correspondant : « Next ».
  • « Précédent » : retourne l'élément qui précède dans la liste. Terme anglais correspondant : « Previous ».
  • « Cherche » : cherche si un élément précis est contenu dans la liste et retourne sa position. Terme anglais correspondant : « Find ».

Types de liste

Une liste est un conteneur d'éléments, où chaque élément contient la donnée, ainsi que d'autres informations permettant la récupération des données au sein de la liste. La nature (les types) de ces informations caractérise un type différent de liste.

On peut distinguer, de manière générale, deux types de liste :

  • les tableaux,
  • les listes chaînées.

Tableau

Article détaillé : Tableau (structure de données).
Un tableau à une dimension, composé de 7 éléments.

L'accès à un élément se fait à l'aide d'un index qui représente l'emplacement de l'élément dans la structure.

Les données présentes dans un tableau sont contiguës en mémoire. Cela induit une taille de tableau fixe, c'est-à-dire ne changeant pas. Cependant certains langages de haut niveau fournissent des tableaux qui modifient leur taille en fonction de leur utilisation, on parle alors de tableau à taille dynamique. Mais leur implémentation utilise le principe des listes chaînées (voir plus bas).

Les tableaux peuvent également avoir plusieurs dimensions, représentées par une séquence d'indices. Dans ce cas, si n est la dimension du tableau (où n est un entier naturel non nul), les éléments du tableau de dimension 1 (le 1er indice de la séquence) pointent chacun vers un autre (sous-)tableau de dimension n-1.

Liste chaînée

Article détaillé : Liste chaînée.
Une liste simplement chaînée, composée de trois éléments ayant respectivement la valeur : 12, 99 et 37.

Contrairement à un tableau, la taille d'une liste chaînée n'a pas de limite autre que celle de la mémoire disponible. Cette limitation est franchie par le fait que chaque élément peut pointer, suivant le type de liste chaînée, vers un ou plusieurs éléments de la liste en utilisant une définition récursive. Ainsi, pour augmenter la taille d'une liste chaînée, il suffit de créer un nouvel élément et de faire pointer certains éléments, déjà présents au sein de la liste, vers le nouvel élément.

Il existe deux grands types de liste chaînée :

  • les listes simplement chaînées : chaque élément dispose d'un pointeur sur l'élément suivant (ou successeur) de la liste. Le parcours se fait dans un seul sens ;
  • les listes doublement chaînées : chaque élément dispose de deux pointeurs, respectivement sur l'élément suivant (ou successeur) et sur l'élément précédent (ou prédécesseur). Le parcours peut alors se faire dans deux sens, mutuellement opposés : de successeur en successeur, ou de prédécesseur en prédécesseur.

À cela on peut ajouter une propriété : le cycle. Cette fois-ci la liste chaînée forme une boucle. Dès qu'on atteint la "fin" de la liste et qu'on désire continuer, on se retrouve sur le "premier" élément de la liste. Dans ce cas, la notion de début ou de fin de chaîne n'a plus de raison d'être.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Liste (informatique) de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Informatique Théorique — L informatique théorique est l étude des fondements logiques et mathématiques de l informatique. Plus généralement, le terme est utilisé pour désigner des domaines ou sous domaines de recherche centrés sur des vérités universelles (axiomes) en… …   Wikipédia en Français

  • Informatique theorique — Informatique théorique L informatique théorique est l étude des fondements logiques et mathématiques de l informatique. Plus généralement, le terme est utilisé pour désigner des domaines ou sous domaines de recherche centrés sur des vérités… …   Wikipédia en Français

  • liste — ● 1. n. f. ►TYPE Structure de données classique, analogue à un tableau, mais en plus souple. Une liste se compose d un premier élément appelé tête , et d une liste formée du reste de ses éléments appelée queue . La liste est dite chaînée quand… …   Dictionnaire d'informatique francophone

  • liste de diffusion — ● 1. loc. f. ►MAIL Liste des adresses des personnes à qui sera envoyé un mailing. ● 2. loc. f. ►MAIL Méthode de diffusion d informations, dans laquelle les abonnés de la liste peuvent envoyer des messages qui seront diffusés aux autres (avec ou… …   Dictionnaire d'informatique francophone

  • liste déroulante — ● loc. f. ►WIDGET widget présentant une liste dans laquelle l utilisateur peut choisir un élément, à la manière d un menu déroulant. Version anglaise: list box. Voir aussi combo box. Exemple intelligent de liste déroulante …   Dictionnaire d'informatique francophone

  • Informatique théorique — L informatique théorique est l étude des fondements logiques et mathématiques de l informatique. Plus généralement, le terme est utilisé pour désigner des domaines ou sous domaines de recherche centrés sur des vérités universelles (axiomes) en… …   Wikipédia en Français

  • Liste Des Écoles D'ingénieurs En France — Article principal : Études d ingénieurs en France. Cet article présente la liste des écoles d ingénieurs en France triée par ville, habilitées en 2009[1]. En construction : Liste des écoles d ingénieurs en France trié par domaine d… …   Wikipédia en Français

  • Liste des ecoles d'ingenieurs en France — Liste des écoles d ingénieurs en France Article principal : Études d ingénieurs en France. Cet article présente la liste des écoles d ingénieurs en France triée par ville, habilitées en 2009[1]. En construction : Liste des écoles d… …   Wikipédia en Français

  • Liste des écoles d'ingénieurs en france — Article principal : Études d ingénieurs en France. Cet article présente la liste des écoles d ingénieurs en France triée par ville, habilitées en 2009[1]. En construction : Liste des écoles d ingénieurs en France trié par domaine d… …   Wikipédia en Français

  • Liste Des Écoles D'informatique — Cet article contient une liste des articles sur les écoles, universités, instituts de formation ou de recherche etc., qu ils soient privés ou publics, spécialisés en informatique ou comprenant un département informatique. Sommaire : Haut A B …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.