// Object contenant l'information generale d'une liste // Ici, liste chainee. // Une liste contient des noeuds (class noeud). public class ListeChaine { // 1er noeud de la chaine de noeuds // null si liste vide private Noeud first; // taille de la liste private int taille; // ATTRIBUT REDONDANT!!!!!!! DOIT ETRE COHERENT! /// SI ON APPELLE SOUVENT TAILLE, ON PEUT FAIRE DE LA REDONDANCE // -> REDONDANCE pour la performance seulement!!!!!!!!!!!!o private Noeud last; // dernier noeud de la liste! public int GetTaille() { return taille; } // Contructeur pour une nouvelle liste vide public ListeChaine () { this.first=null; taille=0; } // Affiche le contenu d'une liste public void Affiche () { Noeud n; System.out.print("{"); for(n=this.first;n!=null;n=n.next) { System.out.print(n.e); if( n.next!=null ) System.out.print(","); } System.out.println("}"); } // si q est null, on retourne le dernier de la liste public Noeud TrouvePrecedent(Noeud q) { Noeud n; for(n=this.first;n!=null;n=n.next) if( n.next==q ) return n; return null; } // Ajoute un element au DEBUT de la liste public void AjouteDebut(int e) { // cree un nouveau noeud Noeud z = new Noeud(e); // z pointe sur le debut de la liste z.next=this.first; // Le debut de la liste est maintenant z this.first=z; taille++; } public void AjouteDebut(Noeud z) { // z pointe sur le debut de la liste z.next=this.first; // Le debut de la liste est maintenant z this.first=z; taille++; } // Retourne la taille de la liste public int Taille() { Noeud n; int nb; // nombre de noeuds dans la liste nb=0; for(n=this.first;n!=null;n=n.next) nb++; return nb; } // Trouve un noeud qui contient l'element e // retourne null si ne trouve pas public Noeud TrouveElement(int e) { Noeud n; for(n=this.first;n!=null;n=n.next) { if( n.e == e ) return n; } return null; } // Insere un element e apres le noeud n // teste si le noeud n est null (dans ce cas, ne fait rien) public void InsereApres(Noeud n,int e) { if( n==null ) return; // cree et initialise un nouveau noeud Noeud z = new Noeud(e); // Le suivant de ce noeud est la suite de n z.next=n.next; // Le suivant de n est maintenant z n.next=z; } public void InsereAvant(Noeud n,int e) { if( n==null ) return; if( n==this.first ) { AjouteDebut(e); }else{ Noeud p = TrouvePrecedent(n);// trouve le precedent de n InsereApres(p,e); } } public Noeud TrouveFin() { return TrouvePrecedent(null); } public void ElimineDebut() { Noeud p = this.first; if( p!=null ) this.first=p.next; taille--; } public void ElimineFin() { // version1 Noeud n = TrouveFin(); Elimine(n); // version2 Elimine(TrouveFin()); } public void Elimine(Noeud n) { if( n==null ) return; if( this.first==n ) { // n est le premier de la liste ElimineDebut(); }else{ // n est le second ou + dans la liste, ou nul part... Noeud p = TrouvePrecedent(n); if( p!=null ) { p.next=n.next; } taille--; } } public static void Transfert(ListeChaine A, ListeChaine B, Noeud p) { // Le noeud P est dans A, on veut l'envoyer au debut de B // elimine p de A A.Elimine(p); // ajoute p dans B B.AjouteDebut(p.e); } // On ajoute un main ici seulement pour les tests public static void main(String arg[]) { Noeud n; // Cree une nouvelle liste vide ListeChaine T = new ListeChaine(); // Imprime la liste T.Affiche(); T.AjouteDebut(1); T.AjouteDebut(2); T.AjouteDebut(3); T.Affiche(); System.out.println("La tailles est "+T.Taille()); n=T.TrouveElement(2); T.InsereApres(n,999); T.Affiche(); } }