[LinkedList] itérateurs multiples qui modifient une même liste.
Salut,
j'ai un petit doute sur les possibilités des ListIterator.
Voilà mon besoin: j'ai une LinkedList contenant beaucoup d'instances d'Item et je dois souvent ajouter / enlever ces éléments dans ma liste de la façon efficace possible.
La première implémentation qui vient à l'esprit:
Code:
1
2
3
4
5
6
7
8
9
10
11
|
public class Item {
public Object unPeuDeContenu;
}
public class ListOwner {
LinkedList<Item> list;
public void addItem(item i) { list.add(i); }
public void removeItem(item i) { list.remove(i); }
} |
Mon problème est que les suppressions vont être trop lentes, car la fonction remove() parcourt de façon linéaire la liste.
Je me demande donc s'il ne serait pas possible de faire que chaque instance d'Item ait son propre itérateur comme donnée membre de la classe (pas besoin de me rappeler que 'designement parlant' c'est pas bôô, mais mes besoins en perfs sont critiques et l'utilisation d'une liste chaînée impérative).
D'où l'idée de la deuxième solution:
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public class Item {
public Object unPeuDeContenu;
public ListIterator<Item> it;
}
public class ListOwner {
LinkedList<Item> list;
public void addItem(Item item) {
list.add(item);
item.it = list.listIterator(list.size() - 1);
}
public void removeItem(Item item) {
item.it.remove();
}
} |
Ici, la fonction LinkedList::remove() est remplacée par le remove de l'itérateur, ce qui me paraît bien plus rapide.
MAIS (ma question, enfin ;)) je me demande si cette approche est correcte. En effet, lorsque je vais faire ListIterator.remove() sur mon item 'x', cela va-t-il invalider les itérateurs de tous mes autres items présent dans cette liste ?
La doc étant souvent notre amie, j'ai fouiné et j'ai trouvé deux phrases dans la description de LinkedList:
D'une part:
Citation:
Note that this implementation is not synchronized. If multiple threads access a list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally
Mais également:
Citation:
The iterators returned by the this class's iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the Iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
Donc j'ai bien compris que pour des accès concurrents (multi-threads) j'oublie (mais c'est pas mon cas). Mais cela fonctionnerait-il pour des accès séquentiels avec plusieurs instances de ListIterator pointant sur des élements d'une même liste ?
Intuitivement, je pense que la réponse est négative parce que j'imagine mal que lorsqu'un iterateur pointant sur l'item 'n' fait un remove(), il aille signifier à tous les itérateurs pointant sur 'n-1' et 'n+1' que (respectivement) leur next() et previous() ont changé. Mais peut-être auriez-vous une réponse définitive ?
Merci d'avance pour vos éclaircissements :)
