Forum Programmation.java LinkedList, itérateurs, et modifications concurrentes

Posté par  .
Étiquettes : aucune
1
12
mar.
2011

Bonjour à tous,

J'ai découvert avec désespoir que Java invalidait les itérateurs sur les listes en cas de modification concurrente.

Ca me chagrine beaucoup parce que je voudrais garder un "pointeur" vers un élément particulier de ma liste pendant que j'ajoute des trucs en fin de liste.

En clair, un truc comme :

LinkedList<MaClasse> aList = new LinkedList<MaClasse>();

// ... on ajoute des éléments dans ma liste ...
// ...

// Je crée mon itérateur et je l'amène à la position voulue
ListIterator<MaClasse> aIt = aList.iterator();

while (aIt.hasNext())
{
aIt.next()
}

// je concatène une autre liste
aList.addAll(monAutreListe);

// Et la je voudrais bien pouvoir accéder à l'élément qui était en fin de liste AVANT la concaténation
aIt.previous().faireCeQueJeVeux()

Mais Java me balance une exception comme quoi la liste a été modifiée après l'allocation de l'itérateur. Pourtant ça me parait vraiment curieux : je comprendrais que les itérateurs d'un tableau soient invalidés (la représentation en mémoire peut complètement changer quand on insère des trucs). Mais les éléments de ma liste chaînée ne sont pas censés bouger quand je concatène des trucs, donc je comprends pas pourquoi Java prend un malin plaisir à me casser les c... pieds.

Si quelqu'un à une solution simple pour faire ce que je veux faire (sans reparcourir toute la liste, ou utiliser des indices, le but de la manip c'est justement d'avoir quelque chose en complexité O(1) pour l'accès à ce fameux élément), je suis preneur ! :)

Merci d'avance.

  • # Fait pointer un objet dessus.

    Posté par  . Évalué à 2.

    Salut,

    Je n'ai pas d'IDE java sous la main et comme ça fait déjà quelques temps que je n'ai plus fait de java, je te dis ça de mémoire en espérant que ça puisse te guider.

    LinkedList<MaClasse> aList = new LinkedList<MaClasse>();

// Cet objet va "pointer" sur le dernier élément de ta liste
MaClasse lastElementBefore = aList.getLast();

// tu concatènes une autre liste
aList.addAll(monAutreListe);

// Et la je voudrais bien pouvoir accéder à l'élément qui était en fin de liste AVANT la concaténation
lastElementBefore.faireCeQueTuVeux();

    • [^] # Re: Fait pointer un objet dessus.

      Posté par  . Évalué à 2.

      Arf je me suis mal exprimé. En fait ce n'est pas l'élément lui même qui m'intéresse mais bien l'itérateur. Je veux pouvoir re-parcourir ma liste à partir de ce dernier élément, ou encore supprimer tout les éléments après ce dernier élément (pour ramener la liste dans l'état initial, avant concaténation).

      Avec ce que tu propose, je garde effectivement une référence sur l'élément, mais je ne peux pas modifier la liste à partir de cette référence.

    • [^] # Re: Fait pointer un objet dessus.

      Posté par  . Évalué à 2.

      En fait, je voudrais garder un itérateur pour pouvoir faire un truc du genre de (en C++):

      aList.erase(MonIterateur, aList.end())
      Et restaurer ainsi l'état de la liste avant la concaténation.

      La fonction en question est décrite ici : ici

      Mais de toute façon, j'ai l'impression qu'il n'y a pas vraiment moyen de faire ça en java. La seule fonction qui s'approche vaguement de ça a l'air d'être AbstractList.removeRange, et elle prend des indices en arguments (et pas des itérateurs) et parcourt betement toute la liste (on voit pas bien l'intérêt de prendre une structure de données chaînée si c'est pour tout reparcourir quand on veut supprimer des éléments...)

      Bref, j'abandonne pour ce soir. (Vengeance mesquine, un petit troll pour la nuit : java c'est de la m***, C++ c'est mieux ;-) )

      Bonne soirée à tous !

      • [^] # Re: Fait pointer un objet dessus.

        Posté par  . Évalué à 1.

        En fonction de la taille de la liste à ajouter, tu peux appeler n fois add de listIterator

        LinkedList<MaClasse> aList = new LinkedList<MaClasse>();

// ... on ajoute des éléments dans ma liste ...
// ...

// Je crée mon itérateur et je l'amène à la position voulue
ListIterator<MaClasse> aIt = aList.listIterator();

while (aIt.hasNext())
{
    aIt.next()
}

// Ajout d'éléments dans la liste à partir de l'itérateur : 

aIt.add(objet1);
aIt.add(objet2);

// ...
while (aIt.hasNext())
{
    aIt.remove();
}

        Ce genre de code n'est pas censé générer de ConcurrentModificationException. Le fait d'avoir déjà l'itérateur fait qu'en interne on a déjà le pointeur vers l'élément à ajouter et on n'a pas besoin de refaire des recherches, mais ça ne correspond peut-être pas à ce que tu veux faire.

        • [^] # Re: Fait pointer un objet dessus.

          Posté par  . Évalué à 1.

          Désolé pour le doublon, le site m'a dit qu'il y avait une erreur alors j'ai bêtement renvoyé ce que j'avais dans mon presse papiers sans vérifier avant si l'enregistrement avait fonctionné.

        • [^] # Re: Fait pointer un objet dessus.

          Posté par  . Évalué à 0.

          Je reviens un peu tard, mais mieux vaut tard que jamais.

          Merci pour ta réponse. Intéressant que la méthode add ne déclenche pas l'exception.

          Cela dit le code que tu propose ne me convient pas vraiment : je garde mon itérateur, certes, mais le prix à payer pour ça est d'ajouter les éléments un à un (complexité en O(n), si n est la taille de ma liste uneAutreListe). Je tenais à la concaténation de listes, parce qu'elle est censée être instantanée.

          Toutefois, je suis pris d'un doute : quelqu'un pourrait-il confirmer que la concaténation de listes avec addAll se fait bien en O(1) ? Bien évidemment, impossible de trouver ce genre d'info sur la doc officielle d'oracle.
          Si ce n'est pas le cas, comment concaténer des listes chaînées en O(1), et si possible sans déclencher de ConcurrentModificationException ?

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.