Structure de données : Tableau

24/01/2018 | Tags: structures de données

Il existe 2 types de tableaux, les tableaux de valeurs et les tableaux de références. Ce sont des structures de données simples et omniprésentes dans les langages de programmation. Un tableau de valeur contient des éléments d’un même type. Un tableau de valeur contient des pointeurs vers de éléments de type et de taille différente.

Liste chainée

Représentation de la mémoire des tableaux. Source: StackOverflow

Il s’agit de blocs de mémoire contigus alloués au stockage de plusieurs éléments. Un tableau contient un nombre défini de “cases” où chaque case fait la même taille (définie par le type des éléments). Quand on initialise un tableau, on alloue entièrement la mémoire. Un tableau vide fait donc la même taille qu’un tableau plein; attention à bien définir sa taille !

Il est possible d’accèder à n’importe quelle position du tableau en O(1) pour la lecture et l’écriture. Il est possible de mettre des tableaux dans des tableaux pour obtenir des matrices ou tableaux N-dimensionnels.

Avantages:

  • Accès aléatoire en écriture: O(1)
  • Accès aléatoire en lecture: O(1)

Inconvénients:

  • Plus gourmand en taille que la liste chainée
  • Un tableau vide pèse autant que s’il était plein
  • Chaque “case” fait la même taille