Discussion :

[jakcam]

Bonjour à tous,

Je voulais avoir votre avis sur une information contenue dans la FAQ JAVA:

java.util.LinkedList :
Un java.util.LinkedList utilise une liste chainée pour ranger les données. L'ajout et la suppression d'éléments est aussi rapide quelle que soit la position, mais l'accès aux valeurs par leur indice est très lente.
Complexité : Les opérations size, isEmpty, add, remove, set, get sont exécutées en temps constant. Toutes les méthodes qui font référence à un indice sont exécutées en temps O(n).

Etes-vous d'accord avec cette définition ? Pour ma part, elle n'est pas assez précise et peu porté à confusion.

J'en profite pour remercier beaucoup tout les contributeurs de la FAQ JAVA qui m'a souvent servi !!!!

[kolodz]

Pour moi, cela est clair.
Surtout si on compare à ce que l'on trouve dans la javadoc.

[Ivelios]

Je là trouve claire aussi :

Un java.util.LinkedList utilise une liste chainée pour ranger les données. L'ajout et la suppression d'éléments est aussi rapide quelle que soit la position,

C'est une chaîne (au sens littéral), il suffit de retirer un maillon ou d'en placer un nouveau en faisant les raccords. Donc très rapide.

mais l'accès aux valeurs par leur indice est très lente.
Complexité : Les opérations size, isEmpty, add, remove, set, get sont exécutées en temps constant. Toutes les méthodes qui font référence à un indice sont exécutées en temps O(n).

Puisqu'il s'agit d'une chaîne, on est obligé de parcours tout depuis le début pour atteindre le maillon souhaité (complexité O(n) ).

Enfin c'est comme ça que je le comprend

[thelvin]

Du coup, 'faut reconnaître que add(), remove(), set() et get() sont O(n), pas O(1)

[Logan Mauzaize]

La remarque est justifiée :

1. La méthode add(E) est bien en O(1) mais pas add(int, E)
2. Toutes les méthodes remove sont en O(n) ; y compris set(int, E).
3. Idem pour get.

Le truc qui serait vrai et vraiment algorithmiquement utile, c'est le fait que toutes les opérations par itérateur sont en O(1) !

[jakcam]

Je suis entièrement d'accord avec thelvin et nemek et c'était la principale raison de ce post.

Serait-il possible de faire pour préciser le contenu le FAQ ?

Merci pour votre participation

[Logan Mauzaize]

Il faut taper très fort sur un modérateur, pas moi si possible

Je fais passer le message

[le y@m's]

Je suis entièrement d'accord avec thelvin et nemek et c'était la principale raison de ce post.

Serait-il possible de faire pour préciser le contenu le FAQ ?

Merci pour votre participation

Pour participer à la FAQ il y a un sujet dédié, tu peux y poster de nouvelles questions/réponses ou proposer une amélioration/correction d'une entrée existante

[jakcam]

Merci de votre aide à tous !

Je vais clore le sujet