// MODULE: ListTest.java // AUTEUR: felipe // OBJET: montrer comment on peut +implementer une liste // COMMENT: utiliser plutot la classe LinkedList de java.util import java.util.*; // ----------------------------------------------------------- // juste pour montrer que l'on peut creer son propre objet // Exception // ----------------------------------------------------------- class MyLinkedListException extends RuntimeException { public MyLinkedListException() {} public MyLinkedListException(String s) {super(s);} } // -------------------------------------------------------------------- // la classe LinkedList de java.util fait ceci de maniere plus complete // -------------------------------------------------------------------- class MyLink { Object data; MyLink next; private void setNode(Object o, MyLink n) { data = o; next = n; } public MyLink(Object o) {setNode(o,null);} public MyLink(Object o, MyLink n) {setNode(o,n);} } // -------------------------------------------------------------- class MyLinkedList { private MyLink firstElement,lastElement,cursor; private int elementCount; private void init() { elementCount = 0; firstElement = lastElement = null; } public MyLinkedList() {init();} // ajout en tete public void addFirst(Object o) { firstElement = new MyLink(o,firstElement); if (elementCount == 0) lastElement = firstElement; elementCount++; } // ajout en queue public void addLast(Object o) { if (elementCount > 0) { lastElement.next = new MyLink(o); lastElement = lastElement.next; } else { firstElement = lastElement = new MyLink(o); } elementCount++; } // remove en tete public Object removeFirst() throws MyLinkedListException { if (elementCount <=0) throw new MyLinkedListException("liste vide"); cursor = firstElement; if ((firstElement = firstElement.next) == null) init(); else elementCount--; return cursor.data; } // remove l'elt d'indice index public Object remove(int index) { if ( index >= 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; return toRemove.data; } // remove en queue 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; lastElement = prev; } else init(); return cursor.data; } // return the first element public Object getFirst() throws MyLinkedListException { if (elementCount == 0) throw new MyLinkedListException("liste vide"); return firstElement.data; } // return the last element public Object getLast() throws MyLinkedListException { if (elementCount == 0) throw new MyLinkedListException("liste vide"); return lastElement.data; } // get any elet public Object get(int indice) throws MyLinkedListException { if (indice >= elementCount) throw new MyLinkedListException("hors liste"); if (indice == (elementCount-1)) return getLast(); cursor = firstElement; for (int i=0; i < indice; i++) cursor = cursor.next; return cursor.data; } // is the object in the list ? public boolean contains(Object o) { for (cursor=firstElement; cursor.next != null; cursor = cursor.next) if (o.equals(cursor.data)) return true; return false; } public void clear() {init();} public int size() {return elementCount;} // NOTE: elements n'existe pas dans la version de java.util // a la place il y a un mecanisme d'iterateur public Enumeration elements() { return new MyLinkedListEnumeration(firstElement); } } // ----------------------------------------------------- // la classe qui implemente Enumeration // ----------------------------------------------------- class MyLinkedListEnumeration implements Enumeration { private MyLink head; public MyLinkedListEnumeration(MyLink h) {head = h;} public boolean hasMoreElements() { return (head != null); } public Object nextElement() { MyLink item = head; head = head.next; return item.data; } } // ------------------------------------------------------- // voici la classe principale // ------------------------------------------------------- public class ListTest { static void afficheListe(Object o) { if (o instanceof MyLinkedList) { Enumeration enum = ((MyLinkedList) o).elements(); System.out.print(""); while (enum.hasMoreElements()) { System.out.print(" " + ((Integer) enum.nextElement()).intValue()); } System.out.println(""); } else { ListIterator li = ((LinkedList) o).listIterator(0); System.out.print(""); while (li.hasNext()) { System.out.print(" " + li.next()); } System.out.println(""); } } static public void main(String [] args) { LinkedList l = new LinkedList(); for (int i=0; i<7; i++) l.addFirst(new Integer(i)); for (int i=0; i<7; i++) l.addLast(new Integer(i)); System.out.println("Size=" + l.size()); System.out.println("valeur de tete=" + l.getFirst()); System.out.println("valeur de queue=" + l.getLast()); System.out.println("elt 4=" + l.get(4)); System.out.println("elt 6=" + l.get(6)); System.out.println("elt 11=" + l.get(11)); System.out.println("is 3 in the list ? " + l.contains(new Integer(3))); afficheListe(l); l.removeFirst(); l.removeLast(); System.out.println("Size=" + l.size()); afficheListe(l); System.out.println("Suppression de elt 5=" + l.remove(5)); afficheListe(l); System.out.println("==========================="); MyLinkedList l2 = new MyLinkedList(); for (int i=0; i<7; i++) l2.addFirst(new Integer(i)); for (int i=0; i<7; i++) l2.addLast(new Integer(i)); System.out.println("Size=" + l2.size()); System.out.println("valeur de tete=" + l2.getFirst()); System.out.println("valeur de queue=" + l2.getLast()); System.out.println("elt 4=" + l2.get(4)); System.out.println("elt 6=" + l2.get(6)); System.out.println("elt 11=" + l2.get(11)); System.out.println("is 3 in the list ? " + l2.contains(new Integer(3))); afficheListe(l2); l2.removeFirst(); l2.removeLast(); System.out.println("Size=" + l2.size()); afficheListe(l2); System.out.println("Suppression de elt 5=" + l2.remove(5)); afficheListe(l2); } }