Paquetage, structures de données, relations d'implantation

Exercice 1 - Les listes chaînées

1. Créer une classe fr.upem.data.Link correspondant à un maillon de la liste chaînée (valeur et référence vers le suivant).
2. Quelle est la commande à utiliser dans un terminal pour exécuter le main de la classe fr.upem.data.Link ?
3. Créer une classe fr.upem.data.LinkedLink qui permettra de manipuler une liste chainée sans que l'utilisateur ait à manipuler des maillons.
   Cette classe maintient une référence sur le premier maillon de la liste et possède les méthodes suivantes :
   1. add(String text) qui ajoute un élément en tête (avant le premier élément).
   2. size() qui retourne le nombre d'éléments de la liste.
   3. toString() qui retourne une représentation textuelle de la liste.

Pour tester ces classes, créer une classe Main sans paquetage (on dit dans le paquetage par défaut), avec un main de test:

$> java Main les jolis ponts du mois de Mai
taille : 7
[Mai, de, mois, du, ponts, jolis, les]

Exercice 2 - Liste chainée (suite)

1. Renommer la classe Main en fr.upem.data.main.Main.
   Dans quel répertoire doit-on se placer et quelle est la commande pour exécuter le main dans une console hors d'eclipse ?
2. Implanter String get(int index) qui renvoie la index-ième chaîne de caractères.
   Que doit-on faire si l'indice est invalide ?
   Pourquoi serait-il logique de changer l'implantation de size() pour que cette méthode s'exécute en temps constant ?
   Ré-implanter size.
3. Ajouter à la classe LinkedLink une méthode textSum renvoyant la taille totale de la liste en nombre de caractères (somme des longueurs des éléments de la liste).
4. Changer la classe fr.upem.data.LinkedLink pour une implantation plus générique à base d'Object au lieu de String.
   Que doit-on changer dans la méthode textSum ?
5. Implanter la méthode boolean contains(Object o) indiquant si un objet est ou non contenu dans la liste chaînée.
6. Tester l'ensemble de vos méthodes. Vous pourrez par exemple utiliser la classe Main suivante:
   
   qui doit produire l'affichage suivant:

   $> java fr.upem.data.main.Main les jolis ponts du mois de Mai
   taille : 11
   [3.141592653589793, Intrus, Mai, de, mois, du, ponts, jolis, les, 4, java.lang.Object@135fbaa4]
   textSum : 73
   true
   

Exercice 3 - Générification de LinkedLink

1. Paramétrer la classe fr.upem.data.LinkedLink pour que celle-ci soit générique.
2. Modifier la classe fr.upem.data.main.Main en conséquence.

Exercice 4 - Performance sur les listes

1. Nous allons dans un premier temps chronométrer le temps d'un parcours d'une ArrayList contenant un million (1 000 000) d'entiers en utilisant d'abbord un Iterator, puis un index pour le parcours.
   Utilisez la méthode System.nanoTime() pour effectuer une mesure de temps.
2. Modifier votre programme pour pouvoir facilement chronométrer le parcours dans le cas d'une ArrayList ou d'une LinkedList avec le même code.

• parcours de la liste d'un million d'entiers par un itérateur
• parcours de la liste d'un million d'entiers par un index