Discussion :

[Seabiscit]

Bonjour à tous,

Je viens juste de m'inscrire sur le forum pour signaler une erreur dans la FAQ java à propos de java.util.LinkedList .

Il est marqué : "Complexité : Les opérations size, isEmpty, add, remove, set, get sont exécutées en temps constant" .

Or l'opération remove n'est pas exécutée en temps constant mais
en temps linéaire.

Il est vrai que dans certains langages comme le C, la supression ou la récupération d'un élément
dans une liste fonctionne en temps constant mais c'est du au fait qu'on
possède l'adresse de la cellule de la liste.
L'opération remove de java.util.LinkedList prend en paramètre
une référence sur l'objet à supprimer mais ne prend
pas en paramètre la référence de la cellule qui contient l'objet :
la référence de la cellule n'est pas connue et donc une recherche doit
être effectuée -> remove est en O(n) .

Pour la petite histoire, je code habituellement en C et je me met doucement
à java. C'est pour ça que je regarde la FAQ java pour essayer d'en apprendre
plus sur le langage.
Je ne comprenais pas comment la méthode remove proposée dans LinkedList pouvait s'exécuter en temps constant.
J'ai donc regarder le code source de LinkedList disponible ici
et découvert qu'elle s'exécutait en fait en temps linéaire.

[KiLVaiDeN]

Bonjour,

Je confirme, tu as tout à fait raison ! La méthode remove(Object o), dont un bout de code est le suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
  241               for (Entry<E> e = header.next; e != header; e = e.next) {
  242                   if (o.equals(e.element)) {
  243                       remove(e);
  244                       return true;
  245                   }
  246               }

va effectivement nécessiter un parcours complet des éléments... La LinkedList offre cependant des méthodes en O(1) pour enlever le premier élément ou le dernier ( removeFirst, removeLast ). Je pense que dans la FAQ il faut préciser cela, en focalisant sur l'intérêt d'une telle liste qui est de faire une pile.

Bienvenue sur le forum