Organiser correctement les données dans un programme, c'est comme bien ranger une boîte à outils : tout devient plus simple et rapide. Ce chapitre présente les structures fondamentales pour stocker et gérer des informations efficacement.
Pourquoi c'est essentiel : Le choix des structures de données impacte directement les performances et la lisibilité de votre code. Une structure adaptée permettra d'accéder rapidement aux informations et de manipuler efficacement les données dans vos programmes.
1. Les tableaux
Les tableaux sont les structures les plus simples : une suite d'éléments numérotés, tous du même type.
- Accès direct à chaque élément avec un indice (ex:
monTableau[3]) - Statique : la taille est fixée à l'avance dans de nombreux langages
// Exemples de déclaration de tableaux
// En JavaScript
const nombres = [42, 17, 99, 8, 75];
console.log(nombres[3]); // Affiche 8
// En Python
nombres = [42, 17, 99, 8, 75]
print(nombres[3]) # Affiche 8
// En Java
int[] nombres = {42, 17, 99, 8, 75};
System.out.println(nombres[3]); // Affiche 8
2. Les listes chaînées
Les listes chaînées relient les données entre elles grâce à des pointeurs.
- Flexible : on peut ajouter/supprimer des éléments facilement
- Plus complexe : il faut parcourir la liste élément par élément
// Implémenter une liste chaînée en JavaScript
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
// Ajouter un élément à la fin
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
// Parcourir et afficher
display() {
let current = this.head;
let result = '';
while (current) {
result += current.data + ' → ';
current = current.next;
}
return result + 'NULL';
}
}
// Exemple d'utilisation
const list = new LinkedList();
list.append(42);
list.append(17);
list.append(99);
console.log(list.display()); // "42 → 17 → 99 → NULL"
Quand utiliser une liste chaînée ? Les listes chaînées sont idéales quand vous avez besoin d'ajouter ou supprimer fréquemment des éléments à différentes positions, sans connaître à l'avance la taille de la collection. Elles sont moins efficaces que les tableaux pour l'accès aléatoire aux éléments.
3. Pointeurs et mémoire
Un pointeur est une variable qui stocke l'adresse d'un autre élément en mémoire.
C'est essentiel pour :
- Créer des structures dynamiques (comme les listes chaînées)
- Optimiser la gestion de la mémoire
// Exemple de pointeurs en C
#include
int main() {
int nombre = 42;
int *pointeur; // Déclaration d'un pointeur
pointeur = &nombre; // pointeur stocke l'adresse de nombre
printf("Valeur de nombre: %d\n", nombre);
printf("Adresse de nombre: %p\n", &nombre);
printf("Valeur de pointeur: %p\n", pointeur);
printf("Valeur pointée par pointeur: %d\n", *pointeur);
// Modifier la valeur via le pointeur
*pointeur = 99;
printf("Nouvelle valeur de nombre: %d\n", nombre);
return 0;
}
4. Enregistrements (ou structures)
Les enregistrements permettent de regrouper plusieurs types de données sous une seule entité (ex: nom, prénom, date de naissance).
En JavaScript, on parle souvent d'objets, en Python de dict, et en C/C++ de struct.
// Exemple d'enregistrement (objet) en JavaScript
const personne = {
nom: "Dupont",
prenom: "Marie",
age: 32,
email: "marie.dupont@example.com"
};
console.log(personne.nom); // "Dupont"
console.log(personne.age); // 32
// Struct en C
struct Personne {
char nom[50];
char prenom[50];
int age;
char email[100];
};
// Dictionnaire en Python
personne = {
"nom": "Dupont",
"prenom": "Marie",
"age": 32,
"email": "marie.dupont@example.com"
}
5. Organisation dynamique
On peut faire évoluer les structures selon les besoins avec :
- Tableaux dynamiques : qui changent de taille (ex:
ArrayListen Java) - Tableaux de pointeurs : pour des cas complexes
// Exemple de tableau dynamique en JavaScript (natif)
let nombres = [];
nombres.push(42); // Ajoute à la fin
nombres.push(17);
nombres.push(99);
console.log(nombres.length); // 3
// Exemple en Java avec ArrayList
import java.util.ArrayList;
ArrayList nombres = new ArrayList<>();
nombres.add(42);
nombres.add(17);
nombres.add(99);
System.out.println(nombres.size()); // 3
Organisation dynamique vs statique : Les structures dynamiques comme les ArrayList ou les vecteurs permettent d'ajuster automatiquement la taille selon les besoins, mais elles ont un léger surcoût en mémoire et en performance par rapport aux tableaux statiques. Choisissez en fonction de vos besoins spécifiques.
À retenir
- Les tableaux sont simples mais peu flexibles (accès direct, taille fixe)
- Les listes chaînées sont plus dynamiques mais plus complexes (accès séquentiel)
- Les pointeurs donnent un contrôle fin sur la mémoire et permettent les structures dynamiques
- Les enregistrements (structs/objets) modélisent des entités du monde réel avec plusieurs attributs
- Les structures dynamiques permettent d'adapter la taille selon les besoins
- Bien choisir sa structure = code plus lisible + plus performant