USTHB - Faculté d’Informatique
Master1 IL – MODAL
TP
Listes Doublement Chaînées
Dans une liste doublement chaînée, chaque cellule possède deux liens : un lien vers la cellule
précédente et un lien vers la cellule suivante. Ainsi l'ensemble des cellules forme une chaine.
Pour programmer les listes doublement chainées nous aurons donc besoin de deux classes :
une classe Cellule programmant les cellules avec leurs liens, une classe
ListeChainee permettant de manipuler l'ensemble de la chaine.
1. La classe Cellule
La classe Cellule possède trois variables d'instance : une variable contenu de type
Object permettant de stocker un élément dans la cellule, et deux variables precedente
et suivante de type Cellule faisant référence aux cellules précédentes et suivantes
de la liste.
1. Programmez une méthode d'instance void chaineSuivante (Object obj)
permettant de chainer une nouvelle Cellule contenant l'objet obj à la suite de la cellule
appelante. L'algorithme de cette méthode est le suivant :
Données : une Cellule this (objet ayant appelé la méthode) Un Object obj.
Résultat : Une nouvelle cellule, contenant l'objet obj, est chainée à la cellule appelante.
Algorithme :
− créer une Cellule nouvelle.
− stocker obj dans le contenu de la cellule nouvelle
− faire pointer la référence suivante de la cellule nouvelle au même endroit que la
référence suivante de la cellule this.
− faire pointer la référence precedente de la cellule nouvelle vers this.
− si la référence suivante de this n'est pas égale à null, faire pointer la référence
precedente de suivante vers nouvelle.
− faire pointer la référence suivante de this vers nouvelle.
2. En vous inspirant de l'algorithme précédent, écrivez une méthode void
chainePrecedente (Object obj) permettant de chainer une nouvelle cellule
contenant l'objet obj avant la cellule appelante.
3. Ecrivez une méthode d'instance Object supprime() permettant de supprimer la
cellule appelante de la chaine dans laquelle elle se trouve. L'algorithme de cette méthode
est le suivant :
Données : une Cellule this (objet ayant appelé la méthode)
1
Résultat : La cellule this est supprimée de la chaine dont elle faisait partie. La chaine est
reformée avec les cellules restantes : la cellule precedente de this est chainée à la cellule
suivante de this. La méthode renvoie l'objet contenu dans la Cellule supprimée.
Algorithme :
− stocker le contenu de la Cellule appelante dans une nouvelle variable de type Object
resultat.
− si la Cellule precedente de this ne désigne pas la référence null alors la chainer
avec la Cellule suivante de this (la Cellule suivante de la Cellule precedente
de this devient la Cellule suivante de this).
− procéder de même pour chainer la Cellule suivante de this avec sa Cellule
precedente.
− envoyer la variable resultat.
2. La classe ListeChainee
Le principe de la classe ListeChainee est le suivant : chaque ListeChainee possède
deux variables d'instances debut et fin de type Cellule. Ces deux variables
représentent des cellules vides dont le seul intérêt est de permettre d'accéder aux autres
Cellules de la liste (respectivement en partant du début ou de la fin de la liste de cellules). En
particulier ces cellules ne seront jamais visibles pour l'utilisateur et elles ne seront jamais
modifiées après la création de la liste.
Par ailleurs chaque ListeChainee possède une variable d'instance taille indiquant
le nombre d'objets stockés dans la liste. Cette variable sera mise à jour chaque fois que l'on
ajoutera ou supprimera un élément de la liste.
1. Ecrire un constructeur sans paramètre pour ListeChainee. Ce constructeur doit
construire les deux Cellule debut et fin puis les chainer afin que la cellule
suivante de debut soit fin et que la cellule précédente de fin soit début.
2. Ecrire une méthode int size () renvoyant le nombre d'objet stockés dans la liste.
3. Ecrire une méthode boolean isEmpty() renvoyant true si et seulement si la liste
est vide.
4. Programmez une méthode void addFirst(Object obj) permettant d'ajouter un
élément au début de la liste. Pour cela il suffit de chainer à la suite de la cellule debut une
nouvelle cellule contenant l'objet obj puis d'ajouter un àtaille (vous utiliserez bien sûr
la méthode chaineSuivante de la classe Cellule).
5. Programmez une méthode void addLast(Object obj) permettant d'ajouter un
objet à la fin de la liste.
6. Programmez une méthode Object getFirst() renvoyant le premier objet de la
liste; c'est à dire le contenu de la cellule suivante de debut.
2
7. Programmez une méthode Object getLast () renvoyant le dernier élément de la
liste.
8. Programmez une méthode Object removeFirst() supprimant le premier élément
de la liste (si la liste n'est pas vide) et renvoyant cet élément (ou null si la liste est vide).
Pour cela vous utiliserez la méthode supprime() de la classe Cellule. N'oubliez pas de
modifier la valeur de taille afin de tenir compte de la nouvelle taille de la liste.
9. Programmez une méthode Object removeLast() supprimant le dernier élément de
la liste (si la liste n'est pas vide) et renvoyant l'élément supprimé.
10. Programmez une méthode void add(int position, Object obj)
permettant d'ajouter l'objet obj à la position donnée dans la liste. L'algorithme de cette
méthode est le suivant :
Données : une ListeChainee this (la ListeChainee appelante), un entier
position, un objet obj
Résultat : L'objet obj est ajouté à la position donnée dans la liste this.
Algorithme :
− Si position < 0 ou position > taille, il n y a rien à faire
− Créer une nouvelle variable temporaire de type Cellule faisant référence à la
cellule debut de this.
− Répéter position fois << Remplacer temporaire par une référence vers la
cellulesuivantede temporaire. La variable temporaire pointe maintenant vers la
cellule position‐1 de la liste chainée >>.
− chainer à la suite de temporaire une nouvelle Cellule contenant l'objet obj.
Ajouter un à la taille de this.
11. En s'inspirant de l'algorithme donné dans la question précédente programmez une
méthode Object get(int i) renvoyant le contenu de la i‐ème cellule de la liste
appelante. De la même façon programmez une méthode void set(int i, Object
obj)permettant de modifier le contenu de la i‐ème cellule de la liste appelante. Enfin
programmez une méthode Object remove (int i) supprimant la i‐ème cellule de la
liste appelante. Les valeurs de retours de ces méthodes seront déterminées comme dans le
cas des méthodes getFirst, setFirst, removeFirst.
12. Programmez une méthode int indexOf(Object obj) renvoyant la position de la
première occurrence de obj dans la liste appelante. L'algorithme de cette méthode est le
suivant :
Données : une ListeChainee this (la ListeChainee appelante), un objet obj
Résultat : La position de la première occurrence de obj dans la liste chainée this
où -1 si l'objet obj n'apparaît pas dans la liste.
Algorithme :
− créer une nouvelle variable entière position initialisée à -1.
3
− créer une nouvelle variable temporaire de type Cellule faisant référence à la cellule
debut de this.
− tant que la cellule suivante de temporaire n'est pas égale à la cellule fin de
this :
ajouter 1 à position.
remplacer temporaire par une référence vers la cellule suivante de
temporaire.
si le contenu de la cellule temporaire est égal à obj (au sens de equals1) alors
renvoyer position.
− renvoyer -1.
13. En s'inspirant de l'algorithme donné dans la question précédente, programmez une
méthode int lastIndexOf(Object obj) renvoyant la position de la dernière
occurrence de l'objet obj dans la liste chainée appelante où -1 si obj n'est pas un
élément de la liste.
14. Programmez une méthode boolean contains (Object obj) renvoyant true
ssi l'objet obj est un élément de la liste appelante.
1
La classe Object de Java propose la méthode equals(). Cette méthode permet de comparer la valeur de deux
instances.
4
