Implantations spécialisées de l’interface List

Buts

• Satisfaire à une interface avec une implantation spécialisée.
• Réutiliser au maximum le code via l’héritage

Il faut créer deux implantations spécialisées de l’interface List du Collection Framework de Java, dans sa version simplifiée illustrée en classe. Vous avez déjà vu deux implantations possibles pour cette interface: ArrayList et LinkedList (qui utilise SLLNode) et on vous demande maintenant d’en écrire deux autres dont les implantations hériteront de celles-ci.

• GapArrayList qui hérite de ArrayList pour implanter une liste avec un tableau mais avec un trou au milieu. Les éléments actifs de la liste sont placés de façon contigue au début et à la fin du tableau. Ainsi plusieurs insertions consécutives à la même position au milieu d’une liste ne nécessitent pas de déplacer des éléments. Il n’y aura que le trou qui va rapetisser. Cette structure est utilisée par exemple pour représenter un tampon de texte dans l’éditeur Emacs comme c’est décrit ici (voir en particulier le 6e paragraphe).
• DoublyLinkedList qui hérite de LinkedList et utilise DLLNode pour implanter une liste doublement chaînée. On pourra ainsi accéder plus rapidement à un élément d’indice quelconque en suivant les pointeurs sur l’élément suivant à partir du début, si l’élément se situe dans la première moitié de la liste, ou en suivant les pointeurs sur l’élément précédent à partir de la fin de la liste si l’élément est dans la seconde moitié.
• DLLNode hérite de SLLNode en ajoutant un champ DLLNode pred.

Vous devez ensuite créer une application Java (non nécessairement graphique) qui va tester votre programme et vous donner confiance que vous respectez bien l’interface. Notez que les correcteurs utiliseront leur propre programme pour tester votre implantation. Vous devez quand même donner copie de votre application test et montrer dans votre rapport que vous respectez et que vous avez testé l’interface.

Notez que nous ne fournissons pas d’exemple de programme car votre implantation devrait retourner les mêmes résultats que ceux des implantations expliquées en classe.

• Vous devez implanter toute l’interface List y compris l’itérateur et les opérations optionnelles associées.
• Vous devez absolument hériter des classes indiquées plus haut et ne redéfinir que les méthodes strictement nécessaires et tenter si possible d’utiliser le code de la superclasse via super. Votre rapport devra donc justifier chaque méthode que vous avec redéfinie. Vous pourriez perdre des points si vous redéfinissez inutilement une méthode.
• Vous pouvez toutefois définir des méthodes privées supplémentaires pour vous aider à la mise au point, par exemple retournant de l’information sur les structures internes.
• Indiquez dans votre rapport les cas de tests que vous avez faits.

Ce travail est à réaliser en groupes de deux (minimum-maximum)

Fonctionnement correct avec les tests des démonstrateurs	3
Vos tests et leur organisation	2
Lisibilité du code et respect des contraintes d’implantation	3
Rapport	2