Exercice n°1

• Créez la classe Cell.java conformément au code ci-dessous (= celle donnée en TD).

public class Cell {

  public int value;
  public Cell next;

  public Cell(int value) {
    this.value = value;
    next = null;
  }
}

• Complétez les méthodes de la classe ListSimple.java donnée ci-dessous, en prenant comme base les méthodes données en TD.

public class ListSimple {

    public Cell head;
    public int size;

    public ListSimple() {
	head = null;
	size = 0;
    }

    public Cell find(int value) {
    }

    public Cell get(int index) {
    }

    public Cell append(int value) {
    }

    public Cell insert(int value, int index) {
    }

    public Cell replace(int value, int index) {
    }

    public Cell removeAt(int index) {
    }

    public Cell remove(int value) {
    }

    public void print() {
    }
}

• Un programme de test : si vous constatez que votre résultat est différent des commentaires, c'est que votre classe ListSimple est fausse.

class TestSimple {

    public static void main(String[] args) {

	ListSimple liste = new ListSimple();
	liste.append(20); // liste vide -> insertion en tête
	liste.insert(10,-5); // insertion en tête
	liste.insert(30,7); // insertion en fin
	liste.append(50); // ajout en fin
	liste.insert(40,3); // insertion en 3
	liste.print(); // affiche 10 20 30 40 50
	liste.remove(12); // ne fait rien
	liste.remove(10); // enlève la valeur 10 (la tête)
	liste.removeAt(-2); // ne fait rien
	liste.removeAt(22); // ne fait rien
	liste.removeAt(2); // enleve la valeur en 2 (i.e. 40)
	liste.print(); // affiche 20 30 50
	Cell c = liste.get(-1); // accès en dehors -> renvoie null
	if (c != null) {
	    System.out.println("pb with get()");
	}
	c = liste.get(99); // accès en dehors -> renvoie null
	if (c != null) {
	    System.out.println("pb with get()");
	}
	c = liste.find(99); // value inexsitante -> renvoie null
	if (c != null) {
	    System.out.println("pb with find()");
	}
	c = liste.find(20);
	if (c.value != 20) {
	    System.out.println("pb with find()");
	}
	c = liste.find(50);
	if (c.value != 50) {
	    System.out.println("pb with find()");
	}
    }
}

Exercice n°2

• Utiliser le canevas de code C à disposition sur cours-info pour faire la même chose que l'exercice 1, mais en C.

Exercice n°3

• On définit maintenant la classe CellDouble.java pour permettre de créer une liste doublement chaînée. Pour cela, on doit ajouter un attribut de type Cell appelé prev, qui référence la cellule précédente

public class CellDouble {

    public int value;
    public CellDouble prev;
    public CellDouble next;

    public CellDouble(int value) {
	this.value = value;
	prev = null;
	next = null;
    }
}

• On définit maintenant une classe ListDoubleCir.java qui permet de gérer une liste doublement chaînée ET circulaire.
• Cela implique qu'une cellule référence celle qui la précède et celle qui la suite mais aussi que la cellule de tête référence la dernière et inversement.
• En terme d'implémentation, cela veut dire que les attribut prev et next de toutes les cellules ne sont JAMAIS égaux à null. Par exemple, lors de l'insertion de la première cellule, ses attributs prev et next doivent référencer la cellule elle-même (donc this).
• Pour vous aider dans l'implémentation quelques remarques sont données en commentaires.

public class ListDoubleCirc {

    public CellDouble head;
    public int size;

    public ListDoubleCirc() {
	head = null;
	size = 0;
    }

    public CellDouble find(int value) {
	// quasi identique à l'exo 1, excepté le test d'arrêt
    }

    public CellDouble get(int index) {
	// pour éviter de tout parcourir, on peut tester si l'indice
        // est avant ou après la moitié de la liste. S'il est avant,
        // on explore la liste grâce à next, et sinon grâce à prev
    }

    public CellDouble append(int value) {
	// pas besoin de trouver la dernière cellule : on y a accès
	// grâce à prev de la tête. Seul cas particulier, la liste est vide
    }

    public CellDouble prepend(int value) {
	// pas compliqué : insertion en tête = insertion en fin
	// puis déplacement de la tête
    }

    public CellDouble insert(int value, int index) {
	// on a get() pour trouver la cellule du point d'insertion
	// Seul cas particulier, la liste est vide
    }

    public CellDouble replace(int value, int index) {
	// utiliser get()
    }

    public CellDouble removeAt(int index) {
	// utiliser get()
    }

    public CellDouble remove(int value) {
	// utiliser find
    }
}

• Le programme de test :