/** * Illustrer le genre de code associe a une liste simplement chainee. * En pratique, il est completement inutile de reimplementer ce genre * de structure de donnees, car elles existent deja (mieux faites :-) * dans la librairie standard de Java. * * Par exemple, le type LinkedList existe dans l'API qui offre des services * similaires et beaucoup plus encore ! * * @author felipe */ import java.util.Enumeration; // ----------------------------------------------------------- // juste pour montrer que l'on peut creer son propre objet // Exception // ----------------------------------------------------------- class MyLinkedListException extends RuntimeException { public MyLinkedListException() {} public MyLinkedListException(String s) {super(s);} } /** * un maillon n'est autre que deux references: l'une sur l'element (data) * l'autre sur l'element suivant (next) * * Note: pour simplifier le code, je ne precise pas de modificateur d'access * aux membres data et next. Dans le package (repertoire), ces membres peuvent * etre utliser comme s'ils etaient prives. Dans Lewis et Loftus, les auteurs * utilisent une classe encapsulee, mais je n'aime pas ca ... */ class MyLink { Object data; // acces package MyLink next; // acces package public MyLink(Object o) {this(o,null);} public MyLink(Object o, MyLink n) { data = o; next = n;} } /** * Une implementation possible de LinKedList. * Je reprends quelques services (methodes publiques) offerts par la classe LinkedList * En pratique, c'est la classe LinkedList qu'il faut utiliser et pas ce code. */ class MyLinkedList { private MyLink firstElement, // pointeur sur le premier element lastElement, // pointeur sur le dernier element cursor; // pointeur de recherche (voir le code) private int elementCount; // nombre d' elements dans la liste /** * Initialisation de la liste * appelee plusieurs fois, sinon j'aurais mis ca dans le(s) constructeur(s) */ private void init() { elementCount = 0; firstElement = lastElement = null; } /** * Le constructeur (cree une liste vide) */ public MyLinkedList() {init();} /** * Ajout en tete d'un element * @param o reference sur l'element a ajouter */ public void addFirst(Object o) { firstElement = new MyLink(o,firstElement); if (elementCount == 0) lastElement = firstElement; elementCount++; } /** * Ajout en queue d'un element * @param o reference sur l'element a ajouter */ public void addLast(Object o) { if (elementCount > 0) { lastElement.next = new MyLink(o); lastElement = lastElement.next; } else { firstElement = lastElement = new MyLink(o); } elementCount++; } /** * Ajoute a un indice donne un element * @param index indice de l'element (commence a 0) * @param o reference a l'element * @throws MyLinkedListException si l'index est mauvais * * Note: on peut ecrire ca de maniere plus elegante (enlever des tests) */ public void add(int index, Object o) throws MyLinkedListException { if (index > size() || index <0) new MyLinkedListException("mauvais indice"); else if (index == 0) addFirst(o); else if (index == elementCount) addLast(o); else { // le cas general int i; MyLink pred; // pointe sur le predecesseur du index-ieme element for (pred = null, cursor = firstElement, i=0 ; (i= elementCount) throw new MyLinkedListException("hors liste"); if (index == 0) return removeFirst(); if (index == (elementCount-1)) removeLast(); cursor = firstElement; for (int i=0; i<(index-1); i++) cursor = cursor.next; // cursor pointe sur l'elt precedant celui a supprimer MyLink toRemove = cursor.next; cursor.next = toRemove.next; elementCount--; return toRemove.data; } /** * Enleve le dernier element de la liste * @return la reference sur le dernier elt supprime * Note: La encore, l'implementation est particulierement inefficace */ public Object removeLast() throws MyLinkedListException { if (elementCount <=0) throw new MyLinkedListException("liste vide"); elementCount--; MyLink prev=null; for (cursor=firstElement; cursor.next != null; cursor = cursor.next) prev = cursor; if (prev != null) { prev.next = null; //cursor = lastElement; (QUIZZ: voyez-vous pourquoi c'est inutile ?) lastElement = prev; } else init(); return cursor.data; } /** * @return une reference sur le premier elt de la liste (s'il existe) * @throws MyLinkedListException si la liste est vide */ public Object getFirst() throws MyLinkedListException { if (elementCount == 0) throw new MyLinkedListException("liste vide"); return firstElement.data; } /** * @return une reference sur le dernier elt de la liste (s'il existe) * @throws MyLinkedListException si la liste est vide */ public Object getLast() throws MyLinkedListException { if (elementCount == 0) throw new MyLinkedListException("liste vide"); return lastElement.data; } /** * Retourne une reference sur l'element souhaite * @param indice l'indice (commence a 0) de l'element * @return une reference sur l'element souhaite (s'il existe) * @throws MyLinkedListException si l'indice n'est pas bon */ public Object get(int indice) throws MyLinkedListException { if ((indice < 0) || (indice >= elementCount)) throw new MyLinkedListException("mauvais indice"); if (indice == (elementCount-1)) return getLast(); cursor = firstElement; for (int i=0; i < indice; i++) cursor = cursor.next; return cursor.data; } /** * Recherche dans la liste un objet similaire (au sens de equals) a * celui passe en argument * @param o la reference sur un objet * @retrun true si un tel objet existe dans la liste */ public boolean contains(Object o) { for (cursor=firstElement; cursor != null; cursor = cursor.next) if (o.equals(cursor.data)) return true; return false; } /** * Elimine tous les elements de la liste */ public void clear() { init(); System.gc(); } /** * @return le nb d'elt dans la liste */ public int size() {return elementCount;} /** * Juste pour nous remettre en tete les interfaces * Je ne suis plus certains, mais elements n'existe pas * dans la version java.util.LinkedList. Il existe a la * place une implementation d'une autre interface (iterator) */ public Enumeration elements() { return new MyLinkedListEnumeration(firstElement); } } /** * La classe qui implemente Enumeration * Idee: consulter un a un les elements * La encore on capitalise sur l'acces package des membres * next et data de MyLink */ class MyLinkedListEnumeration implements Enumeration { private MyLink head; /** * NOTE: On passe ici la reference sur le premier elt de la liste */ public MyLinkedListEnumeration(MyLink h) {head = h;} /** * @return true s'il y a encore des elements a traverser */ public boolean hasMoreElements() {return (head != null);} /** * @return la reference sur le prochain elt a consulter */ public Object nextElement() { MyLink item = head; head = head.next; return item.data; } }