Tableaux, listes et structures de données
Une variable ne contient qu’une seule valeur. Dès qu’un programme manipule des dizaines de notes, des milliers de clients ou la liste des fichiers d’un dossier, il faut des moyens de regrouper les données. Les langages en proposent plusieurs : le tableau, une suite de cases numérotées ; la structure, un petit dossier où chaque champ a un nom et un type ; la liste chaînée, une suite de maillons reliés entre eux par des adresses ; le dictionnaire, qui retrouve une valeur par son nom. Cet article les explique en prenant le langage C comme fil conducteur (il montre ce qui se passe en mémoire), puis montre comment le C++, Python et JavaScript offrent les mêmes idées sous une forme plus sûre. Il compare leurs coûts, pour savoir laquelle choisir. Il couvre le C, le C++ et JavaScript, en corrigeant plusieurs erreurs courantes.
- Rubrique
- Développement
- Niveau
- Débutant à intermédiaire
- Lecture
- 26 min (essentiel)
28 min (complet) - Révision
- 4 novembre 2026
En bref
- Un tableau range des éléments de même type côte à côte ; on accède à l’élément numéro i d’un coup, mais insérer au milieu oblige à décaler tout le reste.
- Une structure regroupe des valeurs de types différents sous un nom ; le compilateur peut y laisser des vides pour aligner les champs, donc l’ordre des champs change la taille.
- Une liste chaînée relie des maillons dispersés par des adresses : insérer est facile, mais atteindre le n-ième maillon oblige à parcourir tous les précédents.
- En C, rien ne vérifie qu’on reste dans les limites d’un tableau : écrire trop loin est une faille de sécurité classique (dépassement de tampon).
- En Python, JavaScript ou C++ moderne, on utilise des tableaux extensibles et des dictionnaires qui cachent ces détails ; le bon choix dépend des opérations les plus fréquentes.
Prérequis conseillés : Variables et types de données · Le langage C
1Pourquoi regrouper des données ?
On part toujours de la même constatation : « les variables ne permettent de stocker qu’une seule donnée à la fois ». Pour une valeur, une variable suffit (voir les variables). Mais imaginez un programme qui calcule la moyenne de trente notes : écrire trente variables note1, note2, et ainsi de suite serait pénible, et impossible si le nombre de notes change d’une exécution à l’autre. On voudrait une « variable commune » qui contienne toutes les notes, et que l’on puisse parcourir avec une boucle.
Les langages offrent pour cela plusieurs structures de données, c’est-à-dire des façons d’organiser plusieurs valeurs en mémoire. On en distingue classiquement deux, communes au C et au C++ : les tableaux, qui rassemblent des données de même type, et les structures, qui rassemblent des données de types différents. On en ajoute une troisième avec les pointeurs : la liste chaînée. Nous y joindrons le dictionnaire, omniprésent aujourd’hui.
1.1Ce qu’il faut savoir avant
La mémoire d’un ordinateur (voir la mémoire vive) est une très longue suite de petites cases de huit bits, appelées octets, chacune repérée par un numéro, son adresse. Une variable occupe une ou plusieurs cases consécutives. Toute la différence entre les structures de données tient à la façon dont elles placent leurs valeurs dans ces cases, et c’est ce qui décide de leur rapidité. Le langage C montre cela sans rien cacher : c’est pourquoi nous l’employons ici (voir le langage C). Les exemples sont donnés sous une forme actuelle ; quand une erreur ou une pratique dépassée est courante, nous le disons.
1.2Le plan de l’article
La partie 2 traite du tableau (figure 1), la partie 3 des tableaux à plusieurs dimensions, la partie 4 de la structure (figure 2), la partie 5 de la liste chaînée (de nouveau figure 1), la partie 6 des autres langages (C++, Python, JavaScript), la partie 7 du choix entre structures (figure 3) et la partie 8 propose sept exercices corrigés.
2Le tableau
On définit ainsi un tableau : « une variable composée de données de même type, stockée de manière contiguë en mémoire (les unes à la suite des autres) ». Contiguë veut dire « sans trou » : les cases se touchent. Un tableau est donc une suite de cases de même taille, dont la taille est celle du type d’élément. C’est cette régularité qui fait sa force : connaissant l’adresse de la première case et la taille d’une case, on calcule l’adresse de n’importe quelle autre par une simple multiplication.
Les éléments d’un tableau peuvent être des types simples (int, char, float, long, double), des pointeurs (des adresses, voir les pointeurs et la mémoire), des structures (partie 4) ou même d’autres tableaux (partie 3). On parle de tableau monodimensionnel (ou vecteur) quand les éléments sont simples.
2.1Déclarer un tableau
En C, on écrit le type des éléments, le nom, puis le nombre d’éléments entre crochets :
char tableau[8]; /* 8 caractères */ int notes[10]; /* 10 entiers */ double mesures[15]; /* 15 nombres décimaux */
Le nom suit les mêmes règles qu’un nom de variable. Le nombre d’éléments est un entier qui, en C classique, doit être connu à la compilation : la taille d’un tableau est « figée dès sa définition ». (Le C99 a ajouté des tableaux dont la taille est calculée à l’exécution, mais leur usage est déconseillé pour de grandes tailles, car ils peuvent faire déborder la mémoire de travail réservée aux variables locales.)
2.2Calculer la taille d’un tableau
La taille en octets est le nombre d’éléments multiplié par la taille d’un élément. On peut la calculer à la main ou demander à l’opérateur sizeof, qui renvoie la taille de ce qu’on lui donne :
int notes[10]; size_t octets = sizeof(notes); /* taille totale */ size_t nombre = sizeof(notes) / sizeof(notes[0]); /* nombre d'éléments : 10 */
Une correction utile. On lit parfois qu’un int occupe 2 octets, soit 20 octets pour dix entiers. C’était la taille sur les anciennes machines, notamment les systèmes à 16 bits. Aujourd’hui, un int occupe presque toujours 4 octets, un char 1, un float 4 et un double 8. La norme du langage ne fixe pas ces tailles : on les demande toujours à sizeof plutôt que de les supposer.
| Définition | Taille d’un élément | Taille du tableau (valeurs courantes aujourd’hui) |
|---|---|---|
char t1[12] | 1 octet | 12 octets |
int t2[10] | 4 octets | 40 octets (et non 20, comme on le lit parfois) |
float t3[8] | 4 octets | 32 octets |
double t4[15] | 8 octets | 120 octets |
Attention : sizeof ne donne la taille du tableau que là où il a été défini. Une fonction qui reçoit un tableau en paramètre reçoit en réalité l’adresse de sa première case, et sizeof y donne la taille d’une adresse, pas celle du tableau. On passe donc toujours le nombre d’éléments à côté (voir les fonctions).
2.3Accéder aux éléments : l’indice
Le nom du tableau seul ne désigne pas un élément précis. On y ajoute un nombre entre crochets, l’indice (index en anglais), qui donne la position de la case. La règle est que la première case porte le numéro 0 et que la dernière porte le numéro « nombre d’éléments moins un ». Ainsi, le cinquième élément est notes[4].
Pourquoi commencer à zéro ? Parce que l’indice est en réalité un décalage : l’adresse de la case i est l’adresse du début plus i fois la taille d’une case (c’est ce que montre la figure 1). La première case est à un décalage de zéro.
Un élément se manipule comme une variable ordinaire :
int toto[10]; toto[7] = 6; /* huitième élément */ toto[9] = toto[0] + toto[1]; /* dixième = somme des deux premiers */
On lit que « l’indice est toujours positif » ; plus exactement, il ne doit jamais sortir de l’intervalle de 0 à n-1, et sortir par le bas (indice négatif) est tout aussi fautif que sortir par le haut.
2.4Le danger : sortir des limites
En C, rien ne vérifie l’indice. Écrire toto[10] dans un tableau de dix cases (dont le dernier indice est 9) ne produit pas d’erreur claire : le programme écrit simplement dans la case qui se trouve juste après, qui appartient peut-être à une autre variable ou à une donnée vitale du programme. C’est le dépassement de tampon (buffer overflow), l’une des familles de failles de sécurité les plus anciennes et les plus dangereuses (voir les pointeurs et la mémoire). Utiliser des constantes pour la taille aide à éviter un « débordement difficile à déceler ». La bonne pratique est de toujours contrôler les indices et d’employer des structures qui le font à votre place (partie 6).
2.5Initialiser un tableau
À la définition, les valeurs d’un tableau local ne sont pas définies : chaque case contient ce qui se trouvait là avant. Il faut donc l’initialiser. Il existe trois méthodes, toujours valables.
- Case par case, méthode « rustique » dont l’intérêt est « bien maigre » dès que le tableau est grand.
- Avec une boucle, où un compteur sert d’indice :
#define NB_NOTES 10 int toto[NB_NOTES]; for (int i = 0; i < NB_NOTES; i++) { toto[i] = 0; } - À la définition, avec des accolades :
int toto[10] = {1, 2, 6, 5, 2, 1, 9, 8, 1, 5}; int zeros[10] = {0}; /* tous les éléments à 0 */
Les règles de l’initialisation par accolades sont les suivantes : il ne doit pas y avoir plus de valeurs que d’éléments ; s’il y en a moins, les derniers éléments sont mis à zéro (c’est pourquoi {0} remplit tout le tableau de zéros) ; et, pour un tableau défini hors des fonctions ou déclaré static, les valeurs doivent être des constantes. Dans les compilateurs modernes (norme C99 et suivantes), les valeurs entre accolades d’un tableau local peuvent être des expressions.
Le conseil d’utiliser une constante (ici NB_NOTES) pour la taille garde tout son sens : moins d’erreurs de débordement, une seule ligne à changer pour modifier la taille, et un code plus lisible. On préfère aujourd’hui const ou une énumération à #define, car le compilateur les connaît et les contrôle.
Une correction utile. On voit proposer d’initialiser un tableau avec memset(*toto, 0, sizeof(toto));. L’écriture *toto est fausse : memset attend l’adresse de la zone à remplir, donc toto tout court, et non son premier élément. La forme correcte est memset(toto, 0, sizeof(toto));, valable seulement là où sizeof donne la vraie taille (voir 2.2). Notez aussi que memset remplit octet par octet : mettre un tableau d’entiers à zéro fonctionne, mais le remplir avec la valeur 1 ne donne pas des entiers égaux à 1.
Pour s’exercer
Exercice 1 : tailles
Sur une machine où int vaut 4 octets et double 8 octets, quelle est la taille de int a[25], de double b[3][4] et de char c[100] ? Comment obtenir le nombre d’éléments de a ?
Voir la réponse
a : 25 × 4 = 100 octets. b : 3 × 4 = 12 éléments × 8 = 96 octets. c : 100 octets. Nombre d’éléments de a : sizeof(a) / sizeof(a[0]) = 100 / 4 = 25, à condition que ce soit écrit là où a est défini et non dans une fonction qui l’a reçu en paramètre.
Exercice 2 : l’erreur d’une unité
Que fait ce code, et que faut-il corriger ? int t[5]; for (int i = 0; i <= 5; i++) t[i] = i;
Voir la réponse
Les indices valides sont 0 à 4. La boucle va jusqu’à 5 inclus : à la dernière itération, elle écrit dans t[5], une case qui n’existe pas, ce qui corrompt la mémoire voisine (comportement imprévisible, faille potentielle). Il faut écrire i < 5.
Exercice 3 : adresse d’une case
Un tableau d’entiers de 4 octets commence à l’adresse 2000. Quelle est l’adresse de t[7] ? Pourquoi le premier indice est-il 0 ?
Voir la réponse
Adresse = 2000 + 7 × 4 = 2028. L’indice est un décalage depuis le début : la première case est à un décalage de 0 × 4 = 0, donc à l’adresse 2000.
3Les tableaux à plusieurs dimensions
Un tableau multidimensionnel est un tableau qui contient d’autres tableaux. Par exemple, un tableau de 3 lignes et 4 colonnes est en fait « un tableau de 3 éléments, chacun étant un tableau de 4 éléments ». On l’appelle aussi matrice ou table.
int grille[3][4]; /* 3 lignes, 4 colonnes */ grille[2][1] = 5; /* ligne 2, colonne 1 */
Le nombre de dimensions n’est pas limité, mais au-delà de trois la lecture devient difficile. Chaque nombre entre crochets est le nombre d’éléments de cette dimension.
3.1Lignes ou colonnes ? Une affaire de convention
La représentation « première dimension = lignes, seconde = colonnes » est arbitraire : on pourrait dessiner le tableau transposé. Mais elle correspond mieux à la façon dont la mémoire range les valeurs : en C, la ligne 0 est rangée tout entière, puis la ligne 1, etc. L’ordre de remplissage est donc [0][0], [0][1], [0][2], [0][3], puis [1][0]… : on incrémente d’abord l’indice de droite. Cela a une conséquence pratique : pour parcourir une grande matrice vite, la boucle intérieure doit faire varier le dernier indice, car lire des cases voisines est bien plus rapide pour le processeur que de sauter d’une ligne à l’autre (le processeur charge la mémoire par blocs, voir la mémoire vive).
3.2Initialiser une matrice
Les quatre façons habituelles s’appliquent encore :
- case par case (
grille[0][0] = 2;…), vite fastidieux ; - avec des boucles imbriquées, une par dimension :
for (int i = 0; i < 3; i++) { for (int j = 0; j < 4; j++) { grille[i][j] = 0; } } - à la définition, avec des accolades, en regroupant par ligne pour la clarté :
int g[3][4] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}};; les valeurs remplissent les éléments successifs en incrémentant d’abord l’indice de droite ; - avec
memsetpour mettre toute la matrice à zéro :memset(grille, 0, sizeof(grille));(voir la correction en 2.5).
Une correction utile. Certains exemples de boucles écrivent i<2 et j<3 pour une grille de 3 lignes et 4 colonnes : cela ne parcourt que 2 lignes sur 3 et 3 colonnes sur 4. Une boucle sur un tableau de n éléments doit aller jusqu’à n-1 inclus, c’est-à-dire i < n et non i < n-1. Cette erreur « d’un cran » est si fréquente qu’on lui a donné un nom : l’erreur de décalage d’une unité (off-by-one).