Formation JAVA les listes chaînées, tutoriel & guide de travaux pratiques en pdf.

OPERATIONS SUR LES LISTES CHAINEES, VERSION ITERATIVE

Conformement a leur definition, les listes sont des structures recursives. Par consequent, les operations sur les listes s’expriment naturellement par des algorithmes recursifs´. En memeˆ temps, les listes sont des structures lineaires, parfaitement adaptees a un parcours iteratif. Nous allons proposer d’abord une version des classes qui implementera les methode de maniere` iterative, et nous en donnerons ensuite une version recursive.
La representation de la classe Liste ci-dessous montre sous forme de methodes les operations sur listes que nous discuterons.

Listing 14.3 – (lien vers le code brut)
1
p u b l i c c l a s s L i s t e f
2
3 p u b l i c b o o l e a n e s t V i d e ( ) fg
4 p u b l i c E l e m e n t L i s t e g e t D e b u t ( ) fg
5 p u b l i c v o i d a j o u t e r A u D e b u t ( i n t v ) fg
6 p u b l i c i n t g e t L o n g u e u r ( ) fg
7 p u b l i c b o o l e a n c o n t i e n t ( i n t v ) fg
8 p u b l i c v o i d r e t i r e r P r e m i e r e O c c u r r e n c e ( i n t v ) fg
9 p u b l i c v o i d c o n c a t e n e r ( L i s t e l ) fg
10
11 g

La classe ElementListe

Nous avons decid´e´ de placer toute la logique des methodes´ dans la classe Liste. Ce n’est pas forcement´ la seule solution, mais le code obtenu sera plus facile a` expliquer.
La classe ElementListe est donc reduite´ a` sa plus simple expression : un el´ement´ de liste a
une valeur, et est suivi d’un autre el´ement´ de liste (qui peut etreˆ eventuellement´ null si notre el´ement´ est le dernier).
La classe est dotee´ de plusieurs constructeurs et des accesseurs necessaires´.
Listing 14.4 – (lien vers le code brut)
1 p u b l i c c l a s s E l e m e n t L i s t e f
2 p r i v a t e i n t v a l e u r ;
3 p r i v a t e E l e m e n t L i s t e s u i v a n t ;
4 p u b l i c E l e m e n t L i s t e ( i n t v a l e u r , E l e m e n t L i s t e s u i v a n t ) f
5
6 t h i s . v a l e u r = v a l e u r ;
7 t h i s . s u i v a n t = s u i v a n t ;
8 g
9
10 /
11 C re´ e un e´ l e´ m e n t de l i s t e s a n s s u c c e s s e u r .
12 @param v
13 /
14 p u b l i c E l e m e n t L i s t e ( i n t v ) f
15 t h i s . v a l e u r = v ;
16 t h i s . s u i v a n t = n u l l ;
17 g
18 p u b l i c i n t g e t V a l e u r ( ) f
19
20 r e t u r n v a l e u r ;
21 g
22
23 p u b l i c v o i d s e t V a l e u r ( i n t v a l e u r ) f
24 t h i s . v a l e u r = v a l e u r ;
25 g
26
27 p u b l i c E l e m e n t L i s t e g e t S u i v a n t ( ) f
28 r e t u r n s u i v a n t ;
29 g
30
31 p u b l i c v o i d s e t S u i v a n t ( E l e m e n t L i s t e s u i v a n t ) f
32 t h i s . s u i v a n t = s u i v a n t ;
33 g
34 g
Consulter la valeur d’un el´ement´ et acceder´ a` l’el´ement´ suivant Ces operations´ sont realis´ees´ par les methodes´ getValeur (qui retourne la valeur associee´ a` un el´ement´ e de la liste), respectivement getSuivant (qui retourne l’el´ement´ qui suit e, ou null si e est le dernier el´ement)´.
En rendant les variables d’instance valeur et suivant private, nous nous sommes interdit d’y acceder´ directement, d’ou` l’ecriture´ de ces methodes,´ appelees´ accesseurs.
Nous verrons plus tard que l’acces` direct aux variables d’instance est deconseill´e´ dans la program-mation orientee´-objet. A la place, on preferre´ “cacher” les variables d’instance et donner acces` a` leur valeurs a` travers des methodes´. Ceci fera l’objet d’un prochain cours.
Remarque : Il ne faut pas oublier que getValeur et getSuivant sont des methodes´ de la classe ElementListe, donc une instruction comme return valeur signifie return this.valeur
Modifier la valeur et l’el´ement´ suivant
Ces operations´ sont realis´ees´ par les methodes´ setValeur (qui modifie la valeur d’un el´ement´ de la liste), respectivement setSuivant (qui change l’el´ement´ suivant).
Ces methodes´ permettent donc de modifier les composants valeur et suivant d’une cellule de la liste. Elles sont complementaires´ aux methodes´ getValeur() et getSuivant(), qui per-mettent de consulter ces memesˆ composants.
Leur presence´ dans la classe ElementListe correspond au memeˆ principe que celui evoqu´e´ pour getValeur() et getSuivant() : remplacer l’acces` direct aux variables d’instance par des appels de methodes´.

Operations´ sans parcours de liste

Pour ces operations´ il n’y a pas de variantes iteratives´ et recursives,´ l’action est realis´ee´ directe-ment sur l’objet Liste.
Obtenir le premier el´ement´ de la liste
Cette operation´ est realis´ee´ par la methode´ getPremier() qui retourne le premier ElementListe
de la liste.
Listing 14.5 – (lien vers le code brut)
1 p u b l i c E l e m e n t L i s t e g e t P r e m i e r ( ) f
2 r e t u r n p r e m i e r ;
3 g
Savoir si une liste est vide
Une liste est vide si son premier el´ement´ est a` null. La methode´ estVide() de la classe
Liste est donc :
Listing 14.6 – (lien vers le code brut)
1 p u b l i c b o o l e a n e s t V i d e ( ) f
2 r e t u r n p r e m i e r == n u l l ;
3 g
Inserer´ un el´ement´ en teteˆ de liste
L’insertion en teteˆ de liste est realis´ee´ par la methode´ ajouterAuDebut. C’est une operation´ simple, car elle necessite´ juste un acces` a` la teteˆ de la liste initiale. On cree´ une nouvelle cellule, a` laquelle on enchaˆıne l’ancienne liste.
Listing 14.7 – (lien vers le code brut)
1 p u b l i c v o i d a j o u t e r A u D e b u t ( i n t v ) f
2 E l e m e n t L i s t e a n c i e n P r e m i e r = p r e m i e r ;
3 p r e m i e r = new E l e m e n t L i s t e ( v , a n c i e n P r e m i e r ) ;
4 g

Operations avec parcours de liste – variante iterative

Ces operations´ necessitent´ un parcours complet ou partiel de la liste. Dans la variante iterative, le parcours est realis´e´ a` l’aide d’une ref´erence´ qui part de la premiere cellule de la liste et suit l’en-chaˆınement des cellules.
La figure 14.2 illustre le principe du parcours iteratif´ d’une liste a` l’aide d’une ref´erence´ ref.
Calculer la longueur d’une liste
Cette operation,´ realis´ee´ par la methode´ getLongueur, necessite´ un parcours complet de la liste
pour compter le nombre de cellules trouvees´.

Listing 14.8 – (lien vers le code brut)
1 p u b l i c i n t g e t L o n g u e u r ( ) f
2 i n t l o n g u e u r = 0 ;
3 E l e m e n t L i s t e r e f = g e t P r e m i e r ( ) ;
4 w h i l e ( r e f ! = n u l l ) f
5 l o n g u e u r + + ;
6 r e f = r e f . g e t S u i v a n t ( ) ;
7 g
8 r e t u r n l o n g u e u r ;
9g
Remarque : La ref´erence´ ref est positionnee´ au debut´ sur la premiere` cellule de la liste et avance jusqu’a` ce qu’elle devient nulle a` la fin de la liste. Chaque fois qu’elle pointe vers une nouvelle cellule, le compteur est increment´e´. Remarquez que l’avancement dans la liste se fait en utilisant la methode´ getSuivant de la cellule courante.
Verifier´ l’appartenance d’un el´ement´ a` une liste
Cette operation,´ realis´ee´ par la methode´ contient, necessite´ un parcours partiel de la liste pour chercher l’el´ement´ en question. Si l’el´ement´ est retrouve,´ le parcours s’arreteˆ a` ce moment-la,` sinon il continue jusqu’a` la fin de la liste.

Listing 14.9 – (lien vers le code brut)
1 p u b l i c b o o l e a n c o n t i e n t ( i n t v ) f
2 b o o l e a n t r o u v e = f a l s e ;
3 E l e m e n t L i s t e r e f = g e t P r e m i e r ( ) ;
4 w h i l e ( ! t r o u v e && r e f ! = n u l l ) f
5 i f ( r e f . g e t V a l e u r ( ) ==v ) f
6 g t r o u v e = t r u e ;
7 e l s e f
8 r e f = r e f . g e t S u i v a n t ( ) ;
9 g
10 g
11 / / t r o u v e e s t v r a i i m p l i q u e d o n c r e f . g e t V a l e u r ( ) ==v
12 / / a u t r e t e s t p o s s i b l e p o u r l a b o u c l e
13 / / w h i l e ( r e f != n u l l && r e f . g e t V a l e u r ( ) != v )
14 / / e x p l i q u e r l ’ o r d r e d e s t e s t d a n s c e c a s .
15 r e t u r n t r o u v e ;
16 g
Concatenation´ de deux listes
Cette operation,´ realis´ee´ par la methode´ concatener, rajoute a` la fin de la liste courante toutes les cellules de la liste passee´ en parametre`. Elle necessite´ un parcours complet de la liste courante, afin de trouver sa derniere` cellule.
La liste obtenue par concatenation´ a toujours la memeˆ premiere` cellule que la liste initiale. On
peut dire donc que la liste initiale a et´e´ modifiee,´ en lui rajoutant par concatenation´ une autre liste.
Tel que le code est ecrit,´ les el´ements´ de la liste l sont partages´ entre l et la liste l0 a` laquelle on
l’a concaten´ee´. Une modification ulterieure´ de l peut avoir des consequences´ inattendues sur l0. Une variante plus sure,ˆ mais plus couteuseˆ en temps et en espace memoire´ serait de dupliquer le contenu de l.

Listing 14.10 – (lien vers le code brut)
1 p u b l i c v o i d c o n c a t e n e r ( L i s t e l ) f
2 i f ( t h i s . e s t V i d e ( ) ) f
3 t h i s . p r e m i e r = l . g e t P r e m i e r ( ) ;
4 g e l s e f
5 / / On p a r c o u r t l a l i s t e j u s q u ’ a` eˆ t r e s u r
6 / / l e d e r n i e r e´ l e´ m e n t , c e l u i d o n t l e s u i v a n t e s t n u l l .
7 E l e m e n t L i s t e d e r n i e r = t h i s . g e t P r e m i e r ( ) ;
8 w h i l e ( d e r n i e r . g e t S u i v a n t ( ) ! = n u l l ) f
9 d e r n i e r = d e r n i e r . g e t S u i v a n t ( ) ;
10 g
11 / / Nous y sommes . d e r n i e r c o r r e s p o n d au d e r n i e r e´ l e´ m e n t
12 / / de l a l i s t e , q u i e x i s t e c a r c e l l e c i n ’ e s t p a s v i d e .
13 / / On f i x e d o n c l e s u i v a n t de ‘ ‘ d e r n i e r ’ ’ au p r e m i e r
14 / / e´ l e´ m e n t de l a l i s t e l .
15 d e r n i e r . s e t S u i v a n t ( l . g e t P r e m i e r ( ) ) ;
16 g
17 g
Remarque : La condition de la boucle while change ici, car on veut s’arreterˆ sur la derniere` cellule et non pas la depasser´ comme dans les methodes´ prec´edentes´. Remarquez que l’enchaˆınement des deux listes se fait en modifiant la variable d’instance suivant de la derniere` cellule a` l’aide de la methode´ setSuivant.
Dans le memeˆ esprit que l’algorithme de concatenation,´ on peut ecrire´ l’ajout d’un el´ement´ en derniere` position d’une liste :

Listing 14.11 – (lien vers le code brut)
1 p u b l i c v o i d a j o u t e r A L a F i n ( i n t v ) f
2 i f ( e s t V i d e ( ) ) f
3 g p r e m i e r = new E l e m e n t L i s t e ( v ) ;
4 e l s e f
5 / / I l y a un d e r n i e r e´ l e´ m e n t .
6 / / On l e c h e r c h e e t on a j o u t e a p r e` s l u i .
7 E l e m e n t L i s t e d e r n i e r = g e t D e r n i e r E l e m e n t ( ) ;
8 / / n o u s s a v o n s que
9 / / d e r n i e r . g e t S u i v a n t ( ) == n u l l => d e r n i e r e s t b i e n l e d e r n i e r e´ l e´ m e n t .
10 d e r n i e r . s e t S u i v a n t ( new E l e m e n t L i s t e ( v ) ) ;
11 g
12 g
13
14 /
15 T r o u v e l e d e r n i e r e´ l e´ m e n t d ’ une l i s t e non v i d e .
16 L a n c e une f @ l i n k N u l l P o i n t e r E x c e p t i o n g p o u r une l i s t e v i d e .
17 @ r e t u r n l e d e r n i e r e´ l e´ m e n t d ’ une l i s t e
18 @throws une N u l l P o i n t e r E x c e p t i o n s i l a l i s t e e s t v i d e
19 /
20 p r i v a t e E l e m e n t L i s t e g e t D e r n i e r E l e m e n t ( ) f
21 E l e m e n t L i s t e d e r n i e r = p r e m i e r ;
22 w h i l e ( d e r n i e r . g e t S u i v a n t ( ) ! = n u l l ) f
23 d e r n i e r = d e r n i e r . g e t S u i v a n t ( ) ;
24 g
25 r e t u r n d e r n i e r ;
26 g
(la methode´ getDernierElement pourra etreˆ reutilis´ee´ avec profit dans concatener pour sim-
plifier son ecriture)´.
Suppression de la premiere` occurrence d’un el´ement´
Cette operation,´ realis´ee´ par la methode´ retirerPremiereOccurrence, elimine´ de la liste la premiere` apparition de l’el´ement´ donne´ en parametre` (s’il existe). On distingue comme prec´edemment´ les cas ou` la cellule modifiee´ est la premiere` et les autres
La suppression d’une cellule de la liste se fait de la maniere` suivante (voir la figure 14.3) :
– si la cellule est la premiere` de la liste, la nouvelle liste sera celle qui commence avec la seconde cellule.
– sinon la cellule a un pred´ecesseur´ ; pour eliminer´ la cellule il faut la “court-circuiter”, en mo-difiant la variable suivant du pred´ecesseur´ pour qu’elle pointe vers la memeˆ chose que la variable suivant de la cellule.