Théorie 4.2: liste chaînée simple #

• Une liste chaînée utilise des pointeurs (références), p.ex:

• Chaque noeud ci-haut est un objet qui contient une valeur

• Pour obtenir le prochain élément, on suit la référence (la flèche)

• Inconvénient:

  • il faut faire une boucle pour obtenir un élément de la liste

• Avantages:

  • l’insertion/retrait au début est efficace
  • on ne consomme pas d’espace mémoire en trop

Exemple: ajouts dans liste chaînée simple #

liste // []
liste.add('a') // [a]
liste.add('b') // [a,b]
liste.add('c') // [a,b,c]

Liste chaînée simple en Java #

• Il faut une classe pour représenter un élément:
  • l’élément contient la valeur et un pointeur vers l’élément suivant

public class ElementChaineSimple<E> {
	
	private E valeur;

	private ElementChaineSimple<E> suivant = null;

	// [...]
	
	public void insererApres(E e) {

		ElementChaineSimple<E> nouveau = new ElementChaineSimple<E>(e);
		
		if(this.suivant != null) {
			nouveau.setSuivant(this.suivant);
		}
		
		this.suivant = nouveau;
	}

	// [...]
}

• Et une classe pour la liste:
  • on mémorise la tête et la taille

public class ListeChaineeSimple<E extends Object> extends ListeJava<E> {
	
	private int taille = 0;
	private ElementChaineSimple<E> tete = new ElementChaineSimple<E>();

	// [...]
	
	private ElementChaineSimple<E> atteindreElement(int position) {
		ElementChaineSimple<E> element = tete;
		
		for(int i = 0; i < position; i++) {
			if(element != null) {
				element = element.suivant();
			}
		}

		return element;
	}

	@Override
	public void set(int position, E e) {
		ElementChaineSimple<E> element = atteindreElement(position);
		
		element.set(e);
	}

	// [...]
}

• Pour modifier un élément, il d’abord le trouver avec une boucle