Liste chaînée | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Une liste chaînée ou liste liée (en anglais linked list) désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d'éléments de même type, dont la représentation en mémoire de l'ordinateur est une succession de cellules faites d'un contenu et d'un pointeur vers une autre cellule. De façon imagée, l'ensemble des cellules ressemble à une chaîne dont les maillons seraient les cellules. L'accès aux éléments d'une liste se fait de manière séquentielle : chaque élément permet l'accès au suivant (contrairement au tableau dans lequel l'accès se fait de manière directe, par adressage de chaque cellule dudit tableau). Le principe de la liste chaînée est que chaque élément possède, en plus de la donnée, un pointeur vers un élément qui lui est contigu dans la liste. L'usage d'une liste est souvent préconisé pour des raisons de rapidité de traitement, lorsque l'ordre des éléments est important et que les insertions et les suppressions d'éléments quelconques sont plus fréquentes que les accès. En effet, les insertions en début ou fin de liste et les suppressions se font en temps constant car elles ne demandent au maximum que deux écritures. En revanche, l'accès à un élément quelconque nécessite le parcours de la liste depuis le début jusqu'à l'index de l'élément choisi. À l'origine appelée NSS memory, les listes chaînées ont été conçues dans les années 1955-1956, par Allen Newell, Cliff Shaw et Herbert Simon de RAND Corporation. Les listes chaînées étaient la structure de donnée de base de leur langage Information Processing Language (IPL). IPL était utilisé par ses auteurs pour le développement de plusieurs programmes d'intelligence artificielle, comme Logic Theory Machine, General Problem Solver et un jeu d'échecs. Leurs travaux sur les listes chaînées sont publiés dans IRE Transactions on Information Theory en 1956 et plusieurs conférences organisées durant la période 1957 à 1959.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (66)

Cours associés (23)

Séances de cours associées (204)

MOOCs associés (2)

CS-250: Algorithms

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

CS-108: Practice of object-oriented programming

Les étudiants perfectionnent leurs connaissances en Java et les mettent en pratique en réalisant un projet de taille conséquente. Ils apprennent à utiliser et à mettre en œuvre les principaux types de

Liste chaînée

Pointeur (programmation)

En programmation informatique, un pointeur est un objet qui contient l'adresse mémoire d'une donnée ou d'une fonction. C'est l'outil fondamental de l'adressage dit « indirect ». La notion de pointeur reflète l'utilisation différente que l'on peut faire d'un entier naturel, à savoir indiquer une adresse mémoire. Cette utilisation est très différente d'une utilisation arithmétique, d'où la création de registres de processeurs spécifiques (les registres d'adresse) et d'un type de donnée spécifique dans les langages de programmations.

Liste (informatique)

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

Information, Calcul, Communication: Introduction à la pensée informatique

Dans une première partie, nous étudierons d’abord comment résoudre de manière très concrète un problème au moyen d’un algorithme, ce qui nous amènera dans un second temps à une des grandes questions d

Information, Calcul, Communication: Introduction à la pensée informatique

Constructions universelles : Listes liées

Couvre les constructions universelles des objets log en utilisant des listes liées et les défis de la mise en œuvre.

Mise en œuvre des listes à liens singuliers

Couvre l'implémentation de listes liées séparément en Java, en se concentrant sur des concepts tels que les nœuds, la gestion de la taille, l'ajout, la suppression et l'obtention d'éléments.

Polymorphisme et preuves

Couvre le polymorphisme paramétrique, énumère la construction, les tuples, les méthodes génériques, le tri de fusion et les propriétés du programme.