//identique à ce qui est dans le package WattBrown; //Version générique juin 2010 import java.util.Iterator; import java.util.NoSuchElementException; public class LinkedList implements List { // Each LinkedList value is an unbounded list whose elements are // objects. // This list is represented as follows: first and last are links to the // first and last nodes of a SLL containing the elements; length is the // number of elements. protected SLLNode first, last; protected int length; // Constructor ... public LinkedList () { // Construct a list, initially empty. first = last = null; length = 0; } public String toString(){ // idem que dans ArrayList StringBuffer sb = new StringBuffer("["); for(Iterator i=iterator();i.hasNext();){ sb.append(i.next()); if(i.hasNext())sb.append(", "); } return sb+"]"; } // Accessors ... public boolean isEmpty () { // Return true if and only if this list is empty. return (first == null); } public int size () { // idem que dans ArrayList // Return this list's length. return length; } public E get (int i) { // Return the element with index i in this list, or null if there is // no such element. if (i < 0 || i >= length) throw new IndexOutOfBoundsException(i+" is not within 0 and "+ length); SLLNode curr = node(i); return curr.element; } public boolean equals (List that) { // idem que dans ArrayList // Return true if and only if this list and that have the same length, // and each element of this list equals the corresponding element // of that. if (length != that.size()) return false; Iterator it = that.iterator(); for(E e:this) if (!e.equals(it.next())) return false; return true; } @SuppressWarnings("unchecked") public boolean equals(Object that){// idem que dans ArrayList if(that==null)return false; if(!(that instanceof List))return false; return equals((List)that); } public int hashCode(){ // idem que dans ArrayList int h = 1; for(E e:this) if(e!=null)h=h*31+e.hashCode(); return h; } public boolean contains(E elem){ // idem que dans ArrayList return indexOf(elem)>=0; } public int indexOf(E elem){ int ix=0; for(SLLNode curr = first;curr!=null;curr=curr.succ,ix++) if(curr.element.equals(elem))return ix; return -1; } // Transformers ... public void clear () { // Make this list empty. first = last = null; length = 0; } public E set (int i, E elem) { // Replace by x the element at index i in this list. if (i < 0 || i >= length) throw new IndexOutOfBoundsException(); SLLNode curr = node(i); E old = curr.element; curr.element = elem; return old; } public boolean add (E elem) { // Add x after the last element of this list. SLLNode newNode = new SLLNode(elem, null); if (first == null) first = newNode; else last.succ = newNode; last = newNode; length++; return true; } public boolean add (int i, E elem) { // Add x as the element with index i in this list. if (i < 0 || i > length) throw new IndexOutOfBoundsException(); SLLNode newNode; if (i == 0) first = newNode = new SLLNode(elem, first); else { SLLNode pred = node(i-1); pred.succ = newNode = new SLLNode(elem,pred.succ); } if (newNode.succ == null) last = newNode; length++; return true; } public boolean addAll(List that) { // idem que dans ArrayList System.out.println("addAll(List)"); // Add all the elements of that after the last element of this list. if(that.isEmpty())return false; for (E e:that) add(e); return true; } // nom en majuscule (LinkedList) pour éviter l'ambiguité d'appel avec la fonction // précédente public boolean addAll(LinkedList that){ System.err.println("addAll(LinkedList)"); if (first==null) first=that.first; else last.succ=that.first; // ajustement de pointeurs si on combine deux LinkedList if (that.first!=null){ last=that.last; length+=that.length; } return true; } public E remove (int i) { // Remove and return the element with index i in this list, // or return null if there is no such element. if (i < 0 || i >= length) throw new IndexOutOfBoundsException(); E old; if (i == 0) { old = first.element; if (first == last) last = null; first = first.succ; } else { SLLNode pred = node(i-1); SLLNode curr = pred.succ; old = curr.element; pred.succ = curr.succ; if (curr == last) last = pred; } length--; return old; } // Iterator ... public Iterator iterator () { // Return an iterator that visits all elements of this list, in // left-to-right order. return new LRIterator(); } /////////// Auxiliary method //////////// protected SLLNode node (int i) { // Return a link to the node containing the element with index i in // this list. SLLNode curr = first; for (int j = 0; j < i; j++) curr = curr.succ; return curr; } //////////// Inner class //////////// private class LRIterator implements Iterator { private SLLNode place, prev, curr; private LRIterator() { place = first; curr = prev = null; } public boolean hasNext () { return (place != null); } public E next () { if (place == null) throw new NoSuchElementException(); E nextElem = place.element; if(curr!=null)prev = curr; curr = place; place = place.succ; return nextElem; } public void remove () { if (curr == null) throw new NoSuchElementException(); if (prev == null) first = first.succ; else prev.succ = curr.succ; curr=null; if(place==null)last=prev; length--; } } }