Structures de Données

2005/2006

Structures de Données

Structures linéaires

Listes chaînées

Listes 2

Listes

Définition

Une liste est une séquence finie d’éléments

Les éléments sont repérés selon leur rang

Il existe une relation d’ordre sur le rang des éléments

• Le rang du premier élément est 1, le rang du second est 2, …

L’ajout et la suppression d’un élément peut se faire à n’importe quel rang valide de la liste

Listes 3

Listes : Cellule

La cellule est la composante principale d’une liste

Une liste est un ensemble de cellules (éléments)

chaînées entre elles à l’aide de liens

Une Cellule est une structure qui comporte deux

parties :

• Partie contenant les informations sur l’élément

représenté par la cellule

• Un lien vers la cellule suivante

Listes 4

Listes : Cellule

Le champ infos représente une ou plusieurs

données de type quelconque

Le champ suivant représente la référence de la

cellule suivante

infos suivant

Cellule

Listes 5

Listes chaînée : schéma

La liste vide est représentée par un trait en diagonal

La dernière cellule pointe (a un lien) vers une liste vide

Liste chaînée

infos suivant infos suivant infos suivant

tête cellule

têteListe vide

Listes 6

Listes

Une liste est définie récursivement :Une liste est : • Soit une liste vide

• Soit une liste avec une seule cellule liée à une liste

tête contient la référence de la première cellule qui contient la référence de la cellule suivante, …

En Java, null désigne la liste vide

Définir une classe Cellule

Définir une classe Liste

Listes 7

Listes : définition récursive

Une liste est : • Soit une liste vide

• Soit composée d’une cellule (la première)

chaînée à une liste

Cette définition est très importante, utilisée dans les

opérations récursives sur les listes

Liste chaînée

infos suivant infos suivant infos suivant

tête

cellule

têteListe vide

Listes 8

Listes : structure d’une Cellule

Données :• Un champ (ou plusieurs) infos de type quelconque :

– primitif– ou structure (objet)

• Un champ (suivant) référence d'une autre Cellule

Opérations :• setSuivant : modifie la référence suivant• getSuivant : retourne la référence suivant• getInfo : retourne le champ infos• afficheInfo : affiche le champ Infos• …

Listes 9

Listes : la classe Cellule

classe CelluleDonnées: infos : typeElement

suivant : CelluleMéthodes :

procédure setSuivant (donnée c : Cellule)//pré-condition ://post- condition : le champ suivant est modifié//spécification : modifie le champ suivant en lui affectant le

paramètre cfinproc

fonction getSuivant () retourne Cellule //pré-condition ://post- condition : //spécification : retourne la référence du suivant

finfonc

Listes 10

Listes : la classe Cellule

fonction getInfo () retourne typeElement //pré-condition :

//post- condition :

//spécification : retourne la donnée infosfinfonc

procédure afficheInfo()//pré-condition :

//post- condition :

//spécification : affiche les données de la classe

finprocclasse Cellule

Rajouter d’autres méthodes si nécessaire

Listes 11

Listes : structure d’une liste

Données :• Un champ tête de type Cellule

Opérations :• ajoutTete

• supprimeTete

• ListeVide : retourne vrai si la liste est vide

• afficheListe : affiche les éléments de la liste

• …

Listes 12

La classe Liste

classe ListeDonnées: tete : CelluleMéthodes : //quelques opérations

procédure ajoutTete(donnée c : Cellule)//pré-condition ://post- condition : une nouvelle cellule ajoutée, tête

modifiée//spécification : ajoute la cellule c en tête de liste

finprocprocédure supprimeTete()

//pré-condition : liste non vide//post- condition : une cellule supprimée, tête modifiée//spécification : supprime la cellule en tête de liste

finproc

Listes 13

La classe Liste

fonction listeVide() retourne booléen //pré-condition :

//post- condition :

//spécification : retourne vrai si la liste est vide, faux sinon

finfonc

procédure afficheListe()//pré-condition :

//post- condition :

//spécification : affiche les éléments de la liste

finproc

classe Liste

Rajouter d’autres méthodes si nécessaire

Listes 14

Listes en Java : classe Cellule

class Cellule {

private typeElement infos;private Cellule suivant;

public Cellule (typeElement e, Cellule c) // constructeur{

infos = e;suivant = c;

} public void setSuivant(Cellule c) {

suivant = c;}

public Cellule getSuivant() {

return suivant;}

Listes 15


public void setInfo(typeElement e) {

infos = e; }

public typeElement getInfo() {

return infos; }

public void afficheInfo() {

System.out.println(infos); }

}//class Cellule

D'autres méthodes peuvent être rajoutées selon le besoin

Listes 16


Accès aux champs d'une cellule : • Seules les méthodes de la classe Cellule peuvent

accéder aux données

Cellule cel;cel

infos suivant

4cel = new Cellule(4, null);

System.out.println(cel.infos);

System.out.println(cel.getInfo());

cel.infos = 11;

cel.setInfo(11);

Listes 17

La classe Liste en Java

class Liste {

private Cellule tete;

public Liste() // constructeur{

tete = null; //à sa création une liste est vide}

public boolean listeVide() {

return tete==null;}

public void ajoutTete(typeElement e) {

Cellule c = new Cellule(e, tete);tete = c;

}

Listes 18

La classe Liste en Java

public void supprimeTete() {

assert (!listeVide()); tete = tete.getSuivant();

}

public void afficheListe() {

Cellule tmp = tete; System.out.println("affichage liste : ");

while(tmp != null) {

tmp.afficheInfo();tmp = tmp.getSuivant();

} }

}//class Liste

D'autres méthodes peuvent être rajoutées selon le besoin

Listes 19

Classe Liste : ajout en tête

Dans la suite : typeElement = int

Ajout en tête : ajouter 3

li (tete)Liste li = new Liste();

infos suivant

3

tete

1) cel = new Cellule(3, tête);

2) tete = cel;

infos suivant

3

cel

ajoutTete(3);

2 étapes :

Listes 20

Classe Liste : ajout en tête

Ajout en tête : ajouter 36

cel = new Cellule(36, tete);

tete = cel;

suivantinfos

36

cel

infos suivant

3

tête

infos suivant

36

tete

infos suivant

3

Listes 21

Classe Liste : supprime en tête

supprimeTete();

tete = tete.getSuivant();

infos suivant

36

tete

infos suivant

3

infos suivant

3

tete

sera rendu au système

par le ramasse-miettes

infos suivant

36

Listes 22

Classe Liste : supprime en tête

supprimeTete();

infos suivant

3

tete

tete = tete.getSuivant();tete

infos suivant

3

sera rendu au système

par le ramasse-miettes

Listes 23

Listes : manipulation

Le constructeur sert à créer un objet Liste et

à l’initialiser à vide (null)

Les deux méthodes :

ajout en tête

supprime en tête

sont très utiles dans beaucoup d’opérations sur

les listes

Listes 24

Listes : exemple d'utilisation

//TestListe.java, typeElement = intclass TestListe{ public static void main(String[]args) {

Liste li = new Liste(); //création d'une liste videSystem.out.println("--- test liste ---");for(int i=1 ;i<=5; i++)

li.ajoutTete(i);li.afficheListe();li.supprimeTete();li.afficheListe();li.supprimeTete();li.afficheListe();

}

}//class TestListe

Listes 25

Listes : exemple d'utilisation

Copier un tableau dans une liste chaînée :

class CopieTableau{ public static void main(String[]args) {

int [] t = new int[10];Liste li = new Liste(); //création d'une liste videfor(int i=0 ;i<10; i++) t[i] = i*2;for(int i=9 ;i>0; i--)

li.ajoutTete(t[i]);li.afficheListe();

}

}//class CopieTableau

Listes 26

Listes : application (Piles)

Les piles peuvent être implantées à l'aide de listes chaînées

Données

tête (correspond à sommet)

tête (sommet)

Listes 27

Listes : application (Piles)

Méthodes :

• empiler : ajout en tête

• dépiler : supprime en tête

• sommet : première cellule

• estVide : teste si la liste est vide (pile vide)

Avantage : • Pas de pile pleine : pas de tailleMax à priori

Listes 28

Listes : application (Files d’attente)

Les files peuvent être implantées à l'aide de listes chaînéesDonnées

tête : référence de la première cellulequeue : référence de la dernière cellule

têtequeue

Listes 29

Listes : application (Files d’attente)

Méthodes :

• enfiler : ajout en queue

• défiler : supprime en tête

• premier : première cellule

• estVide : teste si la liste est vide (file vide)

Avantage : • Pas de file pleine : pas de tailleMax à priori

Listes 30

Listes : parcours récursif

Premier parcours : dans l'ordre• Traiter la cellule courante (première)

• Parcourir la sous-liste qui reste

Ajouter 2 méthodes à la classe Liste

• parcoursRec(Cellule c) : méthode privée qui permet

de passer d'une cellule à une autre grâce à la

récursivité

• parcours() : qui appelle la méthode parcoursRec en

lui passant la tête de la liste

Listes 31


Premier parcours : dans l'ordreprivate void parcoursRec(Cellule c){

if(c != null){

c.afficheInfo(); //traiter infos, ici c'est l'affichageparcoursRec(c.getSuivant());

}}

public void parcours(){

Cellule c = tete;parcoursRec(c);

}

Listes 32


Second parcours : ordre inverse• Parcourir la sous-liste (sans la première cellule)

• Traiter la cellule courante (première)

Ajouter 2 méthodes à la classe Liste

• parcoursRecInv(Cellule c) : méthode privée qui

permet de passer d'une cellule à une autre grâce à la

récursivité

• parcours2() : qui appelle la méthode parcoursRecInv

en lui passant la tête de la liste

Listes 33


Second parcours : ordre inverseprivate void parcoursRecInv(Cellule c){

if(c != null){

parcoursRecInv(c.getSuivant());c.afficheInfo(); //traiter infos, ici c'est l'affichage

}}public void parcours2(){

Cellule c = tete;parcoursRecInv(c);

}

Listes 34


Remarque

Il est plus propre de définir les méthodes parcoursRec et

parcoursRecInv comme privées en utilisant le mot-clé

private.

Cela veut dire que ces méthodes sont accessibles uniquement

par les méthodes de la classe (notamment les méthodes

parcours et parcours2)

private void parcourRec(Cellule c)

private void parcoursRecInv(Cellule c)

Listes 35

Listes : parcours itératif

Parcours itératif : pas besoin de méthode privée

Parcours dans l'ordre

public void parcoursIter() {

Cellule tmp = tete;while(tmp != null) {

tmp.afficheInfo();tmp = tmp.getSuivant();

} }

Listes 36

Listes : exercices

Qu'affiche la procédure P1P1 et P sont des méthodes dans la classe ListeOn suppose que la liste contient dans l'ordre les éléments 1, 2 et 3

public void P1(){

P(tete);}private void P(Cellule c){

if (c!=null){

c.afficheInfo();P(c.getSuivant());c.afficheInfo();

}}

affichage : 1 2 3 3 2 1

Listes 37

Listes : exercices

Qu'affiche la procédure P1P1 et P sont des méthodes dans la classe ListeOn suppose que la liste contient dans l'ordre les éléments 1, 2 et 3

public void P1(){

P(tete);}private void P(Cellule c){

if (c!=null){P(c.getSuivant());c.afficheInfo();P(c.getSuivant());

}}

affichage : 3 2 3 1 3 2 3

Listes 38

Listes : quelques opérations

Nombre d'occurrences d'un élément dans une liste On définit la méthode dans la classe Liste

Version itérative

public int nbOccurrences(int val) //typeElement = int{ int nb =0; Cellule c =tete;

while (c!=null){if (val == c.getInfo()) nb++;c = c.getSuivant();

}return nb;

}

Listes 39


Nombre d'occurrences d'un élément dans une liste

Version récursive

public int nbOccurrences(int val) //typeElement = int{

return nbOcc(val, tete);}private int nbOcc (int val, Cellule c){

if (c==null) return 0;else if (val == c.getInfo())

return 1 + nbOcc(val, c.getSuivant());else return nbOcc(val, c.getSuivant());

}

Listes 40


Accès par position : accès au kième position• Données : un entier positif k et une liste• Résultat : la référence de kième cellule• Spécification : retourne la référence de la kième

cellule si elle existe, null sinon

Exemple : k=3

d3

tête

6 5 5

adrK

Listes 41


Accès par position : version itérative

public Cellule adresseKieme(int k) {

int i = 1; Cellule c = tete;

while (c!=null && i<k){

i++;c = c.getSuivant();

}return c;

}

Listes 42


Accès par position : version récursivepublic Cellule adresseKieme(int k){

Cellule c = tete;return adresseKiemeRec(k, c);

}

private Cellule adresseKiemeRec(int k, Cellule c) {

if(c==null) return null;else if (k==1) return c;

elsereturn adresseKiemeRec(k-1,c.getSuivant());

}

Listes 43


Accès par valeur : accès à la cellule contenant une valeur donnée

• Données : une valeur val et une liste• Résultat : la référence de la cellule contenant val• Spécification : retourne la référence de la cellule

contenant la première occurrence de val, si val n’est pas dans la liste elle retourne null

Exemple : val=5

d3

tête

6 5 5

adrV

Listes 44


Accès par valeur : version itérativepublic Cellule adresseValeur(int val) {

int i = 1; Cellule c = tete;

while (c != null){

if(val == c.getInfo())return c;

c = c.getSuivant();}return null;

}

Listes 45


Accès par valeur : version récursivepublic Cellule adresseValeur(int val){

Cellule c = tete;return adresseValeurRec(val, c);

}

private Cellule adresseValeurRec(int val, Cellule c) {

if(c==null) return null;else if (val == c.getInfo()) return c;

elsereturn adresseValeurRec(val, c.getSuivant());

}

Listes 46


Insertion en fin de liste• Données : une valeur val et une liste• Résultat : une cellule contenant val insérée en fin de liste• Spécification : insertion d’une valeur donnée val en fin de liste

Exemple : val=11

d3

tête

6 5 5

dernier

d3

tête

6 5 5

dernier p

11

11

p

Listes 47


Insertion en fin de liste : version itérative1. Calculer la référence du dernier

2. ajouter après dernier

public void ajoutFin(int val) {

Cellule der = tete, p;if (der != null)

while (der.getSuivant() != null)der = der.getSuivant();

if(der == null) ajoutTete(val); //cas liste videelse {

p = new Cellule(val, null); der.setSuivant(p);

}}

Listes 48


Insertion d’une valeur à la kième position • Données : une valeur val, un entier positif valide k et une liste• Résultat : une cellule contenant val insérée à la position k• Spécification : insertion d’une valeur donnée val à la kième place

Exemple : val=16, k=4

d3

tête

6 5 5

16

p

prec

k-1

Listes 49


Insertion d’une valeur à la kième position

K doit être valide : 0 < k ≤ nombre d’éléments+1

version itérative

1.Calculer la référence de la (k-1)ième cellule

2. ajouter après la (k-1)ième cellule

Listes 50


Insertion d’une valeur à la kième position public void ajoutKieme(int val, int k) {

Cellule prec, p, c;if (k==1) // cas particulier en première position

ajoutTete(val);else {

prec = adresseKieme(k-1);if(prec != null) { p = prec.getSuivant(); c = new Cellule(val, p); prec.setSuivant(c); }else System.out.println(" ajout impossible " );

}}

Listes 51


Suppression du kième élément (cellule)• Données : un entier positif valide k et une liste

• Résultat : la kième cellule supprimée de la liste

• Spécification : suppression de la kième cellule

Exemple : k=4

d3

tête

6 5 516

prec

Listes 52


Suppression du kième élément (cellule)

K doit être valide : 0 < k ≤ nombre d’éléments

version itérative

1.Calculer la référence de la (k-1)ième cellule

2. effectuer le lien (chaînage) entre la (k-1)ième

cellule et la (k+1)ième cellule

Listes 53


Suppression du kième élément (cellule)public void supprimeKieme(int k) {

Cellule prec, p ,s;if (k==1) // cas particulier en première position

supprimeTete();else {

prec = adresseKieme(k-1);if(prec != null && prec.getSuivant() != null) { p = prec.getSuivant(); s= p.getSuivant(); prec.setSuivant(s); }else System.out.println("suppression impossible");

}}

Listes 54


Suppression de la première occurrence d’une valeur donnée val

• Données : une valeur val et une liste

• Résultat : la liste avec une cellule supprimée

• Spécification : suppression de la première cellule contenant val si elle existe

Exemple : val = 5

d3

tête

6 5 516

prec

Listes 55


Suppression de la première occurrence (la

première cellule contenant) d’une valeur

donnée val

version itérative

1.Calculer la référence de la cellule précédente

2. effectuer le lien (chaînage) entre la cellule

précédente et la cellule suivante

Listes 56


Suppression de la première occurrence d’une valeur val

public void supprimeVal(int val) {

Cellule prec=null, p = tete, s;while(p!=null && val != p.getInfo()) {

prec = p; p = p.getSuivant();}

if(p!=null) { //la valeur existe if(prec == null) // la première cellule à supprimer

supprimeTete(); else{

s=p.getSuivant(); prec.setSuivant(s); }

}else System.out.println("suppression impossible");

}

Listes 57

Listes

Listes chaînées particulières

• Listes bidirectionnelles

• Listes circulaires

Listes 58

Listes chaînées bidirectionnelles

Chaque cellule possède deux références• Une vers la cellule suivante

• Une vers la cellule précédenteLe premier n'a pas de précédentLe dernier n'a pas de suivant

tête

5 16 5

prec prec prec precsuiv suiv suiv

6

Listes 59

Listes bidirectionnelles : Cellule

Structure d'une Cellule : Données :• Un champ (ou plusieurs) infos de type quelconque :

– primitif– ou structure (objet)

• Un champ (suivant) référence d’une autre Cellule• Un champ (précédent) référence d’une autre Cellule

Opérations :• setSuivant, setPrecedent• getSuivant, getPrecedent• getInfo : retourne le champs infos• afficheInfo : affiche le champ Infos• …

Listes 60


classe CelluleBiDonnées: infos : typeElement

suivant : CelluleBi precedent : CelluleBi

Méthodes : procédure setSuivant (donnée c : CelluleBi)

//pré-condition ://post- condition : le champ suivant est modifié//spécification : modifie le champ suivant en lui affectant

le paramètre cfinprocfonction getSuivant () retourne CelluleBi

//pré-condition ://post- condition : //spécification : retourne la référence du suivant

finfonc

Listes 61


procédure setPrecedent (donnée c : CelluleBi)//pré-condition :

//post- condition : le champ precedent est modifié

//spécification : modifie le champ precedent en lui affectant le paramètre c

finproc

fonction getPrecedent () retourne CelluleBi //pré-condition :

//post- condition : //spécification : retourne la référence du precedent

finfonc

Listes 62


fonction getInfo () retourne typeElement //pré-condition :

//post- condition : //spécification : retourne la donnée infos

finfoncprocédure afficheInfo()

//pré-condition :

//post- condition :

//spécification : affiche les données de la classe

finproc

classe CelluleBiRajouter d’autres méthodes si nécessaire

Listes 63


class CelluleBi {

private typeElement infos;private CelluleBi suivant;private CelluleBi precedent;public CelluleBi (typeElement e, CelluleBi s, CelluleBi p) // constructeur

{infos = e;suivant = s;precedent = p;

}…

}//class CelluleBi

Listes 64

Listes bidirectionnelles

classe ListeBiDirectDonnées: tete : CelluleBi

Méthodes : //quelques opérationsprocédure ajoutTete(donnée c : CelluleBi)

procédure supprimeTete()

fonction listeVide () retourne booléen

Procédure afficheListe()

…

finClasse ListeBiDirect

Listes 65


UtilisationLes listes chaînées bidirectionnelles sont utilisées

uniquement dans le cas où on a besoin d’effectuer souvent des retour arrière.

ExercicesEn considérant une liste chaînée bidirectionnelle, On

peut réécrire les différents opérations vues sur les listes chaînées simples

Listes 66


class ListeBiDirect {

private CelluleBi tete;

public ListeBiDirect() // constructeur{

tete = null; //à sa création une liste est vide}


…}


…}

…}//class ListeBiDirect

Listes 67

Listes bidirectionnelles : opérations

Ajout en tête : ajouter la valeur 31. Créer une nouvelle cellule2. Effectuer le chaînage en tête

tête

5 16 5


6

tête

5 16 5


6

prec suiv

3

Listes 68



CelluleBi c = new CelluleBi(e, tete, null);if(tete != null)

tete.setPrecedent(c);tete = c;

}Le test tete!=null est nécessaire pour traiter le cas où la liste est vide

Listes 69


supprimer en tête :

tête

5 16 5


6

prec suiv

3

tête

5 16 5


6

prec suiv

3

Listes 70



if(tete!=null){tete= tete.getSuivant();if(tete != null)

tete.setPrecedent(null);}

}

Listes 71

Listes chaînées circulaires

Représentation

• même type que pour les listes chaînées

• Le dernier élément pointe sur le premier

tête

suiv

6suiv

5suiv

16suiv

5

Listes 72

Listes chaînées circulaires : opérations

Affichage : liste simple

void afficheListe() {

Cellule c;if(tete != null) {//liste non vide

c = tete;do {

c.afficheInfo(); c = c.getSuivant();

} while (c!=null);

}}

Affichage : circulaire

void afficheListe() {

Cellule c;if(tete != null) {//liste non vide

c = tete;do {

c.afficheInfo(); c = c.getSuivant();

} while (c!=tete);

}}

Listes 73


Affichage : version récursivepublic void afficheListe(){

Cellule c =tete;afficheListeRec(c);

}private void afficheListeRec(Cellule c) {

if(tete != null) {//liste non videc.afficheInfo();if(c.getSuivant != tete) afficheListeRec(c.getSuivant());

}}

Listes 74


Ajout en tête : utiliser une référence auxiliaire der

1. Création d’une nouvelle cellule

2. Remplissage des données

3. Chaînage Inconvénient : parcourir la liste pour récupérer der

tête

6 5 16 5

der

Listes 75


Ajout en tête : ajouter la valeur 3tête

6 5 16 5

der

tête

6 5 16 5

der

3

p

Listes 76


Ajout en tête : • Inconvénient : parcourir la liste pour récupérer der

Solution : tête pointe sur la dernière cellule

Conséquence : ajout en tête et en fin de liste plus efficace

6 5 16 5

tete

Listes 77

Listes chaînées vs tableaux

Représentation chaînée : Listes

Représentation contiguë : tableaux

En pratique :

On utilise souvent des structures mixtes

composées de listes et de tableaux

Listes 78

Listes chaînées vs tableaux

Listes chaînées : • Avantages : taille peut évoluer (limitée par

l’espace mémoire)• Inconvénients :

– plus encombrants– accès à un élément plus long

Tableaux : • Avantage : accès plus rapide• Inconvénient : limité par la taille spécifiée au

départ

Listes 79

La classe LinkedList en Java

La structure Liste est implémentée en Java

sous le nom LinkedList

La classe LinkedList permet de manipuler

des listes de type Object

Le constructeur LinkedList () crée une liste

vide

Listes 80

La classe LinkedList en Java

Quelques méthodes de la classe LinkedList• void add(int index, Object o) : ajout à la position index

• void addFirst(Object o) : ajout au début

• void addLast(Object o) : ajout en fin

• Object get(int index) : retourne l’objet à la position index

• Object getFirst() : retourne l’objet en tête

• Object getLast() : retourne l’objet en fin

• Object remove(int index) : supprime l’objet à la position index

• Object removeFirst() : supprime et retourne le premier élément

• Object removeLast() : supprime et retourne le dernier élément

• Object set(int index, Object o) : remplace l’objet à la position index par

celui passé en paramètre et retourne l’objet remplacé

Listes 81

La classe LinkedList en Java : exemple

class TestLinkedList{ public static void main(String[]args) {

LinkedList li;Integer n;System.out.println("---- test LinkedList -------");li = new LinkedList();for(int i=1 ;i<=10; i++) { n = new Integer(i*10); li.addFirst(n);}

//le parcours se fait à l'aide de Iterator qui contient les méthode hasNext et nextIterator it = li.iterator();System.out.println("---- Iterator -------");

while(it.hasNext()) { System.out.println(it.next());}

Listes 82

LinkedList : parcours

n = (Integer) li.remove(3); n = (Integer) li.removeFirst(); n = (Integer) li.removeLast(); n = (Integer) li.set(2, n);

System.out.println("---- Apres modif-------");

it = li.iterator();while(it.hasNext()) { System.out.println(it.next());}

//autre façon de parcourir

System.out.println("---- avec size-------");

for(int i=0; i<li.size(); i++) System.out.println(li.get(i));

}}//class TestLinkedList

Listes 83

La classe LinkedList en Java 5

La structure Liste est implémentée en Java

sous le nom LinkedList<E>

La classe LinkedList<E> est une classe

générique qui permet de manipuler des

listes de type E

Le constructeur LinkedList () crée une liste

vide

Listes 84

La classe LinkedList en Java 5

Quelques méthodes de la classe LinkedList<E> • void add(int index, E ele) : ajout à la position index

• void addFirst(E ele) : ajout au début

• void addLast(E ele) : ajout en fin

• E get(int index) : retourne l’élément à la position index

• E getFirst() : retourne l’élément en tête

• E getLast() : retourne l’élément en fin

• E remove(int index) : supprime l’élément à la position index

• E removeFirst() : supprime et retourne le premier élément

• E removeLast() : supprime et retourne le dernier élément

• E set(int index, E ele) : remplace l’élément à la position index par celui

passé en paramètre et retourne l’élément remplacé

Listes 85

La classe LinkedList en Java : exemple

class TestLinkedList5{ public static void main(String[]args) {

LinkedList<Integer> li;Integer n;System.out.println("---- test LinkedList -------");

li = new LinkedList<Integer>();for(int i=1 ;i<=10; i++) { n = new Integer(i*10); li.addFirst(n);}

//le parcours se fait à l'aide de Iterator qui contient les méthode hasNext et nextIterator it = li.iterator();System.out.println("---- Iterator -------");

while(it.hasNext()) { System.out.println(it.next());}

Listes 86

LinkedList : parcours

n = li.remove(3); n = li.removeFirst(); n = li.removeLast(); n = li.set(2, n);

System.out.println("---- affichage avec For-------");

//autre façon de parcourir avec For

for(Integer i : li) {

System.out.println(i);

}}}//class TestLinkedList5

Documents

Structures de Données