7
votes

Comparaison de deux linkedlist avec lisiterator versus pour la boucle et obtenir (int index)

J'ai deux objets LinkedList toujours de la même taille. Je veux les comparer pour voir s'ils sont identiques au contenu. Quelles sont les conséquences générales de performance et de style de la création d'un lititerator pour chaque liste et de l'utilisation d'un moment HASNEXT en boucle par rapport à un compteur (int i) et d'itération de 0 à LinkedList.Size () à l'aide de LinkedList.get (i) pour obtenir et comparer les valeurs? Y a-t-il une meilleure façon de voir?

La seule chose à laquelle je peux penser, c'est que la méthode Lisiterator peut être meilleure en ce sens que je pourrais plus facilement échanger dans une autre liste comparable plus tard (pas que je planifie dessus). Je ne sais pas à quoi ressemblent les deux sous le capot, alors je ne suis pas sûr de la façon dont je voudrais leur comparer la performance-sage.

java comparison linked-list

0 commentaires

3 Réponses :

7
votes

Comme il s'avère abstracttractlist.equals () (quel lingedlist utilise) le fera automatiquement afin d'utiliser cela. Le code est: xxx

donc ne réinventez pas la roue.

une dernière note: N'utilisez pas Obtenir (index) à itérer sur un linkedlist . C'est o (n) accès (O (1) pour un arraylist ) de sorte qu'un linkedlist Traversal à l'aide de obtenez (index) sera O (n ^{2 ).}



                                                                    
                                    
                                    
                                        3 commentaires
                                        
                                                                                            
                                                    Merci. C'est semblable à ce que j'utilise.                                                
                                                
                                                                                            
                                                    Ne serait-il pas préférable de retourner de faux tout de suite, lorsque les deux listes sont de taille différente, au lieu de votre dernier retour conditionnel?                                                
                                                
                                                                                            
                                                    Ouais, je pense qu'un contrôle rapide sur les tailles serait une bonne idée de prévenir itérant à travers des listes de tailles différentes en premier lieu. Bonne prise.


                        
                                            
                            
                                
                                    5
 votes
                                
                            
                            
                                
                                     accès aléatoire dans un  linkedlist  a des performances horribles (il doit commencer à une extrémité et invoquer  suivant  ou similaire à plusieurs reprises), donc le  lisiterator (code)  serait plus rapide.                                 


                                                                    
                                    
                                    
                                        1 commentaires
                                        
                                                                                            
                                                    Merci, cela a un sens complet. J'ai également juste compris que j'ai négligé la possibilité d'utiliser List1.equals (List2), qui, selon l'API, devraient avoir le comportement attendu (et je suppose qu'ils l'ont mis en œuvre avec des itérateurs).                                                
                                                
                                                                                    
                                    
                                                            

                        

                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                      obtenez (n)  code> pour les listes liées n'est pas une opération constante pour les classes qui étendent  abstractentiallist  code>; C'est  O (n)  code>. De  abstraitentielleList # Obtenir (int Index) : 

   Cette implémentation reçoit d'abord un itérateur de liste pointant vers l'élément indexé (avec  lisiterator (index)  code>). Ensuite, il obtient l'élément utilisant  lisiteratorator.next  code> et le renvoie.  P>
 blockQuote> 
 Généralement, vous ne voulez pas faire un accès aléatoire sur des collections qui ne mettent pas en œuvre l'interface de marqueur   java.util.randomAccess  code> .  P> 

   En règle générale, une mise en œuvre de la liste doit mettre en œuvre cette interface si, pour des instances typiques de la classe, cette boucle:  p>

 for (Iterator i=list.iterator(); i.hasNext(); )
     i.next();

                                

                                                                    
                                    
                                    
                                        0 commentaires