L'Altruiste : Le langage Java - La classe <i>LinkedList</i>

La classe LinkedList permet de créer des listes chaînées pouvant être utilisées comme des piles ou des files d'attente.

La classe LinkedList implémente l'interface List et étend la classe abstraite AbstractSequentialList.

Les listes chaînées acceptent tous types d'objets, y compris la valeur null.

Il existe deux constructeurs dans la classe LinkedList, destinées à instancier et initialiser des listes chaînées. Le constructeur par défaut, permet de créer un objet LinkedList vide, tandis que l'autre initialise l'objet créé, en le remplissant avec les éléments contenus dans une collection passée en argument.

// par défaut
LinkedList liste = new LinkedList();
// initialisation avec les éléments d'une collection fournie
Collection collection = new Vector();
collection.add(objet);
// ...
LinkedList liste = new LinkedList(collection);

Les liste pouvant se comporter à l'instar des piles LIFO (Last In First Out) ou des files d'attente FIFO (First In First Out), la classe LinkedList met à disposition de nombreuses méthodes d'extraction ou d'ajout, conçues spécifiquement pour soit l'une et l'autre des listes.

Une pile (stack) peut se servir des méthodes add() et plus spécifiquement addLast(), afin d'ajouter un objet à la fin de la liste. L'extraction et la suppression du dernier élément se réalisent en faisant appel à la méthode removeLast(). De cette manière, le fonctionnement de la liste chaînée peut s'apparenter à celui d'une pile.

import java.util.LinkedList;

public class Pile {
  private LinkedList liste;

  public Pile() {
    liste = new LinkedList();
    }

  public boolean empty(){
    return liste.isEmpty();
  }
  
  public Object peek(){
    return liste.getFirst();
  }
  
  public Object pop() { 
    return liste.removeFirst(); 
  }
  
  public void push(Object o) {
    liste.addFirst(o);
  }

  public int search(Object o) {
    int i = liste.lastIndexOf(o);
    if (i >= 0)
      return liste.size() - i;
    return -1;
  }
  
  public int size(){
    return liste.size();
  }
}

Une file d'attente (queue) peut se servir de la méthode addFirst() pour ajouter un objet au sommet de la liste. L'extraction et la suppression des éléments s'effectuent par le truchement de la méthode removeFirst(). De cette manière, le fonctionnement de la liste chaînée peut s'apparenter à celui d'une file d'attente.

import java.util.LinkedList;

public class FileAttente {
  private LinkedList liste;

  public FileAttente() {
    this.liste = new LinkedList();
  }

  public boolean isEmpty() {
    return liste.isEmpty();
  }

  public void put(Object o) {
    liste.addFirst(o);
  }

  public Object get() {
    return liste.removeLast();
  }
  
  public int size(){
    return liste.size();
  }
}

Une double file d'attente (deque) se construit à partir des méthodes addFirst() et addLast() pour ajouter des éléments au sommet et à la fin de la liste. L'extraction et la suppression des éléments aux extrémités s'accomplissent par les méthodes removeFirst() et removeLast().

import java.util.LinkedList;
import java.util.NoSuchElementException;

public class FileDouble {
    private LinkedList liste;

    public FileDouble() {
      liste = new LinkedList();
    }

  public Object peekFirst(){
    if(liste.isEmpty())
      throw null;
    return liste.getFirst();
  }

  public Object peekLast(){
    if(liste.isEmpty())
      throw null; 
    return liste.getLast();
  }

  public void pushFirst(Object o){
    liste.addFirst(o);
  }

  public void pushLast(Object o){
    liste.addLast(o);
  }

  public Object popFirst(){
    if(liste.isEmpty())
      throw new NoSuchElementException(); 
    return liste.removeFirst();
  }

  public Object popLast(){
    if(liste.isEmpty())
      throw new NoSuchElementException(); 
    return liste.removeLast();
  }

  public int searchFirst(Object o){
    return liste.indexOf(o);
  }

  public int searchLast(Object o){
    int i = liste.lastIndexOf(o);
    if (i >= 0)
      return liste.size() - i;
    return -1;
  }

  public boolean isEmpty(){
    return liste.isEmpty();
  }
  
  public int size(){
    return liste.size();
  }
}

Toutes les autres opérations sur les listes chaînées sont identiques à celles courament pratiquées sur les collections List. Par exemple, l'itération des éléments d'une objet LinkedList peut s'effectuer par l'intermédiaire d'un itérateur (Iterator ou ListIterator), ou l'ajout et la suppression de groupes d'éléments à la fin ou à une position spécifiée de la liste, sont possibles grâce aux méthodes addAll() et removeAll().

Exemple [voir]

public class Programme {
  public static void main(String[] args) {
    Pile pile = new Pile();
    FileAttente file = new FileAttente();
    FileDouble filed = new FileDouble();

    pile.push(new Video("Voyage au bout de l'enfer", "Michael Cimino", 1978));
    pile.push(new Video("Le jour le plus long", "Ken Annakin", 1962));
    pile.push(new Video("Un pont trop loin", "Richard Attenborough", 1977));
    pile.push(new Video("Platoon", "Oliver Stone", 1986));
    pile.push(new Video("Full metal jacket", "Stanley Kubrik", 1987));
    pile.push(new Video("La ligne rouge", "Terrence Malick", 1998));
    pile.push(new Video("The patriot", "Roland Emmerich", 2000));
    pile.push(new Video("Outrages", "Brian De Palma", 1990));
    pile.push(new Video("Paris brûle-t-il ?", "René Clément", 1966));
    pile.push(new Video("Tora ! Tora ! Tora !", "Richard Fleischer", 1970));
    pile.push(new Video("Guerre et Paix", "King Vidor", 1956));
    pile.push(new Video("Apocalypse now", "Francis Ford Coppola", 1979));
    
    System.out.println("Pile (taille = " + pile.size() + ")");
    while(!pile.empty())
      System.out.println(pile.pop());
    System.out.println("Taille = " + pile.size() + "\n");
    
    file.put(new Video("Voyage au bout de l'enfer", "Michael Cimino", 1978));
    file.put(new Video("Le jour le plus long", "Ken Annakin", 1962));
    file.put(new Video("Un pont trop loin", "Richard Attenborough", 1977));
    file.put(new Video("Platoon", "Oliver Stone", 1986));
    file.put(new Video("Full metal jacket", "Stanley Kubrik", 1987));
    file.put(new Video("La ligne rouge", "Terrence Malick", 1998));
    file.put(new Video("The patriot", "Roland Emmerich", 2000));
    file.put(new Video("Outrages", "Brian De Palma", 1990));
    file.put(new Video("Paris brûle-t-il ?", "René Clément", 1966));
    file.put(new Video("Tora ! Tora ! Tora !", "Richard Fleischer", 1970));
    file.put(new Video("Guerre et Paix", "King Vidor", 1956));
    file.put(new Video("Apocalypse now", "Francis Ford Coppola", 1979));

    System.out.println("File d'attente (taille = " + file.size() + ")");
    while(!file.isEmpty())
      System.out.println(file.get());
    System.out.println("Taille = " + file.size() + "\n");

    filed.pushFirst(new Video("Voyage au bout de l'enfer", "Michael Cimino", 1978));
    filed.pushFirst(new Video("Le jour le plus long", "Ken Annakin", 1962));
    filed.pushFirst(new Video("Un pont trop loin", "Richard Attenborough", 1977));
    filed.pushFirst(new Video("Platoon", "Oliver Stone", 1986));
    filed.pushFirst(new Video("Full metal jacket", "Stanley Kubrik", 1987));
    filed.pushFirst(new Video("La ligne rouge", "Terrence Malick", 1998));
    filed.pushLast(new Video("The patriot", "Roland Emmerich", 2000));
    filed.pushLast(new Video("Outrages", "Brian De Palma", 1990));
    filed.pushLast(new Video("Paris brûle-t-il ?", "René Clément", 1966));
    filed.pushLast(new Video("Tora ! Tora ! Tora !", "Richard Fleischer", 1970));
    filed.pushLast(new Video("Guerre et Paix", "King Vidor", 1956));
    filed.pushFirst(new Video("Apocalypse now", "Francis Ford Coppola", 1979));
    
    System.out.println("File double (taille = " + filed.size() + ")");
    while(!filed.isEmpty())
      System.out.println("Premier : " + filed.popFirst()
                          + "\nDernier : " + filed.popLast());
    System.out.println("Taille = " + filed.size() + "\n");
        
  }
}

// Classe Video
import java.util.GregorianCalendar;
import java.util.Calendar;

public class Video implements Comparable {
  private String titre, realisateur;
  private int annee;
  
  public Video(){
    this("Inconnu", "Inconnu", 0);
  }
    public Video (String[] infos) {
      this(infos[0], infos[1], Integer.parseInt(infos[3]));
    }
    public Video (String titre, String realisateur){
      this(titre, realisateur, (new GregorianCalendar()).get(Calendar.YEAR));
    }
  public Video (String titre, String realisateur, String annee){
    this(titre, realisateur, Integer.parseInt(annee));
  }
  public Video (String titre, String realisateur, int annee){
    if (titre == null || realisateur == null)
      throw new NullPointerException();
    this.titre = titre;
    this.realisateur = realisateur;
    this.annee = annee;
  }
  
  public String obtenirTitre(){
    return this.titre;
  }
  public String obtenirRealisateur(){
    return this.realisateur;
  }
  public int obtenirAnnee(){
    return this.annee;
  }

  public void fournirTitre(String titre){
    this.titre = titre;
  }
  public void fournirRealisateur(String realisateur){
    this.realisateur = realisateur;
  }
  public void fournirAnnee(int annee){
    this.annee = annee;
  }
  
  public int hashCode(){
    return annee * titre.hashCode() + realisateur.hashCode();
  }
  
  public boolean equals(Object o){
    if(!(o instanceof Video))
      return false;
    Video v = (Video)o;
    if(this.hashCode() == v.hashCode())
      return true;
    return false;
  }
  
  public int compareTo(Object o){
    if(!(o instanceof Video))
      throw new ClassCastException();
    Video v = (Video)o;
    int comparaison;
    if((comparaison = titre.compareTo(v.obtenirTitre())) != 0)
      return  comparaison;
    else if((comparaison = realisateur.compareTo(v.obtenirRealisateur())) != 0)
      return comparaison;
    else
      return (new Integer(annee)).compareTo(new Integer(v.obtenirAnnee()));
  }
  
  public String toString(){
    StringBuffer res = new StringBuffer("[");
    res.append(titre);
    res.append(", ");
    res.append(realisateur);
    res.append(", ");
    res.append(annee);
    return res.append("]").toString();
  }
}