Aller au contenu
Encyclopédie informatique Édition 2026

Tableaux, listes et structures de données

Partie 3 sur 3

Niveau de lecture :

6Les mêmes idées dans les autres langages

Écrire ses propres listes en C est instructif, mais, dans la pratique, les langages modernes fournissent des structures prêtes à l’emploi, qui cachent la mémoire et vérifient les limites.

6.1C++ : std::array et std::vector

Le C++ garde les tableaux du C, mais propose dans sa bibliothèque standard deux outils plus sûrs : std::array, un tableau de taille fixe qui connaît sa taille, et std::vector, un tableau extensible qui réserve la mémoire, la rend automatiquement et grandit quand on ajoute des éléments :

#include <vector>
std::vector<int> notes = {12, 15, 9};
notes.push_back(14);          /* ajoute à la fin */
int n = notes.size();         /* 4 */
int x = notes.at(10);         /* lève une erreur claire au lieu de déborder */

Quand le vecteur est plein, il alloue un tableau plus grand (souvent deux fois) et y recopie ses éléments ; cette recopie, rare, est rentabilisée par les nombreux ajouts suivants, d’où un coût « O(1) en moyenne ». En C++, les structures sont identiques à celles du C, à ceci près que l’obligation d’écrire struct disparaît.

6.2Python : la liste et le dictionnaire

En Python (voir le langage Python), le mot « liste » désigne en réalité un tableau extensible, qui accepte des éléments de types mélangés :

notes = [12, 15, 9]
notes.append(14)       # ajoute à la fin
notes[0]               # 12 ; l'indice commence à 0 comme en C
notes[-1]              # 14 ; l'indice négatif compte depuis la fin
age = {"Paul": 16, "André": 22}   # dictionnaire : clé -> valeur
age["Pierre"] = 12

Accéder à une case hors limites provoque une erreur explicite (IndexError) et non une corruption silencieuse.

6.3JavaScript : l’objet Array et les tableaux « associatifs »

En JavaScript (voir le langage JavaScript), un tableau est un objet Array. Il existe plusieurs façons de le créer :

const a = ["donnée 1", "donnée 2", "donnée 3"];   /* forme usuelle */
const b = new Array("x", "y");                    /* forme équivalente, moins employée */
const c = [];                                     /* tableau vide */

Pour accéder à un élément, on écrit le nom suivi de l’indice entre crochets (a[3] est le quatrième). La propriété length donne le nombre d’éléments. Voici les méthodes de l’objet Array, avec leur description corrigée :

MéthodeEffet
concat(t2)renvoie un nouveau tableau, concaténation (mise bout à bout) des tableaux
join(sép)renvoie une chaîne contenant tous les éléments, séparés par sép
push(v1, v2…)ajoute des éléments à la fin
pop()supprime le dernier élément et renvoie sa valeur
unshift(v1…)ajoute des éléments au début
shift()supprime le premier élément et renvoie sa valeur
slice(début, fin)renvoie une copie d’une partie (extraction), sans modifier le tableau
splice(pos, n, v…)retire et/ou ajoute des éléments à une position donnée, en modifiant le tableau
reverse()inverse l’ordre des éléments
sort()trie les éléments
valueOf()renvoie la valeur du tableau lui-même
toString()renvoie les éléments sous forme d’une chaîne séparée par des virgules

Des corrections utiles. On voit parfois unshift décrit à tort comme renvoyant « le code source qui a permis de créer l’objet Array » (description qui appartient à une méthode ancienne, toSource, jamais standard) ; en réalité, il ajoute des éléments au début. On liste aussi les propriétés constructor (le constructeur de l’objet) et prototype (qui permet d’ajouter ses propres propriétés à tous les tableaux, pratique déconseillée), ainsi qu’une propriété input qui ne concerne en fait que les résultats d’une recherche par expression régulière, et non les tableaux ordinaires. On écrit parfois des appels de la forme pop(tableau) alors que ces méthodes s’appellent sur le tableau (tableau.pop()). Enfin, sort() trie par défaut comme du texte : [10, 9, 1].sort() donne [1, 10, 9]. Pour trier des nombres, on fournit une fonction de comparaison : tableau.sort((x, y) => x - y).

On parle aussi de tableaux associatifs, où l’on utilise « une chaîne ou un nombre spécifique » comme indice, par exemple MonTableau["Pierre"] = 12. Cela marche parce qu’en JavaScript un tableau est un objet, mais c’est une mauvaise pratique : ces valeurs n’entrent pas dans length et les méthodes comme push ou sort les ignorent. La bonne pratique est d’employer un objet ({"Pierre": 12}) ou, mieux, un objet Map, conçu pour cela. Les tableaux à plusieurs dimensions s’écrivent aujourd’hui comme des tableaux de tableaux : [[1, 2], [3, 4]].

Afficher le résultat avec document.write est déconseillé aujourd’hui, car cela peut effacer toute la page. On écrit plutôt dans un élément de la page ou, pour tester, dans la console du navigateur avec console.log.

6.4Le dictionnaire, ou tableau associatif

Un dictionnaire associe une clé (un nom) à une valeur. Contrairement au tableau, où l’on retrouve une valeur par son numéro, on la retrouve par son nom : age["Pierre"]. Presque tous les langages le proposent sous des noms différents (dict en Python, Map ou objet en JavaScript, std::unordered_map en C++). Il est le plus souvent réalisé avec une table de hachage : une fonction transforme la clé en un numéro de case dans un tableau interne (voir le hachage), ce qui permet de retrouver la valeur en un temps presque constant, quelle que soit la taille du dictionnaire.

Pour s’exercer

Exercice 6 : choisir

Pour chacun des besoins suivants, quelle structure : (a) les 1 000 notes d’une classe lues par numéro d’élève ; (b) retrouver le numéro de téléphone d’un contact par son nom ; (c) une file d’attente où l’on retire toujours le premier et ajoute toujours à la fin, avec des millions d’éléments.

Voir la réponse

(a) un tableau (accès par position en O(1)). (b) un dictionnaire (recherche par clé en O(1) en moyenne). (c) une structure faite pour cela, une file, réalisée avec une liste chaînée ayant un pointeur de tête et un pointeur de fin, ou un tampon circulaire ; un simple tableau où l’on retire le premier élément coûterait O(n) à chaque retrait.

Exercice 7 : le tri en JavaScript

Que donne [25, 100, 3].sort() en JavaScript ? Comment obtenir un tri croissant des nombres ?

Voir la réponse

Par défaut, sort compare les éléments comme du texte : "100" avant "25" avant "3", donc le résultat est [100, 25, 3]. Pour trier des nombres, on passe une fonction de comparaison : [25, 100, 3].sort((x, y) => x - y) donne [3, 25, 100].

7Quelle structure choisir ?

Le bon choix dépend des opérations que le programme fait le plus souvent. La figure 3 compare les structures selon leur coût. On l’exprime avec la notation O (« grand O »), qui indique comment le temps d’une opération grandit avec le nombre n d’éléments : O(1) veut dire que le temps ne dépend pas de n (constant), O(n) qu’il est proportionnel à n (dix fois plus d’éléments, environ dix fois plus de temps).

CE QUE COÛTE CHAQUE OPÉRATION SELON LA STRUCTURE opération tableau liste chaînée dictionnaire accès par position immédiat, O(1) parcours, O(n) sans objet recherche par valeur parcours, O(n) parcours, O(n) par clé : O(1) moyen ajout à la fin O(1) en moyenne O(1) si on garde la fin O(1) en moyenne insertion au milieu décalage : O(n) O(1) une fois trouvé sans objet suppression au milieu décalage : O(n) O(1) une fois trouvé O(1) en moyenne place en mémoire compacte un pointeur par maillon table plus grande n = nombre d’éléments ; O(1) : temps constant ; O(n) : temps proportionnel à n.
Figure 3. Ce que coûte chaque opération selon la structure ; n est le nombre d’éléments.

7.1La règle pratique

  • Si vous lisez souvent par position et ajoutez surtout à la fin, un tableau extensible (vector, liste Python, Array JavaScript) est presque toujours le meilleur choix.
  • Si vous cherchez souvent par un nom, un identifiant ou une clé, un dictionnaire.
  • Si vous insérez et supprimez sans cesse au milieu d’une très grande suite, sans accès par position, la liste chaînée peut convenir ; mais voyez le point suivant.
  • Si vous avez des données de natures différentes qui forment un tout (une personne, un produit), une structure (ou une classe, ou un objet), éventuellement stockée dans un tableau.

7.2Pourquoi le tableau gagne souvent contre la liste

Sur le papier, la liste chaînée gagne l’insertion au milieu. En pratique, les tableaux gagnent beaucoup plus souvent qu’on ne le croit, à cause du matériel : un processeur charge la mémoire par blocs, et le tableau, dont les cases sont voisines, profite pleinement de ce chargement ; les maillons d’une liste, dispersés, obligent à de multiples accès lents à la mémoire. Pour des centaines ou des milliers d’éléments, le tableau est souvent plus rapide même pour l’insertion. Ne choisissez la liste que si la mesure le justifie.

7.3Mesurer plutôt que deviner

Un principe vaut pour toutes ces structures : n’optimisez pas sans avoir mesuré. Un programme qui manipule cent éléments se moque du coût en O(n) ; un programme qui en manipule dix millions s’en soucie. Les mesures (le temps réel avec un chronomètre ou un outil d’analyse de performance) doivent trancher.

Sécurité de l’information

Le coin cyber

Cet article explique pourquoi certaines erreurs sur les tableaux sont dangereuses. Il ne contient aucune méthode pour les exploiter.

C.1Le tableau, premier terrain des failles

Beaucoup de failles graves découlent d’un simple tableau mal contrôlé : un programme copie des données dans une zone trop petite et écrase ce qui se trouve à côté. Les conséquences vont du plantage à la prise de contrôle de la machine. Les défenseurs en tirent des règles simples : vérifier toute taille et tout indice venant de l’extérieur, utiliser des fonctions de copie bornées, activer les protections du compilateur et du système, et, quand c’est possible, écrire dans un langage qui contrôle les limites (voir les pointeurs et la mémoire).

C.2Le cadre légal

Un éditeur de logiciel engage sa responsabilité pour les défauts de sécurité de ses produits ; en Europe, le règlement sur la cyber-résilience (Cyber Resilience Act) impose aux produits comportant des éléments numériques des exigences de sécurité dès la conception et la correction des failles connues. Chercher une faille dans le système d’un tiers sans son autorisation relève des articles 323-1 et suivants du code pénal.

C.3Idée reçue

« Mon tableau fait 100 cases, personne n’écrira jamais 101 valeurs. » Faux. Un attaquant choisit précisément la donnée qui dépasse : un nom trop long, un fichier mal formé, un paquet réseau modifié. Toute donnée venant de l’extérieur doit être contrôlée avant d’être copiée dans un tableau, quelle que soit l’intention supposée de l’utilisateur.

C.4Bonnes pratiques

Développeur

  • Contrôler les indices et les longueurs, employer des copies bornées.
  • Préférer std::vector, std::array ou un langage à contrôle de limites.
  • Compiler avec les avertissements activés et tester avec les outils de détection d’erreurs mémoire.

Organisation

  • Imposer une revue de code attentive sur les zones qui manipulent des tailles venues de l’extérieur.
  • Mener des tests automatiques avec des données aléatoires (« fuzzing ») sur les programmes qui lisent des fichiers ou des messages.
  • Mettre à jour les bibliothèques, qui corrigent régulièrement de telles erreurs.

Référentiels : MITRE, CWE-119 (limites d’un tampon mémoire) et CWE-787 (écriture hors limites) · ISO/IEC 9899 (norme du langage C) · Règlement (UE) 2024/2847 (Cyber Resilience Act) · Code pénal, articles 323-1 à 323-7.

Références

  1. Brian W. Kernighan, Dennis M. Ritchie, The C Programming Language, Prentice Hall, 2e éd., 1988.
  2. ISO/IEC 9899:2018, Information technology, Programming languages, C.
  3. Edsger W. Dijkstra, Why numbering should start at zero, EWD831, 1982.
  4. Eugene H. Spafford, The Internet Worm Program: An Analysis, Purdue Technical Report CSD-TR-823, 1988.
  5. Donald E. Knuth, The Art of Computer Programming, volume 1 : Fundamental Algorithms, Addison-Wesley.

Voir aussi

Citer cet article

« Tableaux, listes et structures de données », Encyclopédie informatique, révision du 4 novembre 2026.