Liste

Historique

Le concept de chaînage apparaît très tôt, entre autres dans la conception d'une table de hachage par Peter Luhn en 1953.

Mais l'implémentation d'une liste chaînée est souvent attribué à Alan Newell, Cliff Shaw, et Herbert Simon, en 1955, qui l'utilisaient dans leur langage IPL (Information Processing Language) pour développer, à la corporation RAND, une machine logique théorique qui devait dériver un nombre indéterminé de théorèmes.

La liste chaînée a par la suite été très utilisée dans le langage LISP, de John McCarthy, en 1958, qui a servi au développement des balbutiements de l’intelligence artificielle.

Description

La liste (list) a un usage libre.

• Type : Libre
• Accès : Position et Itérateur
• Fonctionnalités : Ajouter (append), Insérer (insert) et Retirer (remove)

Implémentations

Statique

Une liste statique a une capacité fixe en mémoire centrale, et consiste en un tableau.

Dynamique

L'implémentation dynamique permet d'utiliser une liste dont la capacité est dynamique en mémoire centrale.

Ajouter

Insérer

Retirer

Itérateur

Un itérateur permet de parcourir efficacement une structure de données, sans affecter sa robustesse.