| précédent | suivant | table des matières | s'évaluer |
|
|
La classe ArrayList implémente un tableau d’objets
qui peut grandir ou rétrécir à la demande, ce qui débarrasse le programmeur de
la gestion de la taille du tableau. Comme pour un tableau on peut accéder à un
élément du ArrayList, par un indice.
Les éléments de la liste tableau sont représentés dans un tableau d'objets de type
E : elementData, qui
sont tous tassés en tête du tableau dans les élément d’indice 0 à size
nombre d’éléments présents dans le ArrayList.
| Une instance de ArrayList contenant quatre objets peut être représentée de la façon suivante : |
|
Lorsque le tableau est plein (size == taille du tableau), et qu’on veut ajouter un élément dans le tableau, le tableau est agrandi : la nouvelle taille est l’ancienne taille *3/2 plus 1.
| Insertion d'un élément, dans un ArrayList qui contient 4 éléments et qui est déjà plein : le tableau elementData est agrandi. |  |
| Après ajout, la taille de elementData est 4*3/2+1 = 7 |
 |
public class ArrayList<E> extends AbstractList<E>
implementsList<E>, RandomAccess, Cloneable, java.io.Serializable{
private transient E[] elementData;>
private int size;
. . .
1 Constructeurs
Le constructeur suivant construit un ListeTableau avec sa capacité initiale :
public ArrayList(int capacityInitial) {
super();
if(capacityInitial<0) throw new IllegalArgumentException("capacityInitial : "
+capacityInitial)
elementData = (E[])new Object[capacityInitial];
size = 0;
}
Le constructeur par défaut construit un ListeTableau de 10 emplacements.
public ArrayList() {
this(10);
}
Le constructeur suivant permet de construire un ArrayList à partir d'une collection d'objets qui sont de la classe E ou d'une sous-classe de E :
public ArrayList(Collection<? extends E> c) {
size = c.size();
// On se donne 10% de plus pour grandir dans le futur
elementData = (E[])new Object[
(int)Math.min((size*110L)/100,Integer.MAX_VALUE)];
c.toArray(elementData);
}
2 Les méthodes de l'interface Collection :
La méthode add ajoute un élément au ArrayList la méthode appelle la méthode ensureCapacity, qui vérifie qu’il y a de la place pour réaliser l’ajout, et s’il n’y a pas de place agrandit le tableau. La méthode ensureCapacity pouvant servir à un utilisateur de la classe, elle est publique.
public void ensureCapacity(capaciteMin){
// assure que la capacité du tableau représentant les éléments
// est au moins de capaciteMin
int ancienneCapacite = elementData.length;
if (capaciteMin > ancienneCapacite) {
E [] ad = elementData;
int nouvelleCapacity = ancienneCapacite * 3 / 2 + 1;
if(nouvelleCapacity < capaciteMin)
nouvelleCapacity = capaciteMin;
elementData = (E[])new Object[nouvelleCapacity];
System.arraycopy(ad, 0, elementData, 0, size);
}
}
La méthode add ajoute un élément en fin de tableau :
public boolean add(E o){
ensureCapacity(size+1);
elementData[size++] = o;
return true;
}
La méthode clear enlève tous les éléments du vecteur, size retourne le nombre d’éléments du ArrayList et isEmpty retourne vrai si et seulement si le ArrayListest vide :
public void clear(){
for( int i = 0; i< nbElements; ++i)
elementData = null;
size = 0;
}
public int size(){return size;}
public boolean isEmpty(){
return size ==0;
}
La méthode contains retourne true si o appartient au ArrayList et false sinon :
public boolean contains(Object o){
return indexOf(o)!=-1;
}
La méthode remove enlève la première occurrence de o du ArrayList, si elle existe et dans ce cas retourne true, sinon la méthode retourne false : dans le cas où l’élément est enlevé, il faut « retasser » le ArrayList :
public boolean remove(Object o){
if(o == null){
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
}else{
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])){
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // le Garbage Collector peut éventuellement récupérer l'espace
}
Les deux méthodes suivantes convertissent un ArrayList en un tableau d’Object :
public Object [] toArray(){
Object [] resultat = new Object[size];
System.arraycopy(elementData, 0, resultat, 0, size);
return resultat;
}
La méthode suivante, copie tous les éléments du ArrayList dans le tableau t et retourne ce tableau si celui ci estassez grand, sinon ellecopie les éléments dans un tableau qui est créé et le retourne.
public <T> T[] toArray(T[] t) {
if (t.length < size)
t = (T[])java.lang.reflect.Array.newInstance(t.getClass().getComponentType(),size);
System.arraycopy(elementData, 0, t, 0, size);
if (t.length > size) t[size] = null;
return t;
}
Parmi les opérations de masse, seule la méthode addAll est redéfinie, pour profiter de l'optimisation due au arraycopy :
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacity(size + numNew);
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
3 Les méthodes de l'interface List :
La méthode suivante permet d’ajouter un élément à un indice donné dans le ArrayList :
public void add(int index, Object o){
if( index < 0 || index > size) throw new IndexOutOfBoundsException();
ensureCapacity( size + 1);
// déplacement des elements d’indice >= index
System.arraycopy(elementData, index, elementData, index+1,size - index );
elementData[index] = o;
++size;
}
La méthode get retourne l’élément se trouvant à un indice, ou lève une exception :
public Object get(int index){
if(index < 0 || index >= nbElements) throw new IndexOutOfBoundsException();
return elementData[index];
}
Les deux méthodes suivantes retournent l’indice d’un objet dans le ArrayList s’il est présent, -1 sinon. indexOf commence au début du ArrayList et lastIndexOf commence à la fin du vecteur :
public int indexOf(Object elem) {
if (elem == null) {
for (int i = 0; i < size; i++)
if(elementData[i]==null)
return i;
}else {
for (int i = 0; i < size; i++)
if (elem.equals(elementData[i]))
return i;
}
return -1;
}
|
public int lastIndexOf(Object elem) {
if (elem == null){
for (int i = size-1; i >= 0; i--)
if(elementData[i]==null)
return i;
}else{
for (int i = size-1; i >= 0; i--)
if (elem.equals(elementData[i]))
return i;
}
return -1;
} |
La méthode Object remove(int index) permet d’enlever du ArrayList l’élément se trouvant à l’indice index si celuici est correct, et retourne l’objet enlevé du ArrayList :
public E remove(int index){
if( index < 0 || index >= size) throw new IndexOutOfBoundsException();
E o = elementData[index];
System.arraycopy(elementData, index+1, elementData, index, size - index - 1);
elementData[ size - 1]=null;
--size;
return o;
}
La méthode Object set(int index, Object o) modifie l’objet se trouvant en position index dans le vecteur, en lui affectant o, et retourne l’objet qui occupait cette place avant.
public e set(int index, e o){
if( index < 0 || index >= size)>throw new IndexOutOfBoundsException();
E x = elementData[index];
elementData[index] = o;
return x;
}
4 Méthode propres à ArrayList
TrimToSize ajuste la capacité du ArrayList à son nombre d'éléments.
public void trimToSize(){
int ancienneCapacity = elementData.length;
if(nbElements < ancienneCapacity) {
E[] oldData = elementData;
elementData = (E[])newObject[size];
System.arraycopy(oldData, 0, elementData,0, nbElements);
}
}