| précédent | suivant | table des matières | s'évaluer |
|
|
La classe LinkedList implémente une liste d’objets représentée de la façon suivante :
Le premier élément de la liste est un élément factice (en jaune sur le dessin) qui facilite l’écriture des algorithmes.
La classe LinkedList implémente l’interface List .
La classe Entry peut être définie comme une classe interne privée : elle est simplement munie d’un constructeur.
private static class Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
LinkedList est définie :
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Cloneable, Serializable{
private transient Entry<E>head ;
private transient int size ;
private transient int modCount = 0;// pour qu'un itérateur sur une liste puisse savoir
// si la liste a été modifiée par ailleurs (ajout ou retrait)
...
}
1 Les constructeurs
Les constructeurs de la classe LinkedList sont définis comme suit :
public LinkedList() {
header = new Entry<E>(null, null, null);
size = 0;
header.next = header.previous = header;
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
2 Quelques outils
Avant de définir les méthodes de l’interface Collection, puis de l’interface List, définissons quelques outils :
La première méthode permet d’enlever de la liste des chaînons, le chaînon c :
private E remove(Entry<E> e) {
// enlève le chaînon e de la liste, et retourne l'élément retiré
if (e == header) throw new NoSuchElementException();
E result = e.element;
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = null;
e.element = null;
size--;
return result;
}
Les deux méthodes suivantes permettent d’ajouter un chaînon contenant o dans son champ élément, avant, ou après le chaînon e :
private Entry<E> addBefore(E o, Entry<E> e) {
// ajoute un nouveau chaînon contenant o avant e
// et retourne la référence au nouveau chaînon
Entry<E> newEntry = new Entry<E>(o, e, e.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
private Entry<E> addAfter(E o, Entry<E> e) {
// ajoute un nouveau chaînon contenant o après e
// et retourne la référence au nouveau chaînon
Entry<E> newEntry = new Entry<E>(o, e.next, e);
e.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
La méthode suivante permet d’obtenir la référence au chaînon d’indice index, s’il existe :
private Entry<E> entry(int index) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
Entry<E> e = header;
if (index < (size >> 1))
for (int i = 0; i <= index; i++) e = e.next;
else
for (int i = size; i > index; i--) e = e.previous;
return e;
}
3 Méthodes de l’interface Collection
La méthode add ajoute un élément en fin de liste :
public boolean add(E o){
// ajout à la fin de la liste
addBefore(o, header);
return true;
}
public boolean addAll(Collection<? extends E> c){
// ajout des éléments de c à la fin de la liste
for(E e : c) addBefore(e, header);
return c.size()!=0;
}
public void clear(){
// le for est là pour aider gc
for (Entry<E> e = header.next, next = e.next; e != header; e = next, next = e.next) {
e.next = e.previous = null;
e.element = null;
}
header.next = previous = header;
size = 0;
}
public boolean isEmpty(){
return size == 0;
}
public int size(){
return size;
}
public< boolean contains(Object o){
Entry<E> p;
if(o==b>null){
for( p = header.next; p != header; p = p.next)
if(p.element==null) return true;
}else{
for(p = header.next; p != header; p = p.next)
if(o.equals(p.element)) return true;
}
return false;
}
La méthode containsAll n'est pas redéfinie.
public boolean remove(Object o){
if(o == null){
for(Entry<E> p = header.next; p != header; p = p.next)
if(p.element==null){ remove(p); return true;}
}else{
for(Entry<E> p = header.next; p != header; p = p.next)
if(o.equals(p.element)){ remove(p); return true;}
}
return false;
}
Les méthodes removeAll et retainAll ne sont pas redéfinies.
public Object [] toArray(){
Object [] resultat = new Object[size];
Entry<E> p = header.next;
for( int i = 0; i < size; ++i, p = p.next)
resultat[i] = p.element;
return resultat;
public <T> T [] toArray(T [] t){
if (t.length < size)
t = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
int i = 0;
Object[] result = t;
for (Entry<E> e = header.next; e != header; e = e.next)
result[i++] = e.element;
if (t.length > size) t[size] = null;
return t;
}
4 Redéfinition des méthodes de Object
equals et toString ne sont pas redéfinies.
public Object clone(){
try {
LinkedList<E> l = (LinkedList<E>)super.clone();
// attention ne pas faire
// l.tete = new Chainon(null, l.tete, l.tete);
l.header = new Entry<E>(null, null, null);
l.header.next = l.header.previous = l.header;
l.size = 0;
for( Entry<E> p = header.next; p!=header; p = p.next) l.add(p.element);
return l;
} catch (CloneNotSupportedException e) {
// ne doit pas se produire :
// ListeLiee implémente Cloneable
throw new InternalError();
}
}
5 Méthodes de l’interface List
public boolean add(int index, E o){
// ajout de o au rang index
if (index == size) add(o);
else addBefore(o, entry(index));
return true;
}
public boolean addAll(int index, Collection<? extends E> c){
// ajout des éléments de c à partir de l'index
e = entry(index);
for(E o : c) e.addBefore(o);
return c.size()!=0;
}
public E get(int index){
return entry(index).element;
}
public int indexOf(Object o){
Entry<E> p;
int index=0;
if(o==null){
for( p = header.next; p != header; ++index, p = p.next)
if(p.element==null) return index;
}else{
for( p = header.next; p != header; ++index, p = p.next)
if(o.equals(p.element)) return index;
}
return -1;
}
public int lastIndexOf(Object o){
Entry<E> p;
int index=size-1;
if(o==null){
for( p = header.previous; p != header; --index, p = p.previous)
if(p.element==null) return index;
}else{
for(p = header.previous; p != header; --index, p = p.previous)
if(o.equals(p.element)) return index;
}
return -1;
}
public E remove(int index){
return remove(entry(index));
}
public E set(int index, E o){
Entry<E> p = entry(index);
E ancienElement = p.element;
p.element = o;
return ancienElement;
}
6 Méthodes propres à LinkedList
public Object getFirst(){
if(size == 0) throw new NoSuchElementException();
return header.next.element;
}
public Object getLast(){
if(size == 0) throw new NoSuchElementException();
return header.previous.element;
}
public E removeFirst(){
remove(header.next);
}
public Object removeLast(){
return remove(header.previous);
}
public void addFirst(Object o){
addBefore(o, header.next);
}
public void addLast(Object o){
addBefore (o, header);
}
7 Itérateurs
Les méthodes iterator() et listIterator() définies dans AbstractList, ne sont pas redéfinies. Seule la méthode listIterator(int index ) est définie.
public ListIterator<E> listIterator(int index) {
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Entry<E> lastReturned = header;
private Entry<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// index est l'indice du prochain élément obtenu par next
// positionner next sur l'élément d'indice index
// et nextIndex à la valeur index
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);
if (index < (size >> 1)) {
next = header.next;
for (nextIndex=0; nextIndex<index; nextIndex++)
next = next.next;
}else{
next = header;
for (nextIndex=size; nextIndex>index; nextIndex--)
next = next.previous;
}
}
public boolean hasNext() {
return nextIndex != size;
}
public E next() {
checkForComodification();
if (nextIndex == size)throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.element;
}
public boolean hasPrevious() {
return nextIndex != 0;
}
public E previous() {
if (nextIndex == 0)throw new NoSuchElementException();
lastReturned = next = next.previous;
nextIndex--;
checkForComodification();
return lastReturned.element;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex-1;
}
public void remove() {
checkForComodification();
Entry<E> lastNext = lastReturned.next;
try {
LinkedList.this.remove(lastReturned);
}catch (NoSuchElementException e) {
thrownew IllegalStateException();
}
if (next==lastReturned) next = lastNext;
elsenextIndex--;
lastReturned = header;
expectedModCount++;
}
public void set(E o) {
if (lastReturned == header)throw new IllegalStateException();
checkForComodification();
lastReturned.element = o;
}
public void add(E o) {
checkForComodification();
lastReturned = header;
addBefore(o, next);
nextIndex++;
expectedModCount++;
}
final void checkForComodification() {
if (modCount != expectedModCount) throw new ConcurrentModificationException();
}
}