Collection (type de données abstrait) - Collection (abstract data type)

En informatique , une collection est un regroupement d'un nombre variable d'éléments de données (éventuellement zéro) qui ont une signification commune pour le problème à résoudre et doivent être exploités ensemble de manière contrôlée. Généralement, les éléments de données seront du même type ou, dans les langages prenant en charge l'héritage, dérivés d'un type d'ancêtre commun. Une collection est un concept applicable aux types de données abstraits et ne prescrit pas une implémentation spécifique en tant que structure de données concrète , bien qu'il existe souvent un choix conventionnel (voir Conteneur pour une discussion sur la théorie des types ).

Des exemples de collections incluent des listes , des ensembles , des ensembles multiples , des arbres et des graphiques .

Les tableaux (ou tableaux) de taille fixe ne sont généralement pas considérés comme une collection car ils contiennent un nombre fixe d'éléments de données, bien qu'ils jouent généralement un rôle dans la mise en œuvre des collections. Les tableaux de taille variable sont généralement considérés comme des collections.

Collections linéaires

De nombreuses collections définissent un ordre linéaire particulier, avec accès à une ou aux deux extrémités. La structure de données réelle implémentant une telle collection n'a pas besoin d'être linéaire - par exemple, une file d'attente prioritaire est souvent implémentée comme un tas , qui est une sorte d'arbre. Les collections linéaires importantes comprennent :

• listes ;
• piles ;
• files d'attente ;
• files d'attente prioritaires ;
• files d'attente doubles ;
• files d'attente prioritaires à deux extrémités .

Listes

Dans une liste, l'ordre des éléments de données est significatif. Les éléments de données en double sont autorisés. Des exemples d'opérations sur les listes sont la recherche d'un élément de données dans la liste et la détermination de son emplacement (s'il est présent), la suppression d'un élément de données de la liste, l'ajout d'un élément de données à la liste à un emplacement spécifique, etc. Si le principal les opérations sur la liste doivent être l'ajout d'éléments de données à une extrémité et la suppression d'éléments de données à l'autre, elle sera généralement appelée file d'attente ou FIFO . Si les opérations principales sont l'ajout et la suppression d'éléments de données à une seule extrémité, cela s'appellera une pile ou LIFO . Dans les deux cas, les éléments de données sont conservés dans la collection dans le même ordre (à moins qu'ils ne soient supprimés et réinsérés ailleurs) et il s'agit donc de cas particuliers de la collection de listes. D'autres opérations spécialisées sur les listes incluent le tri, où, encore une fois, l'ordre des éléments de données est d'une grande importance.

Piles

Une pile est une structure de données LIFO avec deux opérations principales : push , qui ajoute un élément au "top" de la collection, et pop , qui supprime l'élément top.

Files d'attente

Files d'attente prioritaires

Dans une file d'attente prioritaire, les pistes de l'élément de données minimum ou maximum dans la collection sont conservées, selon un certain critère d'ordre, et l'ordre des autres éléments de données n'a pas d'importance. On peut considérer une file d'attente prioritaire comme une liste qui garde toujours le minimum ou le maximum en tête, tandis que les éléments restants sont conservés dans un sac.

Files d'attente doubles

Files d'attente prioritaires à deux extrémités

Collections associatives

D'autres collections peuvent à la place être interprétées comme une sorte de fonction : étant donné une entrée, la collection donne une sortie. Les collections associatives importantes comprennent :

• ensembles ;
• multi-ensembles ;
• tableaux associatifs .

Un ensemble peut être interprété comme un multi-ensemble spécialisé, qui à son tour est un tableau associatif spécialisé, dans chaque cas en limitant les valeurs possibles, en considérant un ensemble tel que représenté par sa fonction indicatrice .

Ensembles

Dans un ensemble, l'ordre des éléments de données n'a pas d'importance (ou n'est pas défini) mais les éléments de données en double ne sont pas autorisés. Des exemples d'opérations sur des ensembles sont l'ajout et la suppression d'éléments de données et la recherche d'un élément de données dans l'ensemble. Certaines langues prennent en charge les ensembles directement. Dans d'autres, les ensembles peuvent être implémentés par une table de hachage avec des valeurs factices ; seules les clés sont utilisées pour représenter l'ensemble.

Multisets

Dans un multi-ensemble (ou un sac), comme dans un ensemble, l'ordre des éléments de données n'a pas d'importance, mais dans ce cas, les éléments de données en double sont autorisés. Des exemples d'opérations sur des multi-ensembles sont l'ajout et la suppression d'éléments de données et la détermination du nombre de doublons d'un élément de données particulier sont présents dans le multi-ensemble. Les multi-ensembles peuvent être transformés en listes par l'action de tri.

Tableaux associatifs

Dans un tableau associatif (ou carte, dictionnaire, table de correspondance), comme dans un dictionnaire, une recherche sur une clé (comme un mot) fournit une valeur (comme une définition). La valeur peut être une référence à une structure de données composée. Une table de hachage est généralement une implémentation efficace, et donc ce type de données est souvent appelé « hachage ».

Graphiques

Dans un graphique, les éléments de données ont des associations avec un ou plusieurs autres éléments de données de la collection et sont un peu comme des arbres sans le concept de racine ou de relation parent-enfant, de sorte que tous les éléments de données sont des pairs. Des exemples d'opérations sur les graphes sont les parcours et les recherches qui explorent les associations d'éléments de données à la recherche d'une propriété spécifique. Les graphiques sont fréquemment utilisés pour modéliser des situations du monde réel et pour résoudre des problèmes connexes. Un exemple est le protocole Spanning Tree , qui crée une représentation graphique (ou maillée) d'un réseau de données et détermine quelles associations entre les nœuds de commutation doivent être rompues pour le transformer en un arbre et ainsi empêcher les données de circuler en boucle.

Des arbres

Dans un arbre, qui est un type particulier de graphique, un élément de données racine est associé à un certain nombre d'éléments de données qui à leur tour leur sont associés un certain nombre d'autres éléments de données dans ce qui est souvent considéré comme une relation parent-enfant . Chaque élément de données (autre que la racine) a un seul parent (la racine n'a pas de parent) et un certain nombre d'enfants, éventuellement zéro. Des exemples d'opérations sur les arbres sont l'ajout d'éléments de données afin de maintenir une propriété spécifique de l'arbre pour effectuer un tri, etc. et des parcours pour visiter des éléments de données dans une séquence spécifique.

Les collections d'arbres peuvent être utilisées pour stocker naturellement des données hiérarchiques, qui sont présentées de manière arborescente, telles que des systèmes de menus et des fichiers dans des répertoires sur un système de stockage de données.

Des arbres spécialisés sont utilisés dans divers algorithmes. Par exemple, le tri par tas utilise une sorte d'arborescence appelée tas .

Concept abstrait vs mise en œuvre

Comme décrit ici, une collection et les différents types de collections sont des concepts abstraits. Il existe dans la littérature une confusion considérable entre les concepts abstraits de l'informatique et leurs implémentations spécifiques dans divers langages ou types de langages. Les affirmations selon lesquelles les collections telles que les listes, les ensembles, les arbres, etc. sont des structures de données, des types de données abstraits ou des classes doivent être lues dans cet esprit. Les collections sont avant tout des abstractions utiles pour formuler des solutions à des problèmes informatiques. Vus sous cet angle, ils conservent des liens importants avec des concepts mathématiques sous-jacents qui peuvent être perdus lorsque l'accent est mis sur la mise en œuvre.

Par exemple, une file d'attente prioritaire est souvent implémentée comme un tas, tandis qu'un tableau associatif est souvent implémenté comme une table de hachage, donc ces types abstraits sont souvent désignés par cette implémentation préférée, comme un « tas » ou un « hachage », bien que ce n'est pas strictement correct.

Implémentations

Certaines collections peuvent être des types de données primitifs dans un langage, comme des listes, tandis que des collections plus complexes sont implémentées en tant que types de données composites dans des bibliothèques, parfois dans la bibliothèque standard . Les exemples comprennent:

• C++ : connu sous le nom de « conteneurs », implémenté dans la bibliothèque standard C++ et les anciennes bibliothèques de modèles standard
• Java : implémenté dans le framework de collections Java
• Oracle PL/SQL implémente les collections en tant que types définis par le programmeur
• Python : certains intégrés, d'autres implémentés dans la bibliothèque des collections

Les références

Liens externes

• Collections Apache Commons .
• AS3Commons Collections Framework Mise en œuvre ActionScript3 des collections les plus courantes.
• CollectionSpy — Un profileur pour le cadre de collections de Java.
• Goyave .
• Bibliothèque Java Mango .