Application de
l'allocation dynamique: Les listes chaînées
Rappel: L'avantage
principal de
définir un tableau dynamique est que l'on peut réserver
l'espace
exact pour le tableau pour chacune des utilisations.
Mais: Que faire si la
taille du tableau n'est pas connu à l'avance par l'utilisateur?
Supposons par exemple que de nouveaux étudiants arrivent en
cours d'année,
il n'est pas possible d'agrandir le tableau en cours d'exécution
car
l'espace réservé pour
un tableau
doit être contigu en mémoire et donc alloué en une
seule fois.
Ce problème est très courant en
informatique:
- Comment prévoir à l'avance combien de
requêtes d'impression vont être envoyées à
l'imprimante?
- Comment prévoir à l'avance le nombre
d'enregistrements que l'on va lire dans un fichier?
- Comment prévoir à l'avance le nombre de
personnes qui vont adhérer à une association?
- Comment prévoir à l'avance le nombre de
contrats qui vont être décrochés par un commercial?
- etc...
Deux
solutions:
- Soit on
surdimensionne le tableau avec les problèmes que cela pose
(perte de place ou programme inadapté si sousdimensionnement).
- Soit on
dispose d'une
structure dynamique dont la taille s'adapte en fonction des besoins: la liste chaînée.
suivant
plan