EDIT: Peu importe

Question

EDIT: Wow, je suis tellement désolé .... Je confondais en quelque sorte les colonnes LinkedList et ArrayList dans le deuxième graphique> _> Je n'ai pas beaucoup dormi .... désolé ... Au moins une réponse m'a aidé d'une autre manière, avec une explication détaillée, donc ce post n'était pas un gâchis TOTAL ...

J'ai trouvé quelques sujets à ce sujet mais il y avait des contradictions dans les articles, donc je voulais une confirmation de qui était correct.

Ce sujet ici est ce que je trouve: When to use LinkedList over ArrayList?

La réponse la plus upvoted dit:

« Pour LinkedList

• get est O (n)
• add est O (1)
• supprimer est O (n)
• Iterator.remove est O (1)

Pour ArrayList

• get est O (1)
• add est O (1) amorti, mais O (n) le plus défavorable puisque le tableau doit être redimensionné et copié
• supprimer est O (n) »

Mais si Meone posté un autre lien ici qui dit:
http://leepoint.net/notes-java/algorithms/big-oh/bigoh.html

Algorithm  ArrayList LinkedList 
access front  O(1)   O(1) 
access back  O(1)   O(1) 
access middle O(1)   O(N) 
insert at front O(N)   O(1) 
insert at back O(1)   O(1) 
insert in middle O(N)   O(1) 

Answer 1

Il n'y a pas de contradiction entre les deux sources citées dans la question.

D'abord quelques réflexions sur chaînées: Dans une liste chaînée, nous devons déplacer un pointeur dans la liste pour obtenir l'accès à un élément particulier soit le supprimer, examiner ou insérer un nouvel élément avant qu'il . Puisque l'implémentation java.util.LinkedList contient une référence au début et à la fin de la liste, nous avons des accès immédiats au recto et au verso de la liste, ce qui explique pourquoi toute opération impliquant le recto ou le verso de la liste est O (1). Si une opération est effectuée à l'aide d'un Iterator, le pointeur est déjà là où vous en avez besoin. Donc, pour supprimer un élément du milieu prend le temps O (n), mais si l'Iterator a déjà passé les opérations O (n) au milieu, alors iter.remove() peut s'exécuter dans O (1).

Maintenant conisider ArrayList: Sous le capot, ArrayList stocke les données dans un tableau de primitives. Donc, bien que nous puissions accéder à n'importe quel élément en O (1) temps, ajouter ou supprimer un élément nécessitera que le tableau entier soit décalé d'un élément vers le bas et cela prend du temps O (n). Si nous ajoutons ou supprimons le dernier élément, cela ne nécessite aucun décalage, donc cela peut s'exécuter dans O (1). Cela signifie qu'appeler list.add(newItem) prend O (1), mais qu'il n'y a parfois pas de place à la fin de la liste, donc la liste entière doit être copiée dans la nouvelle mémoire avant que ArrayList puisse effectuer l'ajout.Cependant, puisque chaque fois que ArrayList se redimensionne elle double la capacité précédente, cette opération de copie ne se produit que si n fois lors de l'ajout de n éléments. Donc nous disons toujours que l'add fonctionne en O (1) temps. Si vous connaissez le nombre d'éléments que vous allez ajouter lors de la création de ArrayList, vous pouvez lui donner une capacité initiale pour améliorer les performances en évitant l'opération de copie.